Problem
COM-B2-M07-P007 Removing an Edge of a Cycle
#7
★★★☆☆ Level 3 of 5
Prove that if one removes an edge lying on a cycle from a connected graph, the graph remains connected.
On the cycle there is an alternate path between the endpoints of the removed edge.
Let the removed edge join \(u\) and \(v\). Since it lies on a cycle, after removing it, the rest of the cycle still contains a path from \(u\) to \(v\).
Any path in the original graph that used edge \(uv\) can be modified: replace \(uv\) by this alternate path. Hence connectedness is preserved.
A basic lemma for constructing a spanning tree.