Note: Not homework/assignment question, review for an exam.
The question is as follows:
Let G be a connected graph, and let e be an edge in G. Prove that there exists a spanning tree in G that contains e.
My thoughts:
I was thinking that in order to approach this proof, I could use the fact that all connected graphs have a spanning tree. So knowing this,
For Graph G, let T be a spanning tree which does not contain e. Removing all the edges of T while keeping G connected, we will get some G \ E(T). But since G is still connected, there will be another spanning tree in G \ E(T). Knowing this, we can keep doing this until we find a spanning tree which contains e since G is connected.
Is my logic sound?
Best Answer
I think you almost have a proof, but just need to adapt it a little.
Consider $G\backslash e$. Two cases:
$G\backslash e$ is not connected. This means that every spanning tree of $G$ must contain $e$ and we are done.
$G\backslash e$ is connected. This means that there is some spanning tree $T$ of $G\backslash e$, so consider $T{+}e$. Now since we have added an edge to a tree, there must be a circuit, and that circuit must contain $e$ (since otherwise $T$ would already contain a circuit, which it doesn't). Now remove some other edge $f$ on a circuit that contains $e$, and $T{+}e{-}f$ is still connected - because the points that $f$ connected are still connected around the circuit - and is now a tree again, and also must be a spanning tree of $G$ that contains $e$.