Prove: an edge e of a connected undirected simple graph G is a cut-edge if and only if it belongs to every spanning tree of G.

Pretty lost on this one. What's a way to connect cut-edges to tree, and how would one go about proving this?

  • $\begingroup$ Hint: Prove that a cut edge can never be part of a cycle. $\endgroup$ – platty Aug 14 '17 at 14:17

Here are two facts you could use to prove this.

An edge $e\in E(G)$ is a cut-edge $\Longleftrightarrow$ $G-e$ is disconnected.

This is the definition.

A graph $G$ is disconnected $\Longleftrightarrow$ $G$ has no spanning trees.

This connects spanning trees with connection.


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.