Do any two spanning trees of a simple graph always have some common edges?

I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn’t find any counter example so far. But I couldn’t prove or disprove this either. How to prove or disprove this conjecture?

Answer

No, consider the complete graph K4:

It has the following edge-disjoint spanning trees:
enter image description here

Attribution
Source : Link , Question Author : Mr. Sigma. , Answer Author : Bjørn Kjos-Hanssen

Leave a Comment