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.
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?