Proving that a Graph has a Spanning Tree which has an edge e 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?
 A: 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$.
A: G \ E(T) is not necessarily still connected. You could have a bridge in E(T).
How about considering cases: If $e$ is a bridge, then it must clearly be in any spanning tree. If it is not, then consider the subgraph G \ $e$. G must still be connected, so there is a spanning tree T on G \ $e$. Then there is a path from $v_1$ to $v_2$, where, these are the vertices adjacent to $e$. Remove some edge $f$ of this path and add in $e$ to T. This is still a spanning tree.
A: (This is essentially the same as Joffan's solution, but I forgot to click "post" when I originally wrote it.)
A modification of your idea does work. You cannot remove the entire tree $E(T)$, because that will often leave $G$ unconnected. Instead, remove only one edge from $E(T)$ such that $G$ remains connected. Such an edge always exists. Then you keep removing edges like this until the spanning tree $T$ that you get includes edge $e$, which must happen eventually.
To prove that an edge always exists in $E(T)$ such that removing it $G$ remains connected: consider adding edge $e$ to $T$.
If $e = (x,y)$, then there exists a path from $x$ to $y$ in $T$. Remove one of those edges, say $v$, and show that $E(T) \cup \{e\} \setminus \{v\}$ is still a spanning tree for the graph, so it is connected.
