# Breadth first search and bipartiteness

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

-

## 1 Answer

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.

-
@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