Trees

Removing any edge from a tree disconnects it, and adding any edge creates a cycle — a tree has exactly the number of edges needed to connect everything, with no redundancy and no shortage. These three conditions each pin down that "just enough" structure from a different angle.

We show (i) connected and acyclic $\implies$ (ii) connected with $n-1$ edges $\implies$ (iii) acyclic with $n-1$ edges $\implies$ (i), which chains all three together.

**(i)$\implies$(ii)**, by induction on $n$. The base case $n=1$ is immediate: a single vertex has $0 = n-1$ edges. For the inductive step, take a connected acyclic graph $T$ on $n\ge2$ vertices. Since $T$ is finite and acyclic, it must contain a leaf $v$ (a vertex of degree $1$): otherwise every vertex would have degree $\ge 2$, and following edges out of any starting vertex without immediately backtracking would eventually revisit a vertex, producing a cycle. Deleting $v$ and its one incident edge leaves a graph $T'$ on $n-1$ vertices that is still connected ($v$ had no other vertices depending on it to stay connected) and still acyclic (a subgraph of an acyclic graph is acyclic). By the inductive hypothesis, $T'$ has $(n-1)-1$ edges, so $T$ has $(n-1)-1+1 = n-1$ edges.

**(ii)$\implies$(iii)**. Suppose $T$ is connected with $n-1$ edges. If $T$ had a cycle, deleting one edge of that cycle would keep the graph connected (the two endpoints of the deleted edge are still joined by the rest of the cycle), giving a connected graph on $n$ vertices with only $n-2$ edges. But any connected graph on $n$ vertices needs at least $n-1$ edges (each new vertex beyond the first needs at least one new edge to reach it), so $n-2$ edges cannot connect $n$ vertices — a contradiction. So $T$ has no cycle, i.e. it is acyclic.

**(iii)$\implies$(i)**. Suppose $T$ is acyclic with $n-1$ edges, and let it have $c$ connected components. Each component is itself connected and acyclic, so by the already-proven direction (i)$\implies$(ii) applied to each component separately, a component with $n_i$ vertices has $n_i - 1$ edges. Summing over all components, the total edge count is $\sum_i (n_i - 1) = n - c$. Since the total is given as $n-1$, we get $n - c = n - 1$, so $c=1$: $T$ is connected.

It answers a purely combinatorial question — how many different ways can $n$ distinguishable points be wired into a tree-shaped network — with a strikingly simple closed formula, and the encoding trick used to prove it (Prüfer sequences) turns "count the trees" into "count the sequences," a much easier problem.

Fix the vertex set $\{1,\dots,n\}$ and, for $n\ge2$, define the Prüfer sequence of a labeled tree $T$: repeatedly find the leaf with the smallest label, write down the label of its unique neighbor, and delete that leaf; stop once $2$ vertices remain. This records $n-2$ labels (one per deletion, since we start with $n$ vertices and stop at $2$), so every labeled tree produces a sequence in $\{1,\dots,n\}^{n-2}$.

There are exactly $n^{n-2}$ such sequences, since each of the $n-2$ positions is independently any of the $n$ labels. It remains to show this encoding is a bijection, so that labeled trees are in exact one-to-one correspondence with these sequences.

The key fact is that in the Prüfer sequence, label $i$ appears exactly $\deg(i)-1$ times: every time one of $i$'s neighbors is deleted as a leaf, $i$ is written down once, and $i$ itself is only ever deleted (contributing no writes) once all but one of its incident edges are gone. In particular, the labels that never appear in the sequence are exactly the original leaves. This lets us decode: given a sequence $(a_1,\dots,a_{n-2})$, repeatedly take the smallest label not currently used as a remaining sequence entry or already attached, join it by an edge to the first remaining sequence entry, remove that label from further consideration and remove that entry from the sequence; after all $n-2$ entries are consumed, join the $2$ labels left over by a final edge.

This decoding procedure exactly reverses the encoding step by step — at each stage it identifies the same smallest-label leaf and the same neighbor that the encoder would have recorded, by induction on the number of vertices remaining. So encoding and decoding are mutually inverse, giving a bijection between labeled trees on $n$ vertices and sequences in $\{1,\dots,n\}^{n-2}$. Since there are $n^{n-2}$ such sequences, there are exactly $n^{n-2}$ labeled trees on $n$ vertices.