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
-
0Given a connected graph, suppose you make a new tree by duplicating each edge. Won't this new graph have two spanning trees with absolutely no edges in common? – 2012-12-10
-
0@FunkSkunk: Duplicating each edge? – 2012-12-10
-
0@FunkSkunk: A simple graph can't have multiple edges between each vertex. – 2012-12-10
-
0@TomOldfield: Right, I missed that. Sorry. – 2012-12-10
-
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".
-
3The complete graph? This example shows that you can have two edge disjoint spanning cycles. – 2012-12-10
-
0@Graphth which is a stronger result, remove one edge from each cycle and we get two edge disjoint spanning trees, I think. It wasn't my intention to go the "whole way around" to get the cycles. – 2012-12-10
-
0Oh yes, I know it is a stronger result. I actually had, "which is a stronger result." but then decided to delete it. That was the point of the second part of the comment, to show it is stronger. But, the first part of my comment was to ask, did you mean complete instead of connected? – 2012-12-10
-
0@Graphth I definitely did! Sorry for misunderstanding, thanks for pointing it out! – 2012-12-10
-
0If am an not mistaken, the complete graph on $2k + 1$ vertices can be decomposed into $k$ disjoint spanning cycles, which is *much* stronger than OP's original request. – 2012-12-10
-
0@AustinMohr My graph theory's not great, so I might be wrong, but I'm not totally convinced for e.g. k = 4. Certainly there is a distinct cycle for each integer $n$ co-prime to and less than or equal to $k$, by picking a starting point and then travelling to the $n^{th}$ point along, but if $2k+1$ is not prime, can we find the other cycles? – 2012-12-10
-
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