HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

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

Submitted by: @import:stackexchange-cs··
0
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:

Context

StackExchange Computer Science Q#101038, answer score: 47

Revisions (0)

No revisions yet.