Problem
COM-B1-M09-P009 Minimum Edges for Connectedness
#9
★★☆☆☆ Level 2 of 5
What is the minimum number of edges in a connected graph on \(10\) vertices?
A connected graph on \(n\) vertices has at least \(n-1\) edges.
The minimum is \(10-1=9\). It is achieved by a path on \(10\) vertices. Fewer edges are impossible because each new vertex needs at least one edge to join the connected part already built.
Give both lower bound and example.