Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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|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
1  
Those correspond exactly to odd cycles in the graph. –  beauby Nov 16 '12 at 9:04
add comment

Your Answer

 
discard

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.