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

• Why do you say that $G \setminus E(T)$ is still connected? There is no reason it will still be connected. It will still have maybe the single edge $e$, but it will likely not be connected. – 6005 Mar 1 '17 at 7:15
• Can I instead remove the edges that allow it to stay connected? I'm unsure of how else to approach the proof. Could you offer a solution? – efxgamer Mar 1 '17 at 7:17
• I thought about doing it with contradiction but unsure of where that would go... – efxgamer Mar 1 '17 at 7:18

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

• when you mean circuit, are you referring to a cycle? If so, I think this really helps! – efxgamer Mar 1 '17 at 7:36
• also, is there a general way of thinking about proofs like this? I really appreciate the help. – efxgamer Mar 1 '17 at 7:37
• As I say you were thinking in a reasonable way about adding and removing edges, just needed to flip into keeping the non-$e$-containing spanning tree. – Joffan Mar 1 '17 at 7:45

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.

• thank you very much for your insight. – efxgamer Mar 1 '17 at 7:37

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