My instinct is yes, but I don't know how to formalize it into a proof. I still haven't wrapped my head around spanning trees yet. Any thoughts are appreciated!
Suppose there are two different spanning trees for a simple graph. Must they have an edge in common?
5
$\begingroup$
graph-theory
discrete-mathematics
trees
-
0@FunkSkunk: Since this doesn't answer the question, you can delete this answer. – 2012-12-11
2 Answers
9
The answer is no. Consider this counterexample:
The red edges form the edges of one spanning tree.
The black edges form the edges of another spanning tree.
-
0Ah you're right... Guess that'll teach me to make assumptions instead of drawing out a graph. Pictured it in my head wrong. Thanks for the correction! – 2012-12-10
6
The complete graph with $5$ verticies provides a counterexample, you can go "around the outside" or "around the star".
-
0@TomOldfield See http://books.google.com/books?id=pA567ECRN_kC&pg=PA10 for Walecki's decomposition of $K_n$ into Hamilton cycles. According to http://arxiv.org/pdf/1204.3709.pdf, one can even decompose $K_n$ into cycles of various lengths as long as the obvious necessary condition is maintained. – 2012-12-11