Proving that a Graph has a Spanning Tree which has an edge e

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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