0
$\begingroup$

I am unsure how to approach this problem:

Prove that an undirected graph is bipartite if and only if there are no edges between nodes at the same level in its BFS tree. (An undirected graph is defined to be bipartite if its nodes can be divided into two sets X and Y such that all edges have one endpoint in X and the other in Y.)

Any help would be awesome!

Thank you in advance

$\endgroup$
1
$\begingroup$

Look at the distance that BFS assigns to each vertex, and color that vertex with respect to its distance.

$\endgroup$
0
$\begingroup$

Hint: Use the facts that a graph is bipartite if and only if it has no cycles of odd length, and that adding an edge to a spanning tree creates a unique cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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