5
$\begingroup$

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!

  • 0
    @FunkSkunk: Since this doesn't answer the question, you can delete this answer.2012-12-11

2 Answers 2

9

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.

  • 0
    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!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