Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

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

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.

share|cite|improve this answer
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! – 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".

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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