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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.