Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was just wondering what the correlation is between a breadth-first search tree of a graph and that graph being bipartite?

share|cite|improve this question
up vote 5 down vote accepted

A bipartite graph is a graph that you can $2$-color. If you fix the color of one vertex (the source), then the rest of the coloring (provided that it exists) is totally defined by the distance to the source vertex. Hence, your graph is bipartite if and only if there is no "horizontal" edge in your BFS tree.

share|cite|improve this answer
@Mark. Is this answer what you were looking for ? – beauby Nov 15 '12 at 6:21
Yes, that's what I was looking for but under what circumstances would we get a "horizontal" edge in our BFS tree? – Gonz Nov 16 '12 at 3:58
Those correspond exactly to odd cycles in the graph. – beauby Nov 16 '12 at 9:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.