Why does an undirected graph with n vertices have at most $n(n-1)/2$ edges?

Conditions

• G is an undirected graph.
• G has n vertices.
• We seek the possible maximum number of edges.

Reasoning, step by step

1. Identify that each vertex can connect to n-1 other vertices.
2. Sum the connections for all n vertices, yielding $n(n-1)$.
3. Divide by 2 because each undirected edge is counted twice (once for each endpoint).
4. Conclude that the maximum number of edges is $n(n-1)/2$.

Example

For a complete graph with 5 vertices, the presenter counts the edges as $4+3+2+1$, which equals $5*4/2 = 10$. This generalizes to $n(n-1)/2$ for n vertices.

Common misconceptions

• Confusing the maximum number of edges in an undirected graph with that in a directed graph (which is $n(n-1)$).
• Assuming that a connected graph must be a complete graph, whereas a connected graph only requires a path between vertices, not direct adjacency.

Watch the explanation

Explore next

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