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!

  • $\begingroup$ Given 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? $\endgroup$ – user52557 Dec 10 '12 at 22:48
  • $\begingroup$ @FunkSkunk: Duplicating each edge? $\endgroup$ – Graphth Dec 10 '12 at 22:49
  • $\begingroup$ @FunkSkunk: A simple graph can't have multiple edges between each vertex. $\endgroup$ – Tom Oldfield Dec 10 '12 at 22:50
  • $\begingroup$ @TomOldfield: Right, I missed that. Sorry. $\endgroup$ – user52557 Dec 10 '12 at 23:10
  • $\begingroup$ @FunkSkunk: Since this doesn't answer the question, you can delete this answer. $\endgroup$ – Graphth Dec 11 '12 at 0:13

The answer is no. Consider this counterexample:enter image description here

The red edges form the edges of one spanning tree.

The black edges form the edges of another spanning tree.

  • $\begingroup$ Ah 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! $\endgroup$ – John Dec 10 '12 at 23:25

The complete graph with $5$ verticies provides a counterexample, you can go "around the outside" or "around the star".

  • 3
    $\begingroup$ The complete graph? This example shows that you can have two edge disjoint spanning cycles. $\endgroup$ – Graphth Dec 10 '12 at 23:03
  • $\begingroup$ @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. $\endgroup$ – Tom Oldfield Dec 10 '12 at 23:06
  • $\begingroup$ Oh 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? $\endgroup$ – Graphth Dec 10 '12 at 23:11
  • $\begingroup$ @Graphth I definitely did! Sorry for misunderstanding, thanks for pointing it out! $\endgroup$ – Tom Oldfield Dec 10 '12 at 23:13
  • $\begingroup$ If 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. $\endgroup$ – Austin Mohr Dec 10 '12 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.