Explaination of Graph Theory concept

35 Views Asked by At

Can anyone please let me know the proof or intuition behind the statement given below? "Given the connected graph, if you take any one of the spanning tree then remaining part of graph is bipartite"

1

There are 1 best solutions below

0
On

The statement as it is now is false: Take $K_5$ for example.

Let the vertices be $v_1, v_2, v_3, v_4, v_5$ and the chosen spanning tree to be the path $v_1 - v_2 - v_3 - v_4 - v_5$.

Then in the complement we have an odd cycle $v_1 - v_3 - v_5 - v_2 - v_4 - v_1$ hence the new graph can't be bipartite.