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

I have been thinking about this question for a long time and have made no progress.

  • $\begingroup$ There are two directions; have you made progress on either? $\endgroup$ – vadim123 May 23 '13 at 16:48
  • $\begingroup$ 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... $\endgroup$ – TheNotMe May 23 '13 at 16:54
  • $\begingroup$ It wasn't apparent that you know there are two directions; the title reflects only one. $\endgroup$ – 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.


I did this prove, whis is kinda similar to the second of 77474.

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


Hint ("only if"): Imagine you have a spanning tree in the graph which doesn't contain the cut-edge. What happens to the graph if you remove this cut edge? What happens to the spanning tree?

Hint ("if"): What happens if you remove this "indispensable" edge (the one which is in every spanning tree)? Can the resulting graph have any spanning tree? What kinds of graphs don't have any spanning tree?


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.