Problem
COM-B2-M07-P008 Connected Graph with \(n-1\) Edges
#8
★★★☆☆ Level 3 of 5
A connected graph has \(n\) vertices and \(n-1\) edges. Prove that it is a tree.
If there is a cycle, one can remove an edge of the cycle and keep connectedness.
Suppose the graph contains a cycle. Remove one edge of this cycle; connectedness remains. Then we obtain a connected graph on \(n\) vertices with \(n-2\) edges.
But a connected graph on \(n\) vertices has at least \(n-1\) edges. Contradiction. Hence there are no cycles, and the graph is a tree.
Important: connectedness is needed here.