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

Conditions

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

Reasoning, step by step

1. Separate one vertex to remain isolated, ensuring the graph is disconnected.
2. Connect all remaining n-1 vertices to each other to form a complete subgraph.
3. Calculate the number of edges in this complete subgraph using the formula for n-1 vertices: (n-1)((n-1)-1)/2.
4. Simplify the expression to (n-1)(n-2)/2.

Example

The presenter constructs an example with 6 vertices (A, B, C, D, E, F). Vertices A through E form a complete graph ($5*4/2 = 10$ edges), while F is isolated. This matches the formula (6-1)(6-2)/2 = 10.

Common misconceptions

• Incorrectly assuming that the isolated vertex can be connected to other vertices without violating disconnectedness.
• Relying solely on the presenter's verbal explanation, which mistakenly stated the formula as $n(n-1)(n-2)/2$, instead of the correct on-screen formula (n-1)(n-2)/2.

Watch the explanation

Explore next

• Why does an undirected graph with n vertices have at most $n(n-1)/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?