Problem
COM-B2-M07-P004 Minimum Edges for Connectedness
#4
★★☆☆☆ Level 2 of 5
Prove that a connected graph on \(n\) vertices has at least \(n-1\) edges.
Delete redundant edges until a spanning tree remains.
Every connected graph has a spanning tree. A spanning tree contains all \(n\) vertices and has exactly \(n-1\) edges. The original graph contains all edges of this tree and possibly more. Hence it has at least \(n-1\) edges.
The problem connects connectedness and trees.