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.

If we have a simple connected graph, G, is the following statement true and if it is true, prove it.

For any two edges of G, there is a spanning tree, T, of G that contains both edges.

I have decided that the statement is infact ture but am a bit stuck on how to prove it.

Is it important to consider the two cases: 1) The two edges have a common vetex, 2) The two edges have no common vertices

Here is my proof so far:

If all the edges of the graph are included in the spanning tree there is nothing to do.

First case - the two edges have a common vertex Say the edges are xy and xz where x is the common vertex. Because T is a spanning of G there is exactly one path between x y, y z, and z x. If we delete two edges so that these three vetices are no longer joined and then replace the edges with the direct egdes between x y, and x z then the result is connected and has the same number of edges so is therefore a spanning tree.

... then something similar for the second case.

Any improvements, problems with this prove or better ideas would be lovely.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Let $T$ be the spanning tree. If $T$ already contains the two edges $e$ and $f$, then we're done. Suppose $T$ contains $e$ but not $f$. Add $f$ to $T$. Now $T+f$ has a unique cycle. This cycle has at least three edges, so an edge $g$ which is neither $e$ nor $f$ exists in this cycle and $g$ can be removed to produce a desired tree $T+f-g$. If $T$ contains neither $e$ nor $f$, $T+e$ has a unique cycle, from which an edge $g$ can be removed to produce a tree that contains $e$, and now we are back to the earlier case where $T$ contains at least one of $e$ or $f$.

share|improve this answer
    
Thank you, that is a very clear and clever proof. –  user64740 Mar 4 '13 at 18:44

Your Answer

 
discard

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