Problem
COM-B1-M09-P023 Remove an Edge Without Losing Connectedness
#23
★★★★☆ Level 4 of 5
A connected graph has \(9\) vertices and \(9\) edges. Prove that one can remove an edge so that the graph remains connected.
A connected graph with at least as many edges as vertices contains a cycle.
Since the number of edges equals the number of vertices, the graph contains a cycle. Take any edge of this cycle. If it is removed, its endpoints are still connected by the rest of the cycle. All other connections remain, so the graph stays connected.
Useful idea: an edge on a cycle is not a bridge.