Trees

A connected graph with no cycles is the leanest way to join a set of points, and the problem is to recognise such graphs and count them.

The previous lesson set up the language. Graphs here are simple (no loops or repeated edges), and by the handshake lemma the degrees (edge counts at each vertex) sum to twice the number of edges. A path is a sequence of distinct vertices each joined to the next, a cycle is a path of at least three vertices whose ends are also joined, and a graph is connected when every two vertices are joined by a path. That lesson ended on the simplest connected graphs, the ones without cycles.

Trees, forests and leaves

A tree is a connected graph with no cycles. A graph with no cycles, connected or not, is a forest, and its connected pieces are trees. A leaf is a vertex of degree $1$ . On ${1, 2, 3, 4, 5}$ the edges $12$ , $13$ , $34$ and $35$ form a tree with leaves $2$ , $4$ and $5$ .

Theorem. Every tree with at least two vertices has at least two leaves.

Take a longest path $v_{0}, v_{1}, \dots, v_{k}$ in the tree. One exists because the graph is finite, and $k \geq 1$ because a connected graph on two or more vertices has an edge. Suppose $v_{0}$ had a neighbour $w$ other than $v_{1}$ . If $w = v_{i}$ for some $i \geq 2$ , then $v_{0}, v_{1}, \dots, v_{i}$ is a cycle, which a tree does not have. If $w$ is off the path, then $w, v_{0}, \dots, v_{k}$ is a longer path, contradicting the choice. So $v_{0}$ is a leaf, and by the same argument so is $v_{k}$ , a different vertex.

A path on $n$ vertices has exactly two leaves, so the bound is sharp; a star, one centre joined to all the others, has $n - 1$ .

Every tree has n - 1 edges

If $v$ is a leaf of a tree $T$ , then $T - v$ ( $T$ with $v$ and its edge deleted) is still a tree. Deleting creates no cycle, and a path between two other vertices never passes through $v$ , since an interior vertex of a path has two neighbours and $v$ has one.

Theorem. A tree with $n$ vertices has exactly $n - 1$ edges.

By induction on $n$ , starting from one vertex and no edges. If trees on $n - 1$ vertices have $n - 2$ edges, a tree $T$ on $n \geq 2$ vertices has a leaf, and removing it takes one edge and leaves a tree on $n - 1$ vertices. So $T$ has $n - 1$ edges.

Adding over components, a forest with $n$ vertices and $c$ components has $n - c$ edges. And since a tree's degrees sum to $2 n - 2$ , averaging just under $2$ , every vertex of degree above $2$ must be paid for by leaves.

Example. A tree has one vertex of degree $4$ , two of degree $3$ , and every other vertex is a leaf. How many leaves does it have?

With $L$ leaves there are $n = 3 + L$ vertices and $2 + L$ edges. The degree sum is $4 + 3 + 3 + L = 10 + L$ , and it equals $2 (2 + L) = 4 + 2 L$ , so $L = 6$ . In general the same algebra gives $L = 2 + \sum (d - 2)$ over the vertices of degree $d \geq 3$ , here $2 + 2 + 1 + 1 = 6$ .

Now you. A tree has one vertex of degree $5$ , two of degree $3$ , one of degree $2$ , and every other vertex is a leaf. How many leaves does it have, and how many vertices?

Answer

$7$ leaves and $11$ vertices. The degree sum is $13 + L$ and there are $3 + L$ edges, so $13 + L = 6 + 2 L$ and $L = 7$ . The shortcut agrees: $2 + 3 + 1 + 1 + 0 = 7$ .

Five ways to say tree

For a graph $G$ on $n$ vertices, these are equivalent: (1) $G$ is connected and acyclic; (2) $G$ is connected with $n - 1$ edges; (3) $G$ is acyclic with $n - 1$ edges; (4) every two vertices are joined by exactly one path; (5) $G$ is minimally connected, meaning connected but disconnected by deleting any one edge. The proofs link each to the definition, (1), in both directions.

One fact does much of the work: deleting an edge $x y$ that lies on a cycle never disconnects a graph, because any path that used $x y$ can detour from $x$ to $y$ the long way round the cycle.

(1) gives (2) and (3) by the edge count. For (3) to (1): an acyclic graph is a forest, so with $c$ components it has $n - c$ edges, and $n - c = n - 1$ forces $c = 1$ . For (2) to (1): if $G$ is connected with $n - 1$ edges, delete edges on cycles, one at a time, until none remain. The graph stays connected, so it ends as a tree on $n$ vertices with $n - 1$ edges; it started with $n - 1$ , so nothing was deleted and $G$ had no cycle.

(1) gives (4). There is a path from $u$ to $v$ ; if there were two, $P$ and $Q$ , let $x$ be the last vertex before they part, and $y$ the first vertex after $x$ on $P$ that lies on $Q$ again (both end at $v$ , so there is one). The stretches of $P$ and $Q$ between $x$ and $y$ meet only at their ends and form a cycle. Conversely, a graph satisfying (4) is connected, and has no cycle, since a cycle through $u$ and $v$ would offer two paths between them, one each way round.

(1) gives (5): if deleting $u v$ from a tree left $u$ and $v$ joined by a path, that path plus $u v$ would be a cycle. Conversely (5) gives (1), since by the fact above a graph with a cycle has an edge whose deletion keeps it connected.

A graph on $n$ vertices is thus a tree once it passes any two of three tests: connected, acyclic, $n - 1$ edges.

Spanning trees

A spanning tree of a graph $G$ is a subgraph that is a tree and contains every vertex of $G$ .

Theorem. Every connected graph has a spanning tree.

While the graph has a cycle, delete an edge of that cycle. The graph stays connected, by the fact above, and keeps every vertex, and since edges run out the process stops at a spanning tree. So a connected graph with $n$ vertices and $m$ edges has $m \geq n - 1$ , and reaching a spanning tree takes exactly $m - n + 1$ deletions, whichever cycles are broken. Finding the cheapest one when edges carry costs is an algorithmic question, answered in Algorithms and Data Structures; the question here is how many there are.

Cayley's formula

A labelled tree on ${1, \dots, n}$ is a tree with those vertices, two counting as different when their edge sets differ: the paths $1, 2, 3$ and $2, 1, 3$ are different. They are the spanning trees of the complete graph $K_{n}$ , in which every pair is joined.

For $n = 2$ there is one, the edge $12$ . For $n = 3$ a tree is a path fixed by its middle vertex, so there are three. For $n = 4$ there are two shapes. A star is fixed by its centre, giving $4$ . A path on four vertices is one of the $4! = 24$ orderings, each read in both directions, giving $12$ . That makes $16$ . A second count confirms it: by characterisation (3), three of the $6$ edges of $K_{4}$ form a tree unless they are one of the $4$ triangles, leaving $(\binom{6}{3}) - 4 = 16$ .

The counts $1, 3, 16$ are $2^{0}$ , $3^{1}$ and $4^{2}$ . Carl Wilhelm Borchardt proved in 1860, via a determinant, that the pattern continues, and Arthur Cayley stated it in 1889 in "A theorem on trees".

Cayley's formula. There are $n^{n - 2}$ labelled trees on $n$ vertices.

Example. Count the labelled trees on ${1, \dots, 5}$ by shape, and compare with $5^{3} = 125$ .

The five degrees are each at least $1$ and sum to $8$ , so their excess over $1$ is $3$ , split as $3$ , as $2 + 1$ or as $1 + 1 + 1$ . The degree sequences are $4, 1, 1, 1, 1$ (a star: $5$ trees, one per centre), $2, 2, 2, 1, 1$ (a path: $\frac{5!}{2} = 60$ ) and $3, 2, 1, 1, 1$ . In the last, the degree $2$ vertex must neighbour the degree $3$ one, or those would lie in separate components. Choose the degree $3$ vertex ( $5$ ways), its degree $2$ neighbour ( $4$ ways) and the leaf hanging from that neighbour ( $3$ ways): $60$ . The total is $5 + 60 + 60 = 125$ .

Now you. Delete the edge $12$ from $K_{4}$ . How many spanning trees does the remaining graph have?

Answer

$8$ . The $16$ trees have $3$ edges each, $48$ in all, and the $6$ edges of $K_{4}$ are alike under relabelling, so each lies in $\frac{48}{6} = 8$ trees. The other $8$ avoid $12$ .

Prüfer's code

The number $n^{n - 2}$ counts the sequences of length $n - 2$ with entries from ${1, \dots, n}$ , and Heinz Prüfer found a bijection with them in 1918. To encode a labelled tree, repeat while more than two vertices remain: remove the leaf with the smallest label, and write down the label of its neighbour.

The code records degrees. A vertex $v$ is written once for each neighbour removed as a leaf, and it keeps exactly one neighbour to the end (when it is removed itself, or as one of the final two), so it appears $\deg (v) - 1$ times. The leaves are precisely the labels missing from the code.

So the first vertex removed is the smallest label missing from the code, its neighbour is the first entry, and the rest of the code is the code of the smaller tree. Decoding therefore runs: for each entry in turn, join it to the smallest label not yet crossed off and not among the entries still to come, and cross that label off; finally join the two labels left over. A tree is determined by its code.

Every sequence is a code, by induction on $n$ . For $n = 2$ the empty sequence codes the single edge. Given $a_{1}, \dots, a_{n - 2}$ , let $b$ be the smallest label missing from it. By induction $a_{2}, \dots, a_{n - 2}$ is the code of a tree $T^{'}$ on the other $n - 1$ labels; attach $b$ to $a_{1}$ . The leaves of the new tree are the labels missing from the whole sequence, so encoding removes $b$ first, writes $a_{1}$ , and continues as for $T^{'}$ . So encoding is a bijection, which proves Cayley's formula.

Example. Encode the tree on ${1, \dots, 7}$ with edges $16$ , $24$ , $34$ , $46$ , $56$ , $67$ , then decode the result.

The leaves are $1, 2, 3, 5, 7$ . Remove $1$ and write $6$ ; remove $2$ , write $4$ ; remove $3$ , write $4$ . Now $4$ is a leaf, and the smallest: remove it, write $6$ . Remove $5$ , write $6$ . Vertices $6$ and $7$ remain, and the code is $6, 4, 4, 6, 6$ : vertex $6$ , of degree $4$ , appears three times. To decode, $1$ is the smallest label missing from the code: join it to $6$ . With $4, 4, 6, 6$ to come, join $2$ to $4$ , then $3$ to $4$ . With $6, 6$ to come, $4$ is free: join it to $6$ , then $5$ to $6$ , and finally the leftover $6$ and $7$ .

Now you. Decode the Prüfer code $3, 3, 5, 1$ into a tree on ${1, \dots, 6}$ , and check by encoding it again.

Answer

The edges are $23$ , $34$ , $35$ , $15$ and $16$ : join $2$ to $3$ , then $4$ to $3$ , then $3$ (now free) to $5$ , then $5$ to $1$ , and finally the leftover $1$ and $6$ . Encoding removes the leaves $2$ and $4$ (writing $3, 3$ ), then $3$ (writing $5$ ), then $5$ (writing $1$ ).

Rooted binary trees

Choosing one vertex of a tree as its root gives the tree a direction. Each other vertex $v$ has a unique path to the root, by characterisation (4), and the next vertex on it is the parent of $v$ , which makes $v$ one of its children. A binary tree is a rooted tree in which every vertex has no children or exactly two, a left and a right, and left differs from right. The vertices with children are internal. With $n$ internal vertices there are $2 n$ children, and every vertex but the root is a child, so there are $2 n + 1$ vertices and $n + 1$ leaves.

Let $B_{n}$ count binary trees with $n$ internal vertices. A lone root gives $B_{0} = 1$ , then $B_{1} = 1$ and $B_{2} = 2$ . For $n = 3$ the root's left subtree holds $2$ , $1$ or $0$ of the other internal vertices, giving $2 + 1 + 2 = 5$ shapes. Read each internal vertex as a multiplication and the five ways to multiply $a, b, c, d$ appear: $((a b) c) d$ , $(a (b c)) d$ , $(a b) (c d)$ , $a ((b c) d)$ and $a (b (c d))$ . In general the left subtree has some $k$ internal vertices and the right $n - 1 - k$ , chosen independently, so

B_{n} = \sum_{k = 0}^{n - 1} B_{k} B_{n - 1 - k}

This is the recurrence $C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}$ that the lesson on generating functions set up for the Catalan numbers, and both start at $1$ . So $B_{n} = C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$ , giving $B_{3} = \frac{20}{4} = 5$ as listed and $B_{5} = 42$ .

Trees, then, are characterised, counted and coded, and they are easy to draw on paper without crossings: root at the top, each generation of children in a row below. Five towns each joined directly to every other, the complete graph $K_{5}$ , resist every attempt to be drawn that way. The last questions of the course are geometric: which graphs can be drawn in the plane without crossings, and how few colours their regions need so that neighbours always differ. The final lesson answers both, starting from a formula of Euler's.