What is the maximum number of edges in an acyclic undirected graph with n…

Concept

An undirected graph that contains no cycle is called a forest. A tree is the special case of a forest that is also connected. Connectedness is the only difference between the two ideas — a forest may fall into any number of separate acyclic pieces, while a tree is one single acyclic piece.

This gives the governing counting identity: a forest on n vertices that splits into k connected components has exactly n − k edges. Each component holding ni vertices is itself a tree and so carries ni − 1 edges; summing over the k components gives (n1 − 1) + … + (nk − 1) = n − k.

Applying it here

1. The graph is required to be acyclic, so it is a forest. Write k for its number of connected components; k can be anything from 1 (all vertices in one piece) up to n (no edges at all).

2. By the identity above, its edge count is fixed by k alone: edges = n − k.

3. The count n − k grows as k shrinks, so the edge count is largest at the smallest admissible k, namely k = 1.

4. k = 1 means the forest is connected — that is, it is a single tree — and substituting k = 1 gives edges = n − 1.

Cross-check and contrast

Approaching from the other side confirms the bound. Take any tree on n vertices and add one further edge. Its two endpoints already have a path between them inside the tree, so the new edge closes that path into a cycle. An acyclic graph therefore can never carry n or more edges, and n − 1 is genuinely the maximum rather than merely an attainable value.

The forest-versus-tree distinction that drives the whole argument:

A worked instance on n = 5: one tree on all five vertices carries 5 − 1 = 4 edges, whereas a forest of two pieces — a chain through three vertices plus a single edge joining the other two — carries only 2 + 1 = 3 = 5 − 2 edges. More components always means fewer edges.

Result: the maximum number of edges in an acyclic undirected graph on n vertices is n − 1, reached exactly when the forest is a single tree.