patternMajor
Do any two spanning trees of a simple graph always have some common edges?
Viewed 0 times
simpleedgesgraphanyalwaystreestwocommonsomespanning
Problem
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?
Solution
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
It has the following edge-disjoint spanning trees:
Context
StackExchange Computer Science Q#101038, answer score: 47
Revisions (0)
No revisions yet.