Problem
COM-B1-M09-P015 Connected Graph with \(n-1\) Edges
#15
★★★☆☆ Level 3 of 5
Prove that a connected graph on \(n\) vertices with \(n-1\) edges has no cycles.
If there is a cycle, remove one edge of the cycle and connectedness remains.
Suppose there is a cycle. Remove one edge of this cycle. Its endpoints are still connected by the rest of the cycle, so the graph remains connected. We get a connected graph on \(n\) vertices with \(n-2\) edges, impossible because a connected graph has at least \(n-1\) edges. Hence there are no cycles.
One characterization of a tree in action.