# Prove that a cut edge is in every spanning tree of a graph

Given a simple and connected graph $$G = (V,E)$$, and an edge $$e \in E$$. Prove:

$$e$$ is a cut edge if and only if $$e$$ is in every spanning tree of $$G$$.

• There are two directions; have you made progress on either? – vadim123 May 23 '13 at 16:48
• Not at all, I know there are two directions. In both of them I just did not get any clue on where to start, I mean what kinda trick to use... – TheNotMe May 23 '13 at 16:54
• It wasn't apparent that you know there are two directions; the title reflects only one. – joriki May 23 '13 at 16:54

Suppose $e$ is not a cut edge. Then $G\setminus e$ is connected. Now, considering any spanning tree $T$ of $G\setminus e$ we see that $T$ is a spanning tree of $G$ as well.
Now let $e$ be a cut edge and let $T$ be a spanning tree of $G$ with $e\notin T$. Then $T$ must be a spanning tree of a disconnected graph, a contradiction.
Be $$G$$ a connected graph and $$e$$ be a cut edge. Additional $$G'= G-e$$ is disconnected .Then be $$T$$ a spanning tree of $$G$$. Note that if $$G'= G-e$$ is disconnected then $$T-e$$ is also disconnected and $$T$$ would not be a spanning tree. A contradiction.Furthermore $$e\in E(T)$$