If no cycle in graph $G$ contains edge $e$, then every spanning tree of graph $G$ contains $e$.

Question

Let $G$ be a connected graph. Prove that the following statements are equivalent:

$(i)$ $G-e$ is not connected.

$(ii)$ No cycle in $G$ contains edge $e$.

$(iii)$ Every spanning tree of $G$ contains $e$

I did a contrapositive proof to show that $(i)$ $\implies$ $(ii)$

Suppose there is a cycle $C$ in $G$ that contains edge $e =(uv)$. This means that there exists a path $P'$ from vertices $u$ to $v$ not containing $e$. So $G-e$ is connected.

I want now to prove that $(ii)$ $\implies$ $(iii)$. This is what I tried:

I supposed that $T$ is a spanning tree of $G$ NOT containing edge $e$. Then $T+e$ contains a cycle.

Is this enough to prove that $(ii)$ $\implies$ $(iii)$

What approach should I take, because I do not feel that this is the correct way.

Thank you in advance for any help.

Answer 1

If $T$ is a spanning tree and $e\notin E(T)$, then $T+e$ contains a cycle.

This cycle necessarily contains $e$, because otherwise this cycle is contained in $T$, and this contradicts the fact that $T$ is a tree.

It seems to me that no further arguments are needed and the author of the question is absolutely right.

Answer 2

Like MangoPizza said in the comments,

Let $e = (uv)$. Then because $T$ is a spanning tree (and connected by definition of tree), there exists a path $(e_1, \dots, e_n)$ in $T$ connecting $u$ and $v$. Also, this path does not have $e$ as an edge. (Why?)

That means $(e_1, \dots ,e_n, e)$ is a cycle of $G$ containing $e$.