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?

  • 1
    $\begingroup$ 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. $\endgroup$ – 6005 Mar 1 '17 at 7:15
  • $\begingroup$ 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? $\endgroup$ – efxgamer Mar 1 '17 at 7:17
  • $\begingroup$ I thought about doing it with contradiction but unsure of where that would go... $\endgroup$ – 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$.

  • $\begingroup$ when you mean circuit, are you referring to a cycle? If so, I think this really helps! $\endgroup$ – efxgamer Mar 1 '17 at 7:36
  • $\begingroup$ also, is there a general way of thinking about proofs like this? I really appreciate the help. $\endgroup$ – efxgamer Mar 1 '17 at 7:37
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ thank you very much for your insight. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.