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.