Lecture 12. Special graphs #

12.0 Overview: why “special” graphs deserve their own chapter #

Lecture 10 introduced graphs in the abstract — vertices, edges, degrees, walks, paths, cycles, connectivity, and the handshake identity — and Lecture 11 turned those objects into algorithms: greedy colouring, breadth-first and depth-first search, Dijkstra’s shortest paths, and the minimum-spanning-tree methods of Kruskal and Prim. A general graph, however, is almost featureless: knowing only that “some vertices are joined by some edges” tells us very little, and most interesting questions about arbitrary graphs are computationally hard.

This lecture studies special families of graphs — graphs carrying extra structure. Structure is exactly what turns a shapeless object into a theorem-rich one: the moment we insist that a graph be acyclic, or that its edges alternate between two colour classes, or that every vertex have even degree, a cascade of clean, provable consequences follows, and efficient algorithms become possible.

The centre of gravity is the tree: a connected acyclic graph. Trees are the single most important non-trivial structure in computer science. They organise:

• file systems — a root directory, folders, files, and the unique path /home/user/notes.txt from root to any file;
• expression and parse trees — how a compiler represents (a + b) * c and how a calculator evaluates reverse Polish notation;
• search structures — binary search trees, AVL and red–black trees, B-trees, heaps — where the height of the tree is the cost of an operation;
• prefix codes — Huffman coding builds an optimal full binary tree whose leaves are the symbols of an alphabet;
• decision trees, game trees, syntax trees, phylogenetic trees, and the recursion trees we draw to analyse divide-and-conquer algorithms.

We develop trees with full rigour — their several equivalent characterizations, the leaf-counting lemmas, rooted-tree vocabulary, $m$-ary and binary trees, traversals, and spanning trees — and then survey four further families that recur throughout the course: bipartite, regular, Eulerian, and Hamiltonian graphs. Two of the deepest theorems in elementary graph theory live here, and we prove both in full: the characterization of Eulerian graphs by even degrees (Euler, 1736 — the birth of graph theory), and the characterization of bipartite graphs as the graphs with no odd cycle.

Throughout, $G=(V,E)$ is a finite undirected graph with $n=|V|$ vertices and $m=|E|$ edges, simple (no loops or parallel edges) unless we explicitly allow a multigraph. We lean constantly on the handshake identity of Lecture 10,

$$\sum_{v\in V}\deg(v)=2\,|E| = 2m,$$

and on its corollary that the number of odd-degree vertices is even.

12.1 Trees: intuition and definition #

Imagine wiring up $n$ computers into one network as cheaply as possible. You need the network connected (every machine can reach every other), and you do not want to pay for redundant cable, so you avoid cycles (a cycle would let you delete a cable and stay connected). The cheapest connected layout is therefore a connected graph with no cycles — a tree. This tension, “connected but with nothing to spare,” is the essence of treeness, and the characterization theorem below makes it precise in four different languages.

Definition (Tree). A tree is a connected undirected graph that contains no cycle. Equivalently, a connected acyclic graph.

Two words carry the definition. Connected means every pair of vertices is joined by at least one path (Lecture 10). Acyclic means the graph contains no cycle, i.e. no simple closed walk of length $\ge 3$ (in a simple graph the shortest possible cycle is a triangle). A single vertex with no edges is a tree (vacuously connected and acyclic); so is a single edge.

Remark (why “no cycle of length $\ge 3$”). In a simple graph there are no loops (length-1 closed walks) and no repeated edges (length-2 closed walks), so the smallest possible cycle already has length $3$. When we later allow a multigraph (Königsberg), a pair of parallel edges does count as a cycle of length $2$.

The definitional picture is deceptively simple. What makes trees powerful is that “connected + acyclic” is only one of many equivalent descriptions.

12.2 Leaves and the two-leaf theorem #

Definition (Leaf). A leaf (or pendant vertex) of a graph is a vertex of degree $1$. A non-leaf, non-isolated vertex is an internal vertex.

Leaves are the “loose ends” of a tree, and their existence drives almost every proof about trees (they give us something to peel off and induct on). Before the big theorem we isolate the key structural fact.

Theorem 12.1 (Two-leaf theorem). Every tree with $n \ge 2$ vertices has at least two leaves.

Proof. Let $T$ be a tree with $n \ge 2$ vertices. Since $T$ is finite, among all paths in $T$ we may choose one of maximum length; call it

$$P: \quad v_0,\, v_1,\, \dots,\, v_k .$$

Because $T$ is connected and has at least two vertices it has at least one edge, so $k \ge 1$ and the endpoints $v_0 \ne v_k$ are distinct. We claim both endpoints are leaves.

Consider $v_0$. It is adjacent to $v_1$, so $\deg(v_0) \ge 1$. Suppose, for contradiction, that $v_0$ had another neighbour $w \ne v_1$. There are two cases.

1. If $w$ does not lie on $P$, then $w, v_0, v_1, \dots, v_k$ is a path of length $k+1 > k$, contradicting the maximality of $P$.
2. If $w = v_i$ for some $i \ge 2$ (it cannot be $v_1$, since $w \ne v_1$), then $v_0, v_1, \dots, v_i, v_0$ is a cycle (its length is $i+1 \ge 3$), contradicting that $T$ is acyclic.

Both cases are impossible, so $v_0$ has no neighbour other than $v_1$; that is, $\deg(v_0) = 1$ and $v_0$ is a leaf. By the identical argument applied to the other end, $v_k$ is a leaf. Since $v_0 \ne v_k$, the tree has at least two leaves. $\blacksquare$

Remark. The proof extracts more than the statement: the endpoints of any longest path in a tree are leaves. This “longest path” trick reappears when studying the diameter and centre of a tree.

Common pitfall. The hypothesis $n\ge 2$ is needed. The one-vertex tree has a single vertex of degree $0$ — that is not a leaf (leaves have degree exactly $1$), and the theorem indeed does not claim two leaves there.

12.3 The tree characterization theorem #

We first record the exact edge count, then prove the master equivalence. The edge count is proved by peeling off a leaf and inducting — precisely why Theorem 12.1 came first.

Lemma 12.2 (Edge count). A tree with $n$ vertices has exactly $n-1$ edges.

Proof. Induction on $n$. Base $n=1$: the tree is a single vertex with $0 = 1-1$ edges. Inductive step: let $n \ge 2$ and assume the claim for all trees with fewer than $n$ vertices. By Theorem 12.1, $T$ has a leaf $v$ with unique neighbour $u$. Form $T' = T - v$ by deleting $v$ and its one incident edge $uv$.

• $T'$ is acyclic: deleting a vertex and edges cannot create a cycle.
• $T'$ is connected: take any two vertices $x, y \ne v$. In $T$ there is a path from $x$ to $y$. Because $\deg_T(v) = 1$, the vertex $v$ can appear on a simple path only as an endpoint; since $x, y \ne v$, the $x$–$y$ path does not pass through $v$ and therefore survives intact in $T'$.

Hence $T'$ is a tree on $n-1$ vertices, so by the inductive hypothesis it has $(n-1)-1 = n-2$ edges. Restoring $v$ and the edge $uv$ adds exactly one edge, so $T$ has $n-1$ edges. $\blacksquare$

Corollary 12.3. In a tree with $n$ vertices, $\displaystyle\sum_{v\in V}\deg(v) = 2(n-1)$. Consequently, if $n \ge 2$, not every vertex can have degree $\ge 2$ (that would force the degree sum to be $\ge 2n > 2(n-1)$), re-proving that a tree has at least one — in fact, by Theorem 12.1, at least two — leaves.

We can now state and prove the theorem that makes trees so pleasant to work with.

Theorem 12.4 (Characterization of trees). Let $T$ be an undirected graph with $n$ vertices. The following are equivalent.

1. $T$ is a tree (connected and acyclic).
2. $T$ is connected and has exactly $n-1$ edges.
3. $T$ is acyclic and has exactly $n-1$ edges.
4. Between every pair of vertices there is a unique simple path.
5. $T$ is minimally connected: connected, but deleting any one edge disconnects it.
6. $T$ is maximally acyclic: acyclic, but adding any one edge between non-adjacent vertices creates exactly one cycle.

The proof is organised as a cycle $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1)$ establishing the equivalence of the first three, then $(1)\Leftrightarrow(4)$, $(1)\Leftrightarrow(5)$, and $(1)\Leftrightarrow(6)$. We use one small fact repeatedly, stated separately.

Fact 12.5 (Cycle edges are not bridges). If an edge $e=uv$ lies on a cycle of a graph $G$, then $G-e$ (delete the edge, keep the vertices) is still connected “through” that pair: any walk using $e$ can be rerouted along the rest of the cycle, which is a $u$–$v$ path avoiding $e$. Hence removing a cycle edge never disconnects the graph.

Proof of Theorem 12.4.

$(1)\Rightarrow(2)$. Immediate: a tree is connected by definition and has exactly $n-1$ edges by Lemma 12.2.

$(2)\Rightarrow(3)$. Assume $T$ is connected with $n-1$ edges; we must show it is acyclic. Suppose not — suppose $T$ contains a cycle. By Fact 12.5 we may delete an edge lying on that cycle and remain connected. Repeat: each deletion removes at least one cycle while preserving connectivity. Because $T$ is finite this process halts, at a graph $T^\star$ that is connected and acyclic, i.e. a tree, on the same $n$ vertices. By Lemma 12.2, $T^\star$ has $n-1$ edges. But we deleted at least one edge, so $T^\star$ has at most $n-2 < n-1$ edges — a contradiction. Hence $T$ was acyclic all along, and being also connected with $n-1$ edges it satisfies (3).

$(3)\Rightarrow(1)$. Assume $T$ is acyclic with $n-1$ edges; we must show it is connected. Let $T$ have connected components $C_1, \dots, C_c$ with $n_1, \dots, n_c$ vertices respectively, where $\sum_i n_i = n$. Each component is connected (by definition of component) and acyclic (a subgraph of an acyclic graph), hence a tree, so by Lemma 12.2 component $C_i$ has $n_i - 1$ edges. Summing,

$$m = \sum_{i=1}^{c}(n_i - 1) = \Big(\sum_i n_i\Big) - c = n - c.$$

But $m = n-1$ by hypothesis, so $n - c = n - 1$, giving $c = 1$. Thus $T$ has a single component; it is connected, and being also acyclic, it is a tree.

This closes the cycle, so (1), (2), (3) are equivalent.

$(1)\Rightarrow(4)$. Let $T$ be a tree. Connectivity gives at least one simple path between any $x$ and $y$; we prove there is at most one. Suppose $x$ and $y$ were joined by two distinct simple paths $P$ and $Q$. Reading both from $x$, they begin at the common vertex $x$; let $a$ be the last vertex up to which they agree (so the two paths share the initial segment ending at $a$ but take different edges immediately after $a$). Both paths eventually reach $y$. Follow $P$ onward from $a$ and let $b$ be the first vertex strictly after $a$ on $P$ that also lies on $Q$ beyond $a$; such a $b$ exists because $y$ qualifies. Now the segment of $P$ from $a$ to $b$ and the segment of $Q$ from $a$ to $b$

• share only their endpoints $a$ and $b$ (by the minimal choice of $b$, no interior vertex of the $P$-segment lies on $Q$ beyond $a$), and
• differ in their first edge out of $a$ (by the choice of $a$),

so together they form a closed walk that repeats no vertex except $a=b$ at the ends — a cycle. (Its length is $\ge 3$: the two $a$–$b$ segments are distinct and, in a simple graph, at most one of them can be the single edge $ab$, so their total length is at least $3$.) This contradicts acyclicity. Hence the path is unique.

$(4)\Rightarrow(1)$. Suppose every pair of vertices is joined by a unique simple path. Existence of a path for every pair means $T$ is connected. And $T$ is acyclic: a cycle through two of its vertices $u, v$ would provide two distinct $u$–$v$ paths (its two arcs), contradicting uniqueness. So $T$ is a tree, and $(1)\Leftrightarrow(4)$.

$(1)\Rightarrow(5)$. Let $T$ be a tree; it is connected. Take any edge $e=uv$. By $(4)$ the only simple $u$–$v$ path is the single edge $e$ itself. Removing $e$ therefore leaves no $u$–$v$ path (a surviving path plus $e$ would be a cycle, impossible), so $T-e$ is disconnected. Thus $T$ is minimally connected.

$(5)\Rightarrow(1)$. Suppose $T$ is minimally connected. It is connected by hypothesis. If it had a cycle, Fact 12.5 lets us delete a cycle edge and stay connected, contradicting minimality. So $T$ is acyclic — a tree. Hence $(1)\Leftrightarrow(5)$.

$(1)\Rightarrow(6)$. Let $T$ be a tree; it is acyclic. Let $u,v$ be non-adjacent, and add the edge $e=uv$. By $(4)$ there is a unique simple $u$–$v$ path $P$ in $T$; then $P + e$ is a cycle. It is the only cycle in $T+e$: every cycle of $T+e$ must use $e$ (since $T$ itself is acyclic), and a cycle through $e$ consists of $e$ together with a simple $u$–$v$ path in $T$ — of which there is exactly one. So adding $e$ creates exactly one cycle; $T$ is maximally acyclic.

$(6)\Rightarrow(1)$. Suppose $T$ is maximally acyclic; it is acyclic. If $T$ were disconnected, pick $u, v$ in different components. They are non-adjacent, and adding $uv$ creates no cycle (a cycle would require a pre-existing $u$–$v$ path, but they lie in different components). That contradicts maximal acyclicity, which demands that adding an edge create a cycle. So $T$ is connected — a tree, and $(1)\Leftrightarrow(6)$.

All six statements are equivalent. $\blacksquare$

Worked example. Take vertices $\{1,2,3,4,5,6\}$ with edges $\{1\text–2,\, 1\text–3,\, 3\text–4,\, 3\text–5,\, 5\text–6\}$.

        2
        |
        1
        |
        3
       / \
      4   5
          |
          6

There are $n=6$ vertices and $m=5 = n-1$ edges; the graph is connected and has no cycle, so it is a tree (any one of characterizations (1)–(3) certifies this). The unique path from $2$ to $6$ is $2\text–1\text–3\text–5\text–6$, illustrating (4). Deleting the edge $3\text–5$ splits it into $\{1,2,3,4\}$ and $\{5,6\}$, confirming minimal connectivity (5). The leaves are $2,4,6$ (degree $1$); vertex $3$ has degree $3$. Degree sum $= 1+2+3+1+2+1 = 10 = 2(n-1)$, matching Corollary 12.3.

Common pitfall (the count $n-1$ is not by itself sufficient). Having $n-1$ edges does not make a graph a tree. The 4-vertex graph consisting of a triangle $\{1\text–2, 2\text–3, 3\text–1\}$ plus an isolated vertex $4$ has $n=4$ and $m=3 = n-1$, yet it is neither connected nor acyclic. Characterization (2) requires both $n-1$ edges and connectivity; (3) requires both $n-1$ edges and acyclicity. Drop either extra hypothesis and the statement fails.

12.4 Forests #

Definition (Forest). A forest is an acyclic undirected graph (not necessarily connected). Equivalently, a disjoint union of trees: each connected component of a forest is a tree.

Proposition 12.6. A forest with $n$ vertices and $c$ connected components has exactly $n - c$ edges.

Proof. Let the components be trees on $n_1, \dots, n_c$ vertices with $\sum_i n_i = n$. By Lemma 12.2 component $i$ has $n_i - 1$ edges, so the total is $\sum_i(n_i - 1) = n - c$. $\blacksquare$

A tree is the special case $c = 1$, recovering $m = n-1$. Turning the equation around, $c = n - m$: in a forest, the number of components equals vertices minus edges. This is the tiny counting engine behind the union–find data structure used by Kruskal’s MST algorithm (Lecture 11): each accepted edge merges two trees into one, dropping the component count by exactly one.

Example. A graph on $8$ vertices made of one $3$-vertex tree, one $4$-vertex tree, and one isolated vertex is a forest with $c=3$ components; it has $8 - 3 = 5$ edges. Adding an edge that joins two different components lowers $c$ to $2$ and keeps it a forest; adding an edge inside a single component would create a cycle (by the maximal-acyclic property, Theorem 12.4(6)).

12.5 Rooted trees and terminology #

Un-rooted trees are symmetric — no vertex is special. Computing almost always wants a distinguished starting point, so we single one out.

Definition (Rooted tree). A rooted tree is a tree in which one vertex is designated the root $r$. Choosing a root orients every edge conceptually away from $r$ and imposes a parent–child hierarchy determined by the unique paths of Theorem 12.4(4).

Fix a rooted tree with root $r$. For a vertex $v$:

• Parent — the vertex adjacent to $v$ on the unique path from $v$ to $r$; the root has no parent, every other vertex has exactly one.
• Child — any vertex whose parent is $v$.
• Siblings — vertices sharing the same parent.
• Ancestors — the vertices on the path from $v$ up to $r$, excluding $v$; descendants — the reverse relation ($v$’s descendants are the vertices having $v$ as an ancestor).
• Leaf — a vertex with no children; internal vertex — a vertex with at least one child. (In a rooted tree “leaf” means childless, which coincides with degree $1$ for all non-root vertices, and can also apply to the root if it has a single child in the un-rooted sense — a mild abuse we tolerate.)
• Subtree rooted at $v$ — $v$ together with all its descendants and the edges among them; itself a rooted tree with root $v$.
• Depth (level) of $v$ — the length (number of edges) of the path from $r$ to $v$; the root has depth $0$.
• Height of the tree — the maximum depth over all vertices, i.e. the length of the longest root-to-leaf path.

Depth 0:            A            (root)
                   / \
Depth 1:          B   C
                 / \
Depth 2:        D   E

Example. In the rooted tree drawn above (root $A$; children $B, C$ of $A$; children $D, E$ of $B$): $A$ is the root at depth $0$; $B, C$ are at depth $1$ and are siblings; $D, E$ at depth $2$ are siblings and children of $B$; $A$ is an ancestor of $D$, and $D$ is a descendant of $A$. Leaves are $C, D, E$; internal vertices are $A, B$. The subtree rooted at $B$ is $\{B, D, E\}$. The height of the tree is $2$.

CS connection (file systems). A Unix-like file system is a rooted tree: the root directory / is $r$, directories are internal vertices, files are leaves, and the unique path guaranteed by Theorem 12.4(4) is exactly the absolute pathname /home/user/notes.txt. Path uniqueness is what makes a pathname a well-defined address. (Symbolic links deliberately break the tree structure, turning it into a general graph — which is why link loops can hang naïve directory traversals.)

12.6 $m$-ary and binary trees; counting and height bounds #

Definition. An $m$-ary tree is a rooted tree in which every internal vertex has at most $m$ children. It is a full $m$-ary tree if every internal vertex has exactly $m$ children. A binary tree is the case $m = 2$, with each child distinguished as the left child or the right child — so a binary tree is an ordered rooted tree, and the empty left/right slot matters.

Two further shape adjectives (terminology varies between textbooks, so we pin them down):

• Perfect (a.k.a. complete) $m$-ary tree — full, and all leaves at the same depth.
• Balanced tree — every leaf is at depth $h$ or $h-1$, where $h$ is the height; the tree is “as short as possible” for its number of leaves. AVL trees and red–black trees are binary search trees that self-balance after each insertion or deletion, keeping the height $\Theta(\log n)$.

Counting vertices and leaves in a full $m$-ary tree #

Theorem 12.7. A full $m$-ary tree with $i$ internal vertices has

$$n = m\,i + 1 \quad\text{vertices and}\quad \ell = (m-1)\,i + 1 \quad\text{leaves}.$$

Proof. Every vertex except the root is the child of exactly one internal vertex, and each of the $i$ internal vertices has exactly $m$ children (fullness). Counting children, the number of non-root vertices is $m\,i$; adding the root gives $n = m\,i + 1$. The leaves are the vertices that are not internal, so $\ell = n - i = (m\,i + 1) - i = (m-1)\,i + 1$. $\blacksquare$

For a full binary tree ($m = 2$) this reads $n = 2i + 1$ and $\ell = i + 1$: the number of leaves is exactly one more than the number of internal vertices.

Example. A full binary tree with $i = 10$ internal vertices has $\ell = 11$ leaves and $n = 21$ vertices; check $i + \ell = 10 + 11 = 21 = n$. $\checkmark$

CS connection (Huffman coding). An optimal binary prefix code corresponds to a full binary tree: the symbols sit at the leaves, and the codeword for a symbol is the sequence of left/right (0/1) turns from the root. “Prefix-free” means no codeword is a prefix of another, which holds precisely because no leaf is an ancestor of another leaf. Huffman’s greedy algorithm repeatedly merges the two least-frequent subtrees, and $\ell = i + 1$ guarantees the arithmetic of the merge tree works out.

The height–leaf bound #

Theorem 12.8 (Leaf bound). An $m$-ary tree of height $h$ has at most $m^{h}$ leaves.

Proof. Strong induction on $h$. Base $h = 0$: the tree is a single vertex (the root), which is a leaf, so it has $1 = m^0$ leaf. Step: let $h \ge 1$. The root has at most $m$ children; deleting the root splits the tree into at most $m$ subtrees, each of height at most $h-1$, hence each with at most $m^{h-1}$ leaves by the inductive hypothesis. Since $h \ge 1$ the root is internal, so every leaf of the whole tree is a leaf of one of these subtrees. Therefore the number of leaves is at most $m \cdot m^{h-1} = m^{h}$. $\blacksquare$

Corollary 12.9 (Height lower bound). An $m$-ary tree with $\ell$ leaves has height $h \ge \lceil \log_m \ell \rceil$. For binary trees, $h \ge \lceil \log_2 \ell \rceil$.

Proof. From $\ell \le m^{h}$ take base-$m$ logarithms: $\log_m \ell \le h$. As $h$ is an integer, $h \ge \lceil \log_m \ell \rceil$. $\blacksquare$

Counting vertices level by level (at most $m^k$ vertices at depth $k$, proved by the same induction) gives the companion bound: an $m$-ary tree of height $h$ has at most $\frac{m^{h+1}-1}{m-1}$ vertices, and for binary trees at most $2^{h+1}-1$.

Example (perfect binary tree). A perfect binary tree of height $3$ has levels $0,1,2,3$ with $1,2,4,8$ vertices, so $2^3 = 8$ leaves and $2^{4}-1 = 15$ vertices in total — the bounds are met with equality exactly for perfect trees.

Example (why balance matters). A binary search tree holding $1{,}000{,}000$ keys in its leaves needs height at least $\lceil \log_2 10^{6}\rceil = 20$. A balanced tree achieves height $\approx 20$, so a lookup touches about $20$ nodes; a degenerate tree (a path — every internal node has one child) has height $\approx 10^6$, so a lookup can touch a million nodes. Balancing is exactly the discipline of keeping the height near its lower bound $\log_2 \ell$, which is why AVL/red–black trees guarantee $O(\log n)$ operations.

Remark (counting shapes — Catalan numbers). The number of distinct shapes of a binary tree with $n$ nodes (left/right distinguished, unlabelled) is the $n$-th Catalan number

$$C_n = \frac{1}{n+1}\binom{2n}{n},$$

so $C_1=1, C_2=2, C_3=5, C_4=14,\dots$. Catalan numbers also count balanced parenthesizations and full binary trees with $n+1$ leaves — a recurring motif in combinatorics, though beyond our present scope.

12.7 Tree traversals #

Definition (Traversal). A traversal of a rooted tree is a systematic order that visits every vertex exactly once. The cost of any of the traversals below is $\Theta(n)$ time (each vertex and edge is handled a constant number of times).

We use the specific binary tree of the slides.

(Figure — the slide binary tree.) Root $A$; $A$’s children are $B$ (left) and $C$ (right); $B$’s children are $D$ (left) and $E$ (right); $C$’s children are $F$ (left) and $G$ (right) — a perfect binary tree of three levels.

          A
        /   \
       B     C
      / \   / \
     D   E F   G

Levels are — depth $0$: $A$; depth $1$: $B, C$; depth $2$: $D, E, F, G$.

Breadth-first (level-order) traversal #

Visit vertices level by level, left to right, using a queue: enqueue the root; repeatedly dequeue a vertex, visit it, and enqueue its children left-to-right. For the figure:

$$\boxed{A\;\;B\;\;C\;\;D\;\;E\;\;F\;\;G}$$

This is exactly breadth-first search from the root (Lecture 11) applied to the tree.

Depth-first orders #

The three depth-first orders are defined recursively. For a node $x$ with left subtree $L$ and right subtree $R$:

• Pre-order — visit $x$, then $L$, then $R$ (root first).
• In-order — visit $L$, then $x$, then $R$ (root in the middle; meaningful for binary trees).
• Post-order — visit $L$, then $R$, then $x$ (root last).

Tracing the recursion on the figure:

As a sanity check: the root $A$ appears first in pre-order and last in post-order — a property that holds for every rooted tree and is a handy way to spot a miscomputed sequence.

Reconstruction. Pre-order together with in-order (or post-order together with in-order) uniquely determines a binary tree: the pre-order tells you the root; the in-order then tells you which vertices fall in the left subtree (those before the root) and which in the right (those after), and you recurse. This is precisely how the tree above is recovered from the slide’s sequences, and it is a standard exercise and interview question.

Common pitfall. In-order is only well-defined for binary (more generally, ordered) trees, because it must interleave the node “between” its left and right subtrees. For a general $m$-ary or unordered tree, pre- and post-order still make sense but in-order does not.

CS connection (expression trees). An arithmetic expression tree for $(a+b)\times c$ has $\times$ at the root, left subtree $(+\,a\,b)$, and right leaf $c$:

        ×
       / \
      +   c
     / \
    a   b

• Pre-order yields prefix / Polish notation: $\times\;+\;a\;b\;c$.
• Post-order yields postfix / reverse Polish notation: $a\;b\;+\;c\;\times$.
• In-order (with parentheses) yields the usual infix form: $(a+b)\times c$.

Post-order matches a stack machine: scanning $a\,b\,+\,c\,\times$, push operands, and on each operator pop its arguments, compute, push the result. This is why reverse Polish calculators and many virtual machines (e.g. the JVM’s operand stack) evaluate in post-order.

12.8 Spanning trees, Cayley’s formula, and the Matrix-Tree theorem #

Definition (Spanning tree). Given a connected graph $G=(V,E)$, a spanning tree is a subgraph $T$ that (i) is a tree and (ii) contains every vertex of $G$. By Theorem 12.4, a spanning tree has all $n$ vertices and exactly $n-1$ edges; it is a minimally connected / maximally acyclic skeleton of $G$.

Theorem 12.10. Every connected graph has a spanning tree.

Proof. Two constructions, either suffices.

Edge-deletion (top-down). While $G$ contains a cycle, delete an edge on that cycle. By Fact 12.5 connectivity is preserved and the process strictly decreases the edge count, so it terminates. The result is connected and acyclic — a spanning tree (it still contains every vertex, since we never delete vertices).

Search-tree (bottom-up). Run BFS or DFS from any vertex (Lecture 11). The tree edges — those that first discover a new vertex — form a connected, acyclic, spanning subgraph, hence a spanning tree. $\blacksquare$

A disconnected graph has no spanning tree, but each component has one; together they form a spanning forest. When $G$ carries edge weights, a minimum spanning tree (MST) is a spanning tree of least total weight — constructed by Kruskal’s and Prim’s algorithms in Lecture 11, which we do not repeat here. Spanning trees model loop-free broadcast in networks (the spanning-tree protocol in Ethernet switching exists precisely to break cycles that would otherwise cause broadcast storms).

Counting spanning trees: Cayley’s formula #

Theorem 12.11 (Cayley’s formula, 1889). The complete graph $K_n$ has exactly $n^{\,n-2}$ spanning trees. Equivalently, there are $n^{\,n-2}$ distinct labelled trees on the vertex set $\{1,2,\dots,n\}$.

We state it and illustrate it for small $n$ rather than proving it in full; the cleanest proof is the bijection of the next paragraph.

• $n = 1$: $1^{-1} = 1$ tree (the single vertex), by convention.
• $n = 2$: $2^{0} = 1$ tree (the single edge $1\text–2$).
• $n = 3$: $3^{1} = 3$ trees. Every tree on $3$ vertices is a path; the three labelled paths differ by which vertex is the middle: $1\text–2\text–3$, $1\text–3\text–2$, $2\text–1\text–3$.
• $n = 4$: $4^{2} = 16$ trees. Every tree on $4$ vertices is either a path $P_4$ or a star $K_{1,3}$. Labelled paths: $4!/2 = 12$ (order the four vertices, divide by the two directions). Labelled stars: $4$ (choose the centre). Total $12 + 4 = 16$. $\checkmark$

Prüfer’s bijection (idea). Cayley’s exponent $n-2$ is explained by a beautiful encoding due to Prüfer (1918). Given a labelled tree on $\{1,\dots,n\}$ with $n \ge 2$, repeat $n-2$ times: find the leaf with the smallest label, record the label of its unique neighbour, and delete the leaf. This produces a Prüfer sequence — a string of length $n-2$ over the alphabet $\{1,\dots,n\}$. The map is a bijection between labelled trees and such strings, and there are exactly $n^{\,n-2}$ strings, which is Cayley’s formula. (Decoding reverses the process.) The vertices appearing in the sequence are the internal vertices; a vertex’s number of appearances is its degree minus one — a useful fact in itself.

The Matrix-Tree theorem (for general graphs) #

For a graph other than $K_n$, the count is given by a determinant.

Theorem 12.12 (Kirchhoff’s Matrix-Tree theorem, 1847). Let $G$ be a connected graph with adjacency matrix $A$ and diagonal degree matrix $D$, and form the Laplacian $L = D - A$. Then the number of spanning trees of $G$ equals the value of any cofactor of $L$ (delete any one row and the matching column, and take the determinant of what remains).

We use it as a black box. Applied to $K_n$ (whose Laplacian is $nI - J$) it recovers Cayley’s $n^{n-2}$, tying the two results together.

Examples.

• $K_4$ has $4^{\,4-2} = 16$ spanning trees; $K_5$ has $5^{3} = 125$; $K_6$ has $6^{4} = 1296$.
• The cycle $C_n$ has exactly $n$ spanning trees: deleting any one of its $n$ edges leaves a path (a tree), and no other subgraph on $n-1$ edges spans it, so there are precisely $n$ choices.

K4 (left) and two of its 16 spanning trees:

   1---2        1---2        1   2
   |\ /|        |            |   |
   | X |        |            |   |
   |/ \|        |            |   |
   4---3        4---3        4---3

12.9 Bipartite graphs and the odd-cycle theorem #

Definition (Bipartite graph). A graph $G$ is bipartite if its vertex set can be partitioned into two disjoint sets $V_1, V_2$ (the parts) so that every edge joins a vertex of $V_1$ to a vertex of $V_2$ — no edge has both endpoints in the same part. Equivalently, $G$ is properly $2$-colourable: colour $V_1$ red and $V_2$ blue and no edge is monochromatic.

Definition (Complete bipartite graph). $K_{m,n}$ has parts of sizes $m$ and $n$ with every cross pair joined; it has $mn$ edges.

Bipartite graphs model any two-sided relationship: students–courses, jobs–applicants, tasks–time-slots, senders–receivers. The central question “can these two sides be matched up?” (bipartite matching) is efficiently solvable, whereas the analogous question in general graphs is much harder — another example of structure buying tractability.

Matchings and Hall’s theorem. A matching is a set of edges no two of which share an endpoint; it is perfect if it covers every vertex. In a bipartite graph with parts $X,Y$, whether $X$ can be completely matched into $Y$ is settled by Hall’s marriage theorem: a matching saturating $X$ exists if and only if every subset $S\subseteq X$ satisfies $|N(S)|\ge|S|$ — no $k$ vertices on the left collectively see fewer than $k$ neighbours on the right. Necessity is immediate; sufficiency is proved with augmenting paths — find a path that alternates unmatched and matched edges between two exposed vertices and flip it, enlarging the matching until Hall’s condition finally blocks growth. This augmenting-path idea is the efficient algorithm alluded to above.

Theorem 12.13 (Odd-cycle characterization; cf. Lecture 10, Theorem 10.17). A graph $G$ is bipartite if and only if it contains no cycle of odd length.

Proof.

($\Rightarrow$) Bipartite $\implies$ no odd cycle. Suppose $G$ is bipartite with parts $A$ and $B$, and let $v_0, v_1, \dots, v_k = v_0$ be any cycle. Each edge crosses between the parts, so the vertices alternate: if $v_0 \in A$ then $v_1 \in B$, $v_2 \in A$, and in general $v_i \in A$ iff $i$ is even. Returning to $v_k = v_0 \in A$ forces $k$ to be even. Hence every cycle has even length; there is no odd cycle.

($\Leftarrow$) No odd cycle $\implies$ bipartite. It suffices to $2$-colour each connected component, since a disjoint union of bipartite graphs is bipartite (colour the components independently). So assume $G$ is connected and has no odd cycle.

By Theorem 12.10, $G$ has a spanning tree $T$; root it at any vertex $r$. Colour each vertex $v$ by the parity of its depth in $T$ (the length of the unique $r$–$v$ path in $T$): white if even, black if odd. This partitions $V$ into two parts; we must check that every edge of $G$ joins different colours.

Take an edge $uv \in E(G)$.

• If $uv \in T$: the depths of $u$ and $v$ differ by exactly $1$, so their parities differ and the colours differ.
• If $uv \notin T$: adding $uv$ to $T$ creates exactly one cycle (Theorem 12.4(6)), namely the unique tree path $P$ from $u$ to $v$ together with the edge $uv$. This cycle lies in $G$, so by hypothesis its length $|P| + 1$ is even, whence $|P|$ is odd. The tree-path length satisfies

$$|P| \equiv \operatorname{depth}(u) + \operatorname{depth}(v) \pmod 2$$

(because $|P| = \operatorname{depth}(u) + \operatorname{depth}(v) - 2\operatorname{depth}(\text{lca})$, where lca denotes their lowest common ancestor, and $2\operatorname{depth}(\text{lca})$ is even). Since $|P|$ is odd, $\operatorname{depth}(u)$ and $\operatorname{depth}(v)$ have different parities, so $u$ and $v$ get different colours.

Every edge is thus bichromatic, so the colouring is proper and $G$ is bipartite. $\blacksquare$

Corollary 12.14. Every tree is bipartite (it has no cycle at all, hence no odd cycle). More generally, every forest is bipartite.

Example. The $4$-cycle $C_4 = v_1v_2v_3v_4$ is bipartite with parts $\{v_1, v_3\}$ and $\{v_2, v_4\}$: BFS from $v_1$ assigns levels $0,1,2,1$, two colours with no clash. The $5$-cycle $C_5$ is not bipartite — it is itself an odd cycle, so any attempt to $2$-colour it collides after going once around.

Example (the hypercube). The $d$-dimensional hypercube $Q_d$, whose vertices are the binary strings of length $d$ with edges between strings differing in one bit, is bipartite: colour each vertex by the parity of its number of $1$s. Every edge flips one bit, hence changes the parity, so it is bichromatic. (This is Exercise S7.)

Common pitfall (Eulerian $\ne$ bipartite, etc.). “Bipartite” constrains cycles (their lengths), while “Eulerian” constrains degrees (their parities). They are unrelated: $C_4$ is both; $C_6$ is both; $C_3$ is Eulerian but not bipartite; the path $P_3$ is bipartite but not Eulerian. Do not conflate a parity condition on cycle lengths with a parity condition on vertex degrees.

12.10 Regular graphs #

Definition (Regular graph). A graph is $k$-regular if every vertex has the same degree $k$. A $3$-regular graph is also called cubic.

Proposition 12.15. A $k$-regular graph on $n$ vertices has $m = \dfrac{nk}{2}$ edges. In particular $nk$ must be even: no $k$-regular graph exists when both $n$ and $k$ are odd.

Proof. By the handshake identity, $2m = \sum_v \deg(v) = nk$, so $m = nk/2$. Since $m$ is an integer, $nk$ is even. $\blacksquare$

Familiar regular graphs: the cycle $C_n$ is $2$-regular; the complete graph $K_n$ is $(n-1)$-regular; the complete bipartite $K_{n,n}$ is $n$-regular; the hypercube $Q_d$ is $d$-regular; the Petersen graph is cubic ($3$-regular) on $10$ vertices.

Example. Can a $3$-regular graph have $5$ vertices? Then $nk = 15$ is odd, so $m = 15/2$ is not an integer — impossible. A cubic graph must have an even number of vertices (e.g. $K_4$ is cubic on $4$ vertices with $4\cdot 3/2 = 6$ edges).

12.11 Eulerian graphs and Euler’s theorem #

Definition. An Euler circuit (Eulerian circuit) is a closed walk that uses every edge exactly once and returns to its start. An Euler trail (Eulerian path) uses every edge exactly once but may start and end at different vertices. A graph with an Euler circuit is an Eulerian graph.

These conditions are about covering all edges, in contrast to the Hamiltonian conditions of §12.12 which cover all vertices. We prove Euler’s characterization for connected graphs; it holds verbatim for connected multigraphs, which we need for Königsberg. (Isolated vertices, having degree $0$, are irrelevant and are ignored; “connected” means the edges live in one piece.)

Theorem 12.16 (Euler, 1736). Let $G$ be a connected (multi)graph with at least one edge.

1. $G$ has an Euler circuit if and only if every vertex has even degree.
2. $G$ has an Euler trail but no Euler circuit if and only if exactly two vertices have odd degree; those two are the endpoints of every such trail.

Proof of (1).

($\Rightarrow$) Necessity. Suppose $G$ has an Euler circuit $C$. Fix a vertex $v$ and walk along $C$. Every time $C$ passes through $v$ it arrives on one edge and departs on another, consuming two edges incident to $v$; and because $C$ is closed, even the visits at the start/end pair up (the very first edge leaving the start and the very last edge returning to it form one such pair). Since $C$ uses each edge exactly once, the edges at $v$ are partitioned into these entry–exit pairs. Hence $\deg(v)$ is even, for every $v$.

($\Leftarrow$) Sufficiency. Suppose $G$ is connected, has an edge, and every vertex has even degree. We construct an Euler circuit (this is Hierholzer’s algorithm, 1873).

Step 1 — any maximal trail from a vertex is closed. Start at any vertex $u$ that has an incident edge and greedily extend a trail (a walk with no repeated edge), leaving each vertex on a not-yet-used edge, continuing as long as possible. Claim: the trail can only get stuck back at $u$. Indeed, consider the moment the trail arrives at some vertex $w \ne u$. Counting edges of $w$ used so far: each earlier visit to $w$ used two (in and out), and this arrival uses one more, an odd total. Since $\deg(w)$ is even, at least one edge at $w$ remains unused, so the trail can leave $w$ — it is not stuck. Only at $u$ can the parity work out to leave no exit. Therefore the maximal trail is a closed trail $C_0$ ending at $u$.

Step 2 — splice in the leftover edges. If $C_0$ uses every edge of $G$, it is an Euler circuit and we are done. Otherwise, let $H$ be the subgraph of unused edges. In passing from $G$ to $H$ we removed the closed trail $C_0$, which uses an even number of edges at every vertex (entry–exit pairs again), so every vertex of $H$ still has even degree. Because $G$ is connected, some vertex $w$ lying on $C_0$ is incident to an unused edge, i.e. $\deg_H(w) > 0$. Apply Step 1 inside $H$ starting at $w$ to obtain a closed trail $C_1$ through $w$ using only unused edges. Now splice $C_1$ into $C_0$: traverse $C_0$ until reaching $w$, detour completely around $C_1$ (returning to $w$), then finish $C_0$. The result is a longer closed trail using strictly more edges.

Step 3 — terminate. Each splice increases the number of used edges, and $G$ has finitely many edges, so after finitely many splices every edge is used. The final closed trail is an Euler circuit. $\blacksquare$

Proof of (2). First, the number of odd-degree vertices is always even (handshake corollary), so “exactly one odd vertex” is impossible and the only traversable cases are $0$ or $2$ odd vertices.

($\Leftarrow$) Suppose exactly two vertices $u, v$ have odd degree. Add a new edge $e = uv$ (a parallel edge if $u,v$ are already adjacent; the graph is allowed to be a multigraph). This raises $\deg(u)$ and $\deg(v)$ by $1$, making all degrees even, and keeps the graph connected. By part (1) there is an Euler circuit; deleting the added edge $e$ from it breaks the circuit open into a trail that uses every original edge exactly once and runs between $u$ and $v$ — an Euler trail.

($\Rightarrow$) Suppose $G$ has an Euler trail from $a$ to $b$ ($a \ne b$, since there is no Euler circuit). Add the edge $ab$; the trail plus $ab$ is an Euler circuit, so by part (1) all degrees in $G + ab$ are even. Removing $ab$ lowers only $\deg(a)$ and $\deg(b)$ by $1$, making exactly $a$ and $b$ odd and all others even. Thus exactly two vertices ($a, b$) have odd degree, and they are the trail’s endpoints. $\blacksquare$

Example (Seven Bridges of Königsberg). Königsberg’s four land masses and seven bridges form a multigraph with vertex degrees $3, 3, 3, 5$ — four odd-degree vertices.

        (A) 3
        /|  \
       / |   \
    (B)3-+---(C)3        [seven edges = seven bridges]
       \ |   /
        \|  /
        (D) 5

Euler’s theorem needs $0$ odd vertices for a circuit or exactly $2$ for a trail; with four odd vertices Königsberg has neither — no walk crosses every bridge exactly once. Euler’s 1736 analysis of this puzzle is regarded as the founding result of graph theory. By contrast, $K_5$ is $4$-regular (all degrees even) and connected, so it is Eulerian.

CS connection. The “even degree” condition powers de Bruijn graph genome assembly, where reconstructing a DNA sequence from overlapping fragments reduces to finding an Euler trail. The route-inspection (“Chinese Postman”) problem asks for the shortest closed walk covering every edge and starts from exactly this theory.

12.12 Hamiltonian graphs; Dirac’s and Ore’s conditions #

Definition. A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle (circuit) does so and returns to its start. A graph with a Hamiltonian cycle is a Hamiltonian graph.

Superficially this is Euler’s problem with “edge” replaced by “vertex,” but it is fundamentally harder. There is no known simple necessary-and-sufficient criterion for Hamiltonicity, and deciding whether a graph is Hamiltonian is NP-complete — one of Karp’s original 21 NP-complete problems, and the pure form of the Travelling Salesman Problem. What we do have are useful sufficient (not necessary) conditions that guarantee Hamiltonicity when the graph is “dense enough.”

Theorem 12.17 (Ore, 1960). Let $G$ be a simple graph with $n \ge 3$ vertices such that $\deg(u) + \deg(v) \ge n$ for every pair of non-adjacent vertices $u, v$. Then $G$ is Hamiltonian.

Corollary 12.18 (Dirac, 1952). If $G$ is a simple graph with $n \ge 3$ vertices and $\deg(v) \ge n/2$ for every vertex $v$, then $G$ is Hamiltonian.

Dirac follows instantly from Ore (any two vertices, adjacent or not, have degree sum $\ge n/2 + n/2 = n$), so we prove Ore. The argument is a classic and illustrates the “maximal counterexample + rotation” technique.

Proof of Theorem 12.17 (Ore). Suppose, for contradiction, that some graph satisfies Ore’s condition yet is not Hamiltonian. Adding an edge never decreases any degree, so Ore’s condition is preserved under adding edges; also, $K_n$ is Hamiltonian for $n \ge 3$. Therefore, starting from our graph and adding edges one at a time, we reach a graph $G$ that is a maximal non-Hamiltonian graph satisfying Ore’s condition: $G$ is not Hamiltonian, but adding any missing edge creates a Hamiltonian cycle.

Since $G$ is not complete, choose non-adjacent vertices $u, v$. Adding $uv$ produces a Hamiltonian cycle, which must use the new edge $uv$ (it is the only new edge). Deleting $uv$ from that cycle leaves a Hamiltonian path in $G$ from $u$ to $v$:

$$x_1, x_2, \dots, x_n, \qquad x_1 = u,\ x_n = v,$$

listing all $n$ vertices.

Define two index sets inside $\{1, 2, \dots, n-1\}$:

$$S = \{\, i : u \sim x_{i+1}\,\}, \qquad T = \{\, i : v \sim x_i \,\}.$$

Here $|S| = \deg(u)$ (each neighbour $x_{i+1}$ of $u=x_1$ contributes the index $i$) and $|T| = \deg(v)$ (each neighbour $x_i$ of $v = x_n$ contributes $i$).

Claim: $S$ and $T$ are disjoint. Suppose some $i \in S \cap T$, so $u \sim x_{i+1}$ and $v \sim x_i$. Then

$$x_1\, x_2 \cdots x_i\ \underbrace{x_n\, x_{n-1} \cdots x_{i+1}}_{\text{reversed}}\ x_1$$

is a cycle: $x_i \sim x_n$ ($=v \sim x_i$), the middle is the path reversed, and $x_{i+1} \sim x_1$ ($= u \sim x_{i+1}$). It visits every vertex exactly once — a Hamiltonian cycle in $G$, contradicting that $G$ is non-Hamiltonian. So $S \cap T = \varnothing$.

Both $S$ and $T$ are subsets of the $(n-1)$-element set $\{1, \dots, n-1\}$ and are disjoint, so

$$\deg(u) + \deg(v) = |S| + |T| = |S \cup T| \le n - 1 < n,$$

contradicting Ore’s condition for the non-adjacent pair $u, v$. This contradiction proves the theorem. $\blacksquare$

Common pitfall (sufficient, not necessary). Dirac’s and Ore’s conditions can fail on graphs that are Hamiltonian. The cycle $C_n$ (for large $n$) is Hamiltonian by definition, yet every vertex has degree $2 < n/2$, so Dirac’s hypothesis fails badly. Never conclude “not Hamiltonian” from the failure of Dirac/Ore.

Necessary conditions (easy direction). A Hamiltonian graph is connected and has minimum degree $\ge 2$ (a Hamiltonian cycle enters and leaves every vertex). Hence no tree with $\ge 3$ vertices is Hamiltonian — trees have leaves. Deleting any $k$ vertices from a Hamiltonian graph leaves at most $k$ components (toughness); this rules out many graphs but is still far from sufficient.

Example. $K_n$ ($n \ge 3$) is Hamiltonian — list the vertices in any order and close the loop; Dirac holds since $\deg = n - 1 \ge n/2$. Every cycle $C_n$ is trivially Hamiltonian. But the Petersen graph (cubic, $10$ vertices) has a Hamiltonian path yet no Hamiltonian cycle — a famous demonstration that regularity and high symmetry are not enough.

12.13 Euler versus Hamilton: a side-by-side #