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?
-
Assuming the weights of the graph are distinct, the edge with the minimum weight will be present in all the minimum spanning trees. – Gokul 2 hours ago
-
@Gokul minimum spanning tree? What?... – Mr. Sigma. 1 hour ago
-
Oh, apologies. I read the title as whether minimum spanning tree have common edges. – Gokul 1 hour ago
No, it's not true that any two spanning trees of a graph have common edges.
Consider the wheel graph:
You can make a spanning tree with edges "inside" the loop and another one from the outer loop.
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
-
2
