Why does a connected undirected graph with n vertices need at least n-1 edges?

Conditions

• G is an undirected graph.
• G has n vertices.
• G is a connected graph.

Reasoning, step by step

1. Consider a graph with n vertices.
2. To connect all vertices without redundancy, add edges one by one to link isolated vertices or components.
3. The minimum number of edges required to link n vertices into a single connected component is n-1.
4. Verify with a star graph example: 5 vertices require 4 edges to remain connected.

Example

The presenter draws a star-shaped graph with 5 vertices (A, B, C, D, E) where the central vertex C connects to the other four. This uses exactly 4 edges (n-1) to make the entire graph connected.

Common misconceptions

• Mistaking 'connected' for 'every pair of vertices must be directly adjacent', which would require $n(n-1)/2$ edges (a complete graph).
• Assuming that fewer than n-1 edges can still form a connected graph, which would leave at least one vertex isolated.

Watch the explanation

Explore next

• What is the maximum number of edges in an undirected graph with n vertices?
• Why does a disconnected undirected graph have at most (n-1)(n-2)/2 edges?
• What is the definition of a connected graph in an undirected graph?