Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers 2

up vote 8 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|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
add comment

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

share|improve this answer
3  
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
show 2 more comments

Your Answer

 
discard

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.