Chapter 15: Fundamentals of Graph Theory

Why do labeled trees have such a simple counting formula?

Graph theory and combinatorics are taught together because a graph is fundamentally a combinatorial structure. Combinatorics is the study of discrete structures, counting, and arrangements, while graph theory studies relationships between discrete pairs of objects.

Suppose four named devices must be connected by an undirected network that has a route between every pair and contains no redundant cycles. Which links can we choose, and how many different networks are possible? If every pair of devices can be linked, there are $16$ valid answers. For $n$ named devices, the answer is the remarkably compact $n^{n-2}$.

The labels matter: a network centered at device $1$ differs structural-wise from one centered at device $2$. Restrictions on available links also matter: the formula counts trees in the complete graph $K_n$, not spanning trees in arbitrary restricted networks. We will explain this count by encoding a tree as a sequence, then connect tree counting to degree constraints, connectivity, colorings, and deletion–contraction.

This chapter develops the graph theory needed for combinatorial proofs and enumeration. Review Combinatorial Thinking, Induction and Recursive Reasoning, and Matchings. Linear algebra is needed only for the optional matrix-tree section. For a dedicated structural treatment, use Carnegie Mellon's Graph Theory course notes; for graph representations and full algorithm implementations, use Princeton's graph algorithms materials. math.cmu.edu

15.1 Graphs, subgraphs, degree sequences

Concept & Definition. Unless stated otherwise, a graph is finite, undirected, and simple: $G=(V,E)$, where $V$ is a vertex set and $E$ is a set of unordered pairs of distinct vertices. There are no self-loops (edges from a vertex to itself) or parallel edges (multiple edges joining the same pair). Write $n=|V|$ for the number of vertices and $m=|E|$ for the number of edges. Vertices joined by an edge are adjacent; the degree $d_G(v)$ is the number of edges incident with vertex $v$.

Subgraphs & Containment Types. Subgraphs capture local structural views of a larger network:

• A general subgraph $H=(V',E')$ satisfies $V'\subseteq V$ and $E'\subseteq E$, where all edge endpoints in $E'$ lie in $V'$.
• An induced subgraph $G[S]$, for a subset $S\subseteq V$, keeps $S$ as its vertex set and retains all edges of $G$ whose endpoints both lie in $S$. You cannot cherry-pick edges; if two vertices in $S$ were joined in $G$, their edge must exist in $G[S]$.
• A spanning subgraph keeps all vertices ($V'=V$), while potentially deleting edges ($E'\subseteq E$).

Our primary running example throughout this chapter is a square with one diagonal:

$$ V(G)=\{A,B,C,D\},\qquad E(G)=\{AB,BC,CD,DA,AC\}. $$

Its degrees in order $(A,B,C,D)$ are $(3,2,3,2)$. The induced subgraph $G[\{A,B,C\}]$ is a triangle $K_3$; the spanning subgraph with edges $AB,BC,CD,DA$ is a four-cycle $C_4$. The familiar complete graph $K_n$ contains all $\binom{n}{2}$ possible edges. A complete bipartite graph $K_{a,b}$ consists of two disjoint vertex partitions of sizes $a$ and $b$, containing all $ab$ possible cross-edges and no internal edges.

Handshake Lemma (Double Counting Fundamentals). Counting vertex–edge incidences in two ways yields:

$$ \sum_{v\in V}d_G(v)=2m. $$

Why it works: Every edge has exactly two endpoints, so placing a token at every endpoint-edge incidence puts two tokens on every edge. Consequently, the sum of all degrees is always an even number. A fundamental corollary is that the number of vertices of odd degree in any graph is always even. In our running example, $d(A)+d(B)+d(C)+d(D) = 3+2+3+2 = 10 = 2(5)$, confirming $m=5$.

Degree Sequences & Havel–Hakimi Theorem. A degree sequence lists the vertex degrees of a graph, typically in nonincreasing order $(d_1, d_2, \ldots, d_n)$. A sequence is graphical if there exists a simple graph realizing those exact degrees.

Necessary conditions for a sequence to be graphical are: $0\le d_i\le n-1$ and an even sum. However, these are not sufficient. For instance, $(3,3,1,1)$ has an even sum ($8$) and respects $d_i \le 3$. But two vertices of degree $3$ in a 4-vertex graph must connect to every other vertex, forcing the remaining two vertices to have degree at least $2$. Thus $(3,3,1,1)$ cannot be realized by any simple graph.

The definitive test for graphical sequences is the Havel–Hakimi reduction algorithm:

Why the reduction is valid. A realization of the reduced sequence extends directly by adding a vertex adjacent to those $d_1$ selected high-degree vertices. For the converse, start with any realization and call its maximum-degree vertex $v$ ($d(v)=d_1$). Suppose a desired high-degree neighbor $a$ is absent while an undesired lower-degree neighbor $b$ is present. Since $d(a)\ge d(b)$ and $b$ meets $v$ while $a$ does not, there must exist a vertex $w\ne v,a,b$ adjacent to $a$ but not $b$. Swapping edges $\{vb, aw\}$ with $\{va, bw\}$ preserves every vertex degree, introduces no loops or parallel edges, and increases the overlap between $v$'s neighbors and the desired high-degree set. Repeating this swap makes all desired adjacencies available; deleting $v$ yields the reduced graphical realization.

Exercise. Is $(2,2,2,2)$ graphical? Is its realization necessarily a tree? Hint: draw a square. Solution: The four-cycle $C_4$ realizes $(2,2,2,2)$, so it is graphical. However, $C_4$ contains a cycle, so it is not a tree. Degree constraints alone do not establish acyclicity.

15.2 Trees, spanning trees, Cayley's formula

Fundamentals & Definitions.

• A path is a sequence of distinct connected vertices.
• A graph is connected if a path exists between every pair of vertices.
• A cycle is a closed path with at least three distinct vertices.
• A tree is a connected graph containing no cycles. A forest is an acyclic graph (a disjoint union of trees).
• A leaf is a vertex of degree $1$. Every tree on $n \ge 2$ vertices has at least two leaves.

Key Structural Theorem: A tree on $n$ vertices has exactly $n-1$ edges. Proof by Leaf Induction: Find a longest path in $T$; its endpoint $v$ must be a leaf (otherwise the path could be extended, or an extra edge would close a cycle). Removing leaf $v$ and its incident edge yields a smaller tree $T'$ on $n-1$ vertices. By induction, $T'$ has $n-2$ edges, so $T$ has $(n-2) + 1 = n-1$ edges.

Summing over components, a forest with $n$ vertices and $c$ components has $n-c$ edges. A connected graph contains a spanning tree: repeatedly delete edges from cycles until no cycle remains while preserving connectivity. Consequently, any connected graph on $n$ vertices with exactly $n-1$ edges is a tree.

Cayley's Formula. For $n\ge2$, the number of distinct labeled trees on the set $[n]=\{1,2,\ldots,n\}$ is:

$$ n^{n-2}. $$

Proof via Prüfer Sequences (Encoding & Decoding Bijection). Heinz Prüfer established a 1-to-1 correspondence between labeled trees on $[n]$ and sequences of length $n-2$ with entries from $[n]$.

Degree–Occurrence Invariant: In a Prüfer code, vertex $i$ appears exactly $d_i - 1$ times, where $d_i$ is its degree in the tree. This immediate consequence refines Cayley's count for prescribed positive degree vectors $(d_1, \ldots, d_n)$ via multinomial coefficients:

$$ \frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}. $$

15.3 Connectivity, Eulerian and Hamiltonian structures

Route Hierarchy & Fundamentals.

• A walk is an alternating sequence of vertices and edges $v_0, e_1, v_1, e_2, \ldots, v_k$ (repeating vertices and edges allowed).
• A trail is a walk with no repeated edges.
• A path is a walk with no repeated vertices (and thus no repeated edges).
• A component is a maximal connected subgraph.
• A bridge is an edge whose deletion increases the component count. An edge is a bridge if and only if it lies on no cycle.
• A cut vertex is a vertex whose deletion increases the component count.

Eulerian Structures (Traversing Every Edge). An Euler circuit is a closed trail using every edge of $G$ exactly once.

• Theorem (Euler, 1736): A connected graph contains an Euler circuit if and only if every vertex has an even degree.
• A connected graph contains an open Euler trail (starting and ending at distinct vertices) if and only if exactly two vertices have odd degree (which serve as the start and end points).

Hamiltonian Structures (Visiting Every Vertex). A Hamiltonian cycle is a closed path visiting every vertex of $G$ exactly once before returning to the start.

• Unlike Eulerian circuits (which depend locally on degree parity), determining whether a graph contains a Hamiltonian cycle is NP-complete.
• Necessary conditions: A Hamiltonian simple graph on $n \ge 3$ vertices must have minimum degree $\delta(G) \ge 2$ and can contain no cut vertices.

Exercise. Classify the star $K_{1,3}$: connected, Euler circuit, open Euler trail, Hamiltonian cycle? Hint: its degrees are $3,1,1,1$. Answer: Connected, but none of the three requested tours exists. Four odd-degree vertices rule out both Eulerian tours; degree-$1$ leaf vertices rule out a Hamiltonian cycle.

15.4 Planar graphs and Euler's formula

Concept & Definitions. A graph is planar if it can be drawn in the two-dimensional plane such that no two edges cross each other. A plane graph is a specific planar embedding of such a graph. Drawing a plane graph partitions the plane into contiguous geometric regions called faces, including one infinite unbounded outer face.

Euler's Formula for Planar Graphs. For any connected plane graph with $n$ vertices, $m$ edges, and $f$ faces:

$$ n - m + f = 2. $$

Proof Mechanism by Edge Restoration: Begin with a spanning tree of the plane graph. It has $n$ vertices, $n-1$ edges, and exactly $1$ face (the exterior region). Checking Euler's formula gives $n - (n-1) + 1 = 2$. Now restore the remaining $m - (n-1)$ non-tree edges one by one in their plane positions. Each added edge connects two vertices within an existing face, splitting that face into two independent regions. Thus, each edge restoration increases both $m$ and $f$ by $1$, leaving $n - m + f = 2$ invariant.

Planar Edge Bounds. Summing boundary lengths across all face walks yields $\sum \text{len}(F_i) = 2m$. In a simple connected planar graph with $n \ge 3$, every face boundary requires at least $3$ edges, so $3f \le 2m$. Substituting $f \le \frac{2}{3}m$ into Euler's formula yields the maximum edge bound:

$$ m \le 3n - 6. $$

If $G$ is also triangle-free (no $C_3$, such as bipartite graphs), every face boundary requires at least $4$ edges ($4f \le 2m$), giving the tighter bound:

$$ m \le 2n - 4. $$

15.5 Graph coloring and chromatic polynomials

Concept & Fundamentals. A proper vertex coloring assigns a color to each vertex such that no two adjacent vertices share the same color. The chromatic number $\chi(G)$ is the minimum number of colors required to properly color $G$. The chromatic polynomial $P_G(q)$ is a counting function that outputs the exact number of proper vertex colorings of $G$ using a palette of $q$ available colors.

Deletion–Contraction Recurrence for Colorings. For any edge $e = uv$ in $G$:

$$ P_G(q) = P_{G-e}(q) - P_{G/e}(q). $$

Why the minus sign? Consider proper $q$-colorings of $G-e$ (where constraint edge $e$ is removed). In $G-e$, endpoints $u$ and $v$ can either receive different colors or the same color:

• Colorings of $G-e$ where $c(u) \ne c(v)$ are valid proper colorings of $G$.
• Colorings of $G-e$ where $c(u) = c(v)$ correspond to proper colorings of contracted graph $G/e$ (where $u$ and $v$ are merged).

Thus, $P_{G-e}(q) = P_G(q) + P_{G/e}(q)$, which rearranging yields $P_G(q) = P_{G-e}(q) - P_{G/e}(q)$.

Worked Example (Square + Diagonal Graph). In $G$, color non-adjacent vertices $A,C$ first in $q(q-1)$ ways (forcing $c(A) \ne c(C)$). Vertices $B$ and $D$ are each adjacent to both $A$ and $C$, so each must choose from the remaining $q-2$ available colors. Thus:

$$ P_G(q) = q(q-1)(q-2)^2. $$

For $q=3$ colors, $P_G(3) = 3(2)(1)^2 = 6$ proper three-colorings exist, confirming $\chi(G)=3$.

15.6 Matrix-tree theorem

Optional Extension: Algebraic Enumeration. For a loopless multigraph $G$ with adjacency matrix $A$ and diagonal degree matrix $D = \mathrm{diag}(d(v_1), \ldots, d(v_n))$, the Graph Laplacian Matrix is defined as:

$$ L = D - A. $$

Properties of $L$: Diagonal entries $L_{ii} = d(v_i)$; off-diagonal entries $L_{ij} = -m_{ij}$ (where $m_{ij}$ is the number of edges between $v_i$ and $v_j$). Every row and column sum of $L$ is identically $0$.

Matrix-Tree Theorem (Kirchhoff, 1847). Delete any arbitrary row $r$ and column $r$ from $L$ to obtain reduced matrix $L^{(r)}$. The number of spanning trees $\tau(G)$ is given by:

$$ \tau(G) = \det L^{(r)}. $$

15.7 Menger's theorem and connectivity dualities

Concept & Duality. Connectivity evaluates network robustness. For non-adjacent target vertices $s$ and $t$:

• An $s$–$t$ vertex separator $S \subseteq V \setminus \{s,t\}$ is a set of vertices whose deletion disconnects $s$ and $t$.
• Paths are internally vertex-disjoint if they share no common vertices other than $s$ and $t$.

Menger's Theorem (Vertex Form). For non-adjacent vertices $s, t$:

$$ \max \{\text{internally vertex-disjoint } s\text{–}t \text{ paths}\} = \min \{|S| : S \text{ separates } s, t\}. $$

Global Connectivity Hierarchy. For connected simple graphs with $n \ge 2$:

$$ \kappa(G) \le \lambda(G) \le \delta(G), $$

where $\kappa(G)$ is vertex connectivity, $\lambda(G)$ is edge connectivity, and $\delta(G)$ is minimum degree.

15.8 Tutte polynomials and deletion–contraction

Optional Extension: The Master Unifying Invariant. For a multigraph $G=(V,E)$ and edge subset $A \subseteq E$, let $c(A)$ denote the number of connected components of spanning subgraph $(V,A)$. Define the rank function $r(A) = n - c(A)$.

The Tutte polynomial $T_G(x,y)$ is defined as:

$$ T_G(x,y)=\sum_{A\subseteq E} (x-1)^{r(E)-r(A)}(y-1)^{|A|-r(A)}. $$

Its deletion–contraction recurrence rules are:

$$ T_G(x,y)=\begin{cases} T_{G-e}(x,y)+T_{G/e}(x,y),& e \text{ is an ordinary edge (neither loop nor bridge)},\\ x T_{G/e}(x,y),& e \text{ is a bridge},\\ y T_{G-e}(x,y),& e \text{ is a loop}. \end{cases} $$

Universal Specializations:

• $T_G(1,1) = \tau(G)$ (Number of Spanning Trees).
• $T_G(2,1) = 2^{|E|-n+c}$ (Number of Spanning Subgraphs).
• Chromatic Polynomial: $P_G(q) = (-1)^{r(E)} q^{c(E)} T_G(1-q, 0)$.

15.9 Graph minors and forbidden-subgraph characterizations

Optional Extension: Structural Containment Hierarchy.

Classical Planarity Characterizations:

• Kuratowski's Theorem (1930): A finite graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or $K_{3,3}$.
• Wagner's Theorem (1937): A finite graph is planar if and only if it contains neither $K_5$ nor $K_{3,3}$ as a minor.

Robertson–Seymour Graph Minor Theorem (2004): In any infinite sequence of finite undirected graphs, some graph is a minor of a later one. Consequently, every minor-closed property of finite graphs is characterizable by a finite set of forbidden minors.

Compare tree counts, colorings, and deletion–contraction recurrences

Return to running graph $G$ ($V=\{A,B,C,D\}$, $E=\{AB,BC,CD,DA,AC\}$). Spanning trees count connected backbone topologies under addition, whereas proper colorings count conflict-free state assignments under subtraction.