Contents / Discrete Mathematics / Graph Theory

Chapter 5

Graph Theory

Graphs, degrees and the handshake lemma by double counting; edge bounds forcing connectivity; walks, paths and cycles; four characterisations of a tree proved in a cycle of implications; bipartite graphs characterised by the absence of odd cycles; and Euler's theorem in both directions, with the Konigsberg bridges as a corollary.

Introduction

Almost everything a computer scientist works with is a network of things joined to other things. A social platform stores who follows whom. A build system stores which source file must be compiled before which other. A router stores which machines it can reach in one hop. A course catalogue stores which module is a prerequisite for which. These look like four different problems, and they are not: strip away the words and each is a set of objects together with a set of pairs of objects, which is exactly what a graph is.

The payoff of that abstraction is that a theorem proved about graphs is a theorem about all four systems at once. When we prove below that a graph can be traversed in one closed stroke exactly when every vertex has even degree, we have simultaneously decided a puzzle about the bridges of eighteenth-century Königsberg, a question about whether a plotter can draw a figure without lifting the pen, and a question about whether a street-sweeping route can avoid repeating a street. The theorem does not know or care which of these it is being applied to.

This chapter builds the vocabulary from nothing and then proves the first real theorems of the subject. The single most important is the handshake lemma, which says the degrees of a graph sum to twice the number of edges; almost every counting argument here descends from it. After that we look at three families that carry most of the applications: trees, which are exactly the minimally connected graphs and which underlie file systems, parse trees and spanning-tree protocols; bipartite graphs, which are exactly the graphs with no odd cycle and which model every two-sided matching problem; and Eulerian graphs, where Euler's theorem gives a complete, checkable characterisation of a property that looks as though it should require searching.

That last point deserves emphasis up front. Euler's theorem is remarkable not because closed traversals are intrinsically interesting but because it replaces a search over exponentially many routes with a scan over $n$ degree counts. The chapter ends by putting the neighbouring Hamiltonian question beside it — visit every vertex once rather than every edge — where no such characterisation is known and, as far as anyone can prove, none exists in any usable form.

Throughout, $G = (V, E)$ denotes a finite graph, $n = ∣ V ∣$ and $m = ∣ E ∣$ . Deeper material — colouring beyond two colours, planarity, matchings, Ramsey theory, network flow — belongs to the chapters Graph Combinatorics and Combinatorial Optimization in the Combinatorics subject, and is pointed at rather than developed here.

5.1Graphs: the objects and their pictures

A graph is a set together with a set of pairs drawn from it. The definition is so light that the hard work is entirely in what one deduces from it, which is a good sign: a definition carrying many clauses usually hides a theorem that should have been proved.

Definition 5.1 (Graph). A graph is an ordered pair $G = (V, E)$ where $V$ is a finite non-empty set whose elements are called vertices, and $E$ is a set of unordered pairs ${u, v}$ of vertices, called edges. We write $uv$ for the edge ${u, v}$ , and we set

n = ∣ V ∣, m = ∣ E ∣.

Because an edge is an unordered pair, $uv$ and $vu$ are the same edge: there is no first endpoint. If $uv \in E$ we say $u$ and $v$ are adjacent or neighbours, and that the edge $uv$ is incident with each of $u$ and $v$ .

Definition 5.2 (Simple graph, multigraph, digraph). A loop is an edge joining a vertex to itself; a multi-edge is a repeated edge between the same pair. A graph with neither is simple. A multigraph permits loops and multi-edges, so its edges form a multiset. A directed graph or digraph replaces unordered pairs by ordered pairs $(u, v)$ , called arcs, so direction matters and $(u, v) \neq = (v, u)$ .

Unless stated otherwise, graph means simple graph in what follows. The one place we deliberately step outside that convention is Königsberg, which is genuinely a multigraph — two of its bridges join the same pair of land masses — and Euler's theorem is stated so that it covers that case.

Intuition. A digraph is a one-way street network, an undirected graph a two-way one. A multigraph is a road map that records two separate bridges over the same river as two separate roads, because a traveller can drive across either. Which model you pick is a modelling decision, not a mathematical one: choose the one whose edges are the things you actually want to count.

A graph is a combinatorial object and not a picture, but pictures are how anyone thinks about them. A drawing places the vertices as dots anywhere in the plane and each edge as any curve joining its two endpoints. Nothing in the definition constrains a drawing, so a single graph has infinitely many of them, some clear and some unreadable, and two drawings that look nothing alike may be drawings of the same graph.

Definition 5.3 (Isomorphism). Two graphs $G = (V, E)$ and $H = (W, F)$ are isomorphic, written $G ≅ H$ , if there is a bijection $φ : V \to W$ such that for all $u, v \in V$ ,

uv \in E ⟺ φ (u) φ (v) \in F .

Such a $φ$ is an isomorphism: it renames the vertices and preserves exactly which pairs are joined.

Isomorphic graphs are the same graph wearing different labels, and every property in this chapter — degrees, connectedness, being a tree, being Eulerian — is preserved by isomorphism. That gives a practical test for showing two graphs are not isomorphic: find any such property they disagree on. Showing they are isomorphic needs an explicit bijection, and the general problem of deciding isomorphism has no known efficient algorithm, which is a recurring theme of this chapter.

Definition 5.4 (Subgraph). A graph $H = (W, F)$ is a subgraph of $G = (V, E)$ if $W \subseteq V$ and $F \subseteq E$ , and every edge of $F$ has both endpoints in $W$ . If $F$ contains every edge of $E$ with both endpoints in $W$ , then $H$ is the subgraph induced by $W$ , written $G [W]$ .

Two ways to store a graph dominate in practice, and the choice between them is the first algorithmic consequence of the definition.

Definition 5.5 (Adjacency matrix and adjacency list). Order the vertices $v_{1}, \dots, v_{n}$ . The adjacency matrix of $G$ is the $n \times n$ matrix $A$ with

A_{ij} = {10 if v_{i} v_{j} \in E, otherwise.

The adjacency list representation stores, for each vertex, the list of its neighbours.

Proposition 5.6 (Shape of the adjacency matrix). The adjacency matrix of a simple graph is symmetric, has zero diagonal, and its entries sum to $2 m$ .

Proof. Symmetry is the statement that $v_{i} v_{j} \in E$ if and only if $v_{j} v_{i} \in E$ , which holds because an edge is an unordered pair. The diagonal entry $A_{ii}$ records whether $v_{i} v_{i} \in E$ , that is, whether there is a loop at $v_{i}$ ; a simple graph has none, so $A_{ii} = 0$ .

For the sum, each edge $v_{i} v_{j}$ with $i \neq = j$ contributes exactly the two entries $A_{ij} = A_{ji} = 1$ , and every entry equal to $1$ arises from exactly one edge in this way. Hence the total is $2 m$ .∎

The two representations trade space against query time. An adjacency matrix answers "is $uv$ an edge?" in constant time but always occupies $n^{2}$ bits, which is wasteful for the sparse graphs that occur in practice — a road network has vertices of bounded degree, so $m$ grows like $n$ , not like $n^{2}$ . An adjacency list occupies space proportional to $n + m$ and lets an algorithm sweep the neighbours of a vertex in time proportional to that vertex's degree, which is what breadth-first and depth-first search need. Almost every graph algorithm in a first course assumes lists.

Example 5.7 (Reading a graph off a description). Let $V = {1, 2, 3, 4, 5}$ and let $E$ consist of all pairs ${i, j}$ with $i \neq = j$ and $i + j$ even. List the edges, give the adjacency matrix, and say whether the graph is connected in the informal sense of "you can walk from any vertex to any other".

Solution.

$i + j$ is even exactly when $i$ and $j$ have the same parity. The odd vertices are $1, 3, 5$ and the even ones are $2, 4$ .
So the edges are all pairs inside ${1, 3, 5}$ — namely $13$ , $15$ , $35$ — and all pairs inside ${2, 4}$ — namely $24$ . That is $m = 4$ edges.
Ordering the vertices $1, 2, 3, 4, 5$ , the adjacency matrix is

A = 0010100010100010100010100 .

There is no edge between an odd and an even vertex, so no walk can ever cross from ${1, 3, 5}$ to ${2, 4}$ . The graph is not connected: it falls into two pieces.

□

Proposition 5.8 (How many graphs there are). The number of distinct simple graphs on a fixed labelled vertex set of size $n$ is

2^{(2 n)} .

Proof. A simple graph on the set $V$ is determined by its edge set, which is an arbitrary subset of the set $P$ of all unordered pairs of distinct vertices. Distinct subsets give distinct graphs, and every subset gives a graph, so the graphs correspond bijectively to the subsets of $P$ .

There are $(2 n)$ such pairs, since a pair is a choice of $2$ elements from $n$ with order irrelevant, and a set of size $k$ has $2^{k}$ subsets. Hence the count is $2^{(2 n)}$ .∎

The growth here is worth pausing on: on $10$ labelled vertices there are $2^{45}$ graphs, about $3.5 \times 1 0^{13}$ . Any approach to a graph problem that inspects all graphs of a given size is dead on arrival, which is why the subject proves theorems instead.

Example 5.9 (Counting labelled graphs and subgraphs). How many simple graphs are there on the labelled vertex set ${a, b, c, d}$ ? Of these, how many contain the edge $ab$ ?

Solution.

There are $(2 4) = 6$ possible edges, so by the proposition How many graphs there are the total is $2^{6} = 64$ .
Fixing $ab$ to be present leaves the remaining $5$ pairs free, giving $2^{5} = 32$ .
As a check, exactly half of all graphs contain any fixed edge, by the symmetry that toggles that one edge; $64/2 = 32$ .

□

Pitfall. "Labelled" matters. The $64$ graphs on ${a, b, c, d}$ collapse to only $11$ once isomorphic graphs are identified, because many relabellings give the same picture. Counting graphs up to isomorphism is much harder and is taken up in Graph Combinatorics; every count in this chapter is a labelled count unless it explicitly says otherwise.

Exercises for §5.1 →

5.2Degrees, the handshake lemma and edge counts

The degree of a vertex is the single most useful local statistic a graph has, and the first theorem of graph theory says that the local degrees and the global edge count determine each other.

Definition 5.10 (Degree). The degree $de g (v)$ of a vertex $v$ in a simple graph is the number of edges incident with $v$ , equivalently the number of its neighbours. A vertex of degree $0$ is isolated and a vertex of degree $1$ is a leaf. We write

δ (G) = v \in V min de g (v), Δ (G) = v \in V max de g (v)

for the minimum and maximum degree. In a multigraph a loop at $v$ contributes $2$ to $de g (v)$ , since it meets $v$ at both ends.

Theorem 5.11 (Handshake lemma). For every graph $G = (V, E)$ ,

v \in V \sum de g (v) = 2 m .

Proof. Count the set $I$ of incidences, that is, the set of pairs $(v, e)$ where $v$ is a vertex, $e$ is an edge, and $v$ is an endpoint of $e$ . We count $∣ I ∣$ in two ways.

Group the incidences by their vertex. The pairs with first coordinate $v$ are exactly the edges incident with $v$ , and there are $de g (v)$ of these, by the definition of degree. Summing over $v$ gives

∣ I ∣ = v \in V \sum de g (v) .

Now group the incidences by their edge. Each edge $e = uv$ has exactly two endpoints, so it occurs in exactly two pairs, namely $(u, e)$ and $(v, e)$ . Summing over $e$ gives $∣ I ∣ = 2 m$ .

The two counts are of the same set, so they are equal. (In a multigraph the second count still gives $2$ per edge, because a loop at $v$ contributes the two incidences of its two ends, which is precisely why a loop is defined to add $2$ to the degree.)∎

Intuition. At a party, shake hands and count. Each person reports how many hands they shook; add the reports. Every handshake involves two people, so every handshake was reported exactly twice, and the total of the reports is twice the number of handshakes. That is the whole proof, and it is why the result is named as it is.

The technique in that proof — count one set two different ways and equate — is called double counting, and it is the workhorse of the subject. Notice that it never constructs anything: no graph is built, no case is checked, and the conclusion holds for all graphs simultaneously.

Corollary 5.12 (The number of odd vertices is even). In every graph, the number of vertices of odd degree is even.

Proof. Split the sum in the theorem Handshake lemma according to the parity of the degree. Writing $V_{odd}$ and $V_{even}$ for the sets of vertices of odd and even degree,

v \in V_{odd} \sum de g (v) + v \in V_{even} \sum de g (v) = 2 m .

The right-hand side is even, and the second sum on the left is a sum of even numbers and hence even. Therefore the first sum is even too.

But that first sum is a sum of $∣ V_{odd} ∣$ odd numbers, and a sum of odd numbers is even exactly when there is an even number of them. Hence $∣ V_{odd} ∣$ is even.∎

Example 5.13 (Does such a graph exist?). Is there a simple graph with degree sequence $3, 3, 3, 3, 3$ ? What about $4, 3, 3, 2, 2$ ?

Solution.

For the first, the degrees sum to $15$ , which is odd, contradicting the theorem Handshake lemma since $2 m$ is even. Equivalently, there would be five vertices of odd degree, and five is odd, contradicting the corollary The number of odd vertices is even. No such graph exists.
For the second, the degrees sum to $14$ , so any such graph has $m = 7$ edges — the parity test is passed and gives no obstruction.
Passing the test is not a construction, so we produce one. On vertices $a, b, c, d, e$ take the edges $ab, a c, a d, a e, b c, b d, ce$ . Then $de g (a) = 4$ , $de g (b) = 3$ , $de g (c) = 3$ , $de g (d) = 2$ , $de g (e) = 2$ , and there are $7$ edges, as predicted.

□

Pitfall. The handshake lemma is a necessary condition, never a sufficient one. An even degree sum does not guarantee a graph exists: the sequence $4, 1, 1, 1, 1$ sums to $8$ , but a vertex of degree $4$ needs four distinct neighbours among four vertices of degree $1$ , which forces every other degree to be exactly $1$ and uses up all four — that one happens to work. The sequence $4, 4, 1, 1, 1, 1$ does not: each degree- $4$ vertex must be adjacent to the other, leaving each needing three of the four leaves, which is nine leaf-endpoints among four leaves. Deciding which sequences occur is the Erdős–Gallai problem, treated in Graph Combinatorics.

Definition 5.14 (Complete graph, complement, regular graph). The complete graph $K_{n}$ has $n$ vertices with every pair joined. The complement $\overline{G}$ of a simple graph $G$ has the same vertices, with $uv$ an edge of $\overline{G}$ exactly when $u \neq = v$ and $uv \in / E$ . A graph is $r$ -regular if every vertex has degree $r$ .

Proposition 5.15 (Maximum number of edges). A simple graph on $n$ vertices has at most

(2 n) = \frac{n ( n - 1 )}{2}

edges, with equality exactly for $K_{n}$ .

Proof. Every edge is an unordered pair of distinct vertices, and in a simple graph no such pair occurs twice. So $E$ is a subset of the set of all $(2 n)$ unordered pairs of distinct vertices, whence $m \leq (2 n)$ .

Equality holds exactly when $E$ is the whole set of pairs, which is the definition of $K_{n}$ .

For the closed form, count ordered pairs of distinct vertices: there are $n$ choices of first and $n - 1$ of second, giving $n (n - 1)$ , and each unordered pair is counted twice.∎

Corollary 5.16 (Degrees in a complete graph). Every vertex of $K_{n}$ has degree $n - 1$ , and $K_{n}$ has $\frac{n ( n - 1 )}{2}$ edges.

Proof. A vertex of $K_{n}$ is joined to every vertex other than itself, so it has $n - 1$ neighbours. Summing over the $n$ vertices and applying the theorem Handshake lemma, $n (n - 1) = 2 m$ , so $m = n (n - 1) /2$ , agreeing with the proposition Maximum number of edges.∎

Proposition 5.17 (Edge count of a regular graph). An $r$ -regular graph on $n$ vertices has $m = \frac{n r}{2}$ edges. Consequently $n r$ is even, so no $r$ -regular graph exists when $n$ and $r$ are both odd.

Proof. Every one of the $n$ vertices has degree $r$ , so the degree sum is $n r$ . By the theorem Handshake lemma this equals $2 m$ , giving $m = n r /2$ .

Since $m$ is an integer, $n r$ must be even. If $n$ and $r$ are both odd then $n r$ is odd, which is impossible; hence no such graph exists.∎

Example 5.18 (A 3-regular graph on 7 vertices). Does a $3$ -regular graph on $7$ vertices exist? On $8$ ?

Solution.

For $n = 7$ , $r = 3$ : both are odd, so by the proposition Edge count of a regular graph no such graph exists.
For $n = 8$ , $r = 3$ : $n r = 24$ is even, so the obstruction vanishes and $m$ would be $12$ .
And such a graph does exist — take the cube graph $Q_{3}$ , whose vertices are the eight binary strings of length $3$ with an edge whenever two strings differ in exactly one position. Each string has three positions to flip, so every degree is $3$ .

□

Figure 5.19.

K_{5}

: every pair of the five vertices is joined, so all ten edges are drawn and every vertex has degree

4

The picture makes a point the algebra does not. $K_{5}$ has only five vertices but ten edges, and every drawing of it in the plane has at least one crossing — it is the smallest non-planar graph together with $K_{3, 3}$ , a fact proved in Graph Combinatorics. Density of edges is what makes drawings unreadable, and it is why real network diagrams are almost always sparse.

Proposition 5.20 (Two vertices of equal degree). Every simple graph with at least two vertices has two distinct vertices of the same degree.

Proof. Let $G$ have $n \geq 2$ vertices. Each degree lies in ${0, 1, \dots, n - 1}$ , a set of $n$ possible values, and there are $n$ vertices, so the pigeonhole principle does not immediately apply. We rule out one value.

Suppose some vertex has degree $0$ and some vertex has degree $n - 1$ . The second is adjacent to every other vertex, including the first, so the first has degree at least $1$ — a contradiction. Hence at most one of the values $0$ and $n - 1$ is attained.

So all $n$ degrees lie in a set of at most $n - 1$ values. By the pigeonhole principle two vertices share a value.∎

Example 5.21 (Degrees in a complement). A simple graph $G$ on $9$ vertices has $12$ edges. How many edges does $\overline{G}$ have, and what is $de g_{\overline{G}} (v)$ if $de g_{G} (v) = 5$ ?

Solution.

Every pair of distinct vertices is an edge of exactly one of $G$ and $\overline{G}$ , so the edge counts sum to $(2 9) = 36$ by the proposition Maximum number of edges.
Hence $\overline{G}$ has $36 - 12 = 24$ edges.
Similarly the neighbours of $v$ in $G$ and in $\overline{G}$ partition the other $8$ vertices, so $de g_{\overline{G}} (v) = 8 - 5 = 3$ .

□

Exercises for §5.2 →

5.3Walks, paths, cycles and connectivity

Everything about routing, reachability and search is a statement about the ways one can travel along edges. The definitions below distinguish four levels of strictness, and confusing them is the commonest source of a wrong proof in a first course.

Definition 5.22 (Walk, trail, path, cycle). A walk from $u$ to $v$ in $G$ is a finite sequence of vertices

u = w_{0}, w_{1}, \dots, w_{k} = v

in which $w_{i - 1} w_{i} \in E$ for each $i$ . Its length is $k$ , the number of edge steps. A walk is

a trail if no edge is repeated,
a path if no vertex is repeated,
closed if $w_{0} = w_{k}$ and $k \geq 1$ .

A cycle is a closed walk $w_{0}, w_{1}, \dots, w_{k} = w_{0}$ with $k \geq 3$ in which $w_{0}, \dots, w_{k - 1}$ are distinct. A cycle of length $k$ is a $k$ -cycle, written $C_{k}$ ; it is odd or even according to the parity of $k$ .

A path never repeats a vertex, and therefore never repeats an edge, so every path is a trail and every trail is a walk; the converses fail. In a simple graph, a closed walk of length $1$ would be a loop and of length $2$ would retrace a single edge, which is why cycles are required to have length at least $3$ .

Intuition. A walk is a route you actually took, wandering allowed. A trail never drives down the same street twice but may pass through a junction twice. A path never even revisits a junction. Eulerian questions, later, are about trails; Hamiltonian questions are about paths.

Definition 5.23 (Connectedness and components). Vertices $u$ and $v$ are connected if there is a walk from $u$ to $v$ . The graph $G$ is connected if every pair of its vertices is connected, and disconnected otherwise. A connected component of $G$ is a maximal connected subgraph: a set of vertices any two of which are connected, which cannot be enlarged.

Proposition 5.24 (Components partition the vertices). The relation " $u$ is connected to $v$ " is an equivalence relation on $V$ , so its classes partition $V$ into the connected components.

Proof. Reflexive: the one-term sequence $u$ is a walk from $u$ to $u$ of length $0$ .

Symmetric: if $u = w_{0}, \dots, w_{k} = v$ is a walk, then reading it backwards, $v = w_{k}, \dots, w_{0} = u$ , is also a walk, because each required adjacency $w_{i} w_{i - 1} \in E$ is the same unordered pair as $w_{i - 1} w_{i}$ .

Transitive: given a walk from $u$ to $v$ and a walk from $v$ to $x$ , concatenate them at $v$ . Every consecutive pair in the concatenation is a consecutive pair of one of the two original walks, so every required adjacency holds, and the result is a walk from $u$ to $x$ .

An equivalence relation partitions its underlying set into classes, and the class of $u$ is precisely the set of vertices reachable from $u$ , which is the vertex set of the component containing $u$ .∎

Symmetry is exactly where undirectedness is used; in a digraph the analogous relation is not symmetric, and the correct notion splits into strong and weak connectivity. Everything below assumes undirected graphs.

Lemma 5.25 (Every walk contains a path). If there is a walk from $u$ to $v$ in $G$ , then there is a path from $u$ to $v$ in $G$ .

Proof. Among all walks from $u$ to $v$ choose one of minimum length; this is possible because the set of lengths of such walks is a non-empty set of non-negative integers, which has a least element by well-ordering. Write it as $u = w_{0}, w_{1}, \dots, w_{k} = v$ .

We claim this walk is a path. Suppose not: then $w_{i} = w_{j}$ for some $i < j$ . Delete the portion strictly between them, forming the shorter sequence

w_{0}, \dots, w_{i}, w_{j + 1}, \dots, w_{k} .

This is still a walk: every consecutive pair other than $(w_{i}, w_{j + 1})$ was consecutive before, and that one is a valid step because $w_{i} = w_{j}$ and $w_{j} w_{j + 1} \in E$ . Its length is $k - (j - i) < k$ , contradicting minimality.

Hence no vertex repeats, and the chosen walk is a path from $u$ to $v$ .∎

This little lemma is used constantly, and it is why the definition of connectedness can be stated with the weak notion — walks — while every proof is free to assume the strong one. It also means a shortest walk between two vertices is automatically a path, which is the correctness statement underlying breadth-first search.

Definition 5.26 (Distance). For connected $u, v$ , the distance $d (u, v)$ is the length of a shortest path from $u$ to $v$ ; if no walk joins them, $d (u, v) = \infty$ . The diameter of a connected graph is $max_{u, v} d (u, v)$ .

Example 5.27 (Distances in a cycle with a chord). Let $G$ be the $6$ -cycle $v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{1}$ together with the extra edge $v_{1} v_{4}$ . Compute $d (v_{1}, v_{4})$ , $d (v_{2}, v_{5})$ and the diameter.

Solution.

$v_{1} v_{4}$ is an edge, so $d (v_{1}, v_{4}) = 1$ .
From $v_{2}$ to $v_{5}$ : the route $v_{2}, v_{1}, v_{4}, v_{5}$ has length $3$ , and so does $v_{2}, v_{3}, v_{4}, v_{5}$ . Could it be $2$ ? That needs a common neighbour of $v_{2}$ and $v_{5}$ ; the neighbours of $v_{2}$ are $v_{1}, v_{3}$ and those of $v_{5}$ are $v_{4}, v_{6}$ , which are disjoint. So $d (v_{2}, v_{5}) = 3$ .
Every other pair is at distance at most $2$ : the chord makes $v_{1}$ and $v_{4}$ adjacent to four vertices between them. Hence the diameter is $3$ , attained by the pair $v_{2}, v_{5}$ (and by $v_{3}, v_{6}$ ).

□

Theorem 5.28 (Powers of the adjacency matrix count walks). Let $A$ be the adjacency matrix of $G$ with respect to the ordering $v_{1}, \dots, v_{n}$ . For every integer $k \geq 0$ , the entry $(A^{k})_{ij}$ is the number of walks of length exactly $k$ from $v_{i}$ to $v_{j}$ .

Proof. Induct on $k$ . For $k = 0$ , $A^{0}$ is the identity, and the only walk of length $0$ from $v_{i}$ is the one-term walk at $v_{i}$ itself, so the count is $1$ when $i = j$ and $0$ otherwise.

Assume the claim for $k$ . A walk of length $k + 1$ from $v_{i}$ to $v_{j}$ consists of a walk of length $k$ from $v_{i}$ to some vertex $v_{ℓ}$ , followed by a single step $v_{ℓ} v_{j}$ . The choices of the initial walk and of the last step are independent, and distinct choices give distinct walks, so the number of walks of length $k + 1$ from $v_{i}$ to $v_{j}$ is

ℓ = 1 \sum n (walks of length k from v_{i} to v_{ℓ}) \cdot A_{ℓ j} = ℓ = 1 \sum n (A^{k})_{i ℓ} A_{ℓ j},

using the inductive hypothesis. The right-hand side is the definition of the matrix product entry $(A^{k + 1})_{ij}$ .∎

Remark. This is why $(A^{3})_{ii}$ divided by $2$ counts the triangles through $v_{i}$ : a closed walk of length $3$ from $v_{i}$ must be a triangle, and each triangle is traversed in two directions. It is also the cheapest available triangle-counting algorithm, at the cost of a matrix multiplication.

Proposition 5.29 (A graph of minimum degree at least two contains a cycle). If $δ (G) \geq 2$ then $G$ contains a cycle.

Proof. Since $G$ is finite it has a path of maximum length; let $P = w_{0}, w_{1}, \dots, w_{k}$ be one, and note $k \geq 1$ because $δ (G) \geq 2 > 0$ forces some edge to exist.

Consider the endpoint $w_{0}$ . It has at least two neighbours. One of them is $w_{1}$ ; let $x$ be another, so $x \neq = w_{1}$ . If $x$ were not on $P$ , then $x, w_{0}, w_{1}, \dots, w_{k}$ would be a longer path, contradicting maximality. Hence $x = w_{i}$ for some $i \geq 2$ .

Then $w_{0}, w_{1}, \dots, w_{i}, w_{0}$ is a closed walk whose vertices $w_{0}, \dots, w_{i}$ are distinct, being vertices of a path, and its length is $i + 1 \geq 3$ . That is a cycle.∎

Theorem 5.30 (An edge bound forcing connectedness). Let $G$ be a simple graph on $n \geq 2$ vertices with

m > \frac{( n - 1 ) ( n - 2 )}{2}

edges. Then $G$ is connected.

Proof. We prove the contrapositive: a disconnected simple graph on $n$ vertices has at most $\frac{( n - 1 ) ( n - 2 )}{2}$ edges.

Suppose $G$ is disconnected. Pick a component and let $H_{1}$ be the subgraph it induces, with $k$ vertices, and let $H_{2}$ be the subgraph induced by the remaining $n - k$ vertices; both are non-empty, so $1 \leq k \leq n - 1$ . No edge joins $H_{1}$ to $H_{2}$ , since such an edge would connect vertices in different components. So every edge lies inside $H_{1}$ or inside $H_{2}$ , and by the proposition Maximum number of edges applied to each,

m \leq (2 k) + (2 n - k) .

It remains to maximise the right-hand side over $1 \leq k \leq n - 1$ . Write $f (k) = (2 k) + (2 n - k)$ and compare $k$ with $k + 1$ for $k < n /2$ :

f (k) - f (k + 1) = [(2 k) - (2 k + 1)] + [(2 n - k) - (2 n - k - 1)] = - k + (n - k - 1) = n - 2 k - 1,

which is positive when $k < (n - 1) /2$ . So $f$ decreases as $k$ moves from $1$ towards the middle, and by the symmetry $f (k) = f (n - k)$ it increases again afterwards. Its maximum over the allowed range is therefore at the ends, $k = 1$ or $k = n - 1$ , where

f (1) = (2 1) + (2 n - 1) = \frac{( n - 1 ) ( n - 2 )}{2} .

Hence $m \leq \frac{( n - 1 ) ( n - 2 )}{2}$ , as required.∎

The bound is sharp, and the extremal example is exactly what the proof points at: take $K_{n - 1}$ together with one isolated vertex. It has $\frac{( n - 1 ) ( n - 2 )}{2}$ edges and is disconnected, so the strict inequality in the hypothesis cannot be weakened.

Example 5.31 (Applying the connectivity bound). A network has $12$ machines and $60$ links, no two machines linked twice. Must it be connected? What if it had $55$ links?

Solution.

Here $n = 12$ , so the threshold is $\frac{11 \cdot 10}{2} = 55$ .
With $m = 60 > 55$ , the theorem An edge bound forcing connectedness applies and the network must be connected.
With $m = 55$ it need not be: $K_{11}$ plus one isolated machine has exactly $(2 11) = 55$ links and is disconnected. So $55$ links guarantee nothing, and the bound cannot be improved.

□

Proposition 5.32 (Minimum degree forces connectedness). If $G$ is a simple graph on $n$ vertices with $δ (G) \geq \frac{n - 1}{2}$ , then $G$ is connected.

Proof. Let $u$ and $v$ be distinct vertices. If they are adjacent, they are connected. Otherwise let $N (u)$ and $N (v)$ be their neighbourhoods; neither contains $u$ or $v$ , so both are subsets of the remaining $n - 2$ vertices.

If $N (u)$ and $N (v)$ were disjoint, then

∣ N (u) ∣ + ∣ N (v) ∣ \leq n - 2.

But $∣ N (u) ∣ + ∣ N (v) ∣ = de g (u) + de g (v) \geq 2 \cdot \frac{n - 1}{2} = n - 1 > n - 2$ , a contradiction.

So there is a common neighbour $w$ , and $u, w, v$ is a walk. Every pair of vertices is connected, so $G$ is connected.∎

Pitfall. A walk from $u$ to $v$ of length $k$ does not mean $d (u, v) = k$ ; it means $d (u, v) \leq k$ . Shortest-path claims need the lemma Every walk contains a path plus an argument that nothing shorter exists — usually by inspecting all common neighbours, as in the example Distances in a cycle with a chord.

Exercises for §5.3 →

5.4Trees

A tree is what is left of a connected graph when every redundancy has been removed. That informal description turns into several precise definitions which look quite different and are nonetheless equivalent, and proving their equivalence is the main business of this section.

Definition 5.33 (Tree, forest, leaf). A graph is acyclic if it contains no cycle. A tree is a connected acyclic graph; a forest is an acyclic graph, that is, a graph each of whose components is a tree. A leaf of a tree is a vertex of degree $1$ .

Figure 5.34. A tree on seven vertices. It has six edges, its three leaves are marked, and between any two vertices there is exactly one path.

Calling one vertex the root is a convenience and not part of the definition: a tree has no distinguished vertex until you choose one, at which point every other vertex acquires a depth and a parent, and the familiar file-system picture appears.

Theorem 5.35 (Characterisations of a tree). Let $G$ be a graph on $n \geq 1$ vertices. The following are equivalent.

$G$ is connected and acyclic, that is, $G$ is a tree.
Between any two vertices of $G$ there is exactly one path.
$G$ is connected and has $n - 1$ edges.
$G$ is acyclic and has $n - 1$ edges.

Proof. We prove $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$ , which establishes all the equivalences by composing implications around the cycle.

$1 \Rightarrow 2$ . Let $u, v$ be vertices. Connectedness gives a walk from $u$ to $v$ , and the lemma Every walk contains a path upgrades it to a path, so at least one path exists. Suppose $P$ and $Q$ were two different paths from $u$ to $v$ . Since they differ, there is a first index $i$ at which they diverge; let $x$ be their last common vertex before diverging. After $x$ the two paths are distinct, and since both end at $v$ they must meet again; let $y$ be the first vertex after $x$ lying on both. The portion of $P$ from $x$ to $y$ and the portion of $Q$ from $x$ to $y$ share only their endpoints, and at least one of them has length at least $2$ since the two differ. Joining them gives a closed walk with no repeated vertex except at its ends and of length at least $3$ — a cycle, contradicting acyclicity. So the path is unique.

$2 \Rightarrow 3$ . Uniqueness implies existence, so $G$ is connected. We prove the edge count by induction on $n$ . For $n = 1$ there are no edges, and $n - 1 = 0$ . Suppose the claim holds for all graphs on fewer than $n$ vertices satisfying (2), and let $G$ satisfy it on $n \geq 2$ vertices. Take any edge $uv$ and delete it, obtaining $G^{'}$ . Then $G^{'}$ has no $u$ – $v$ path: such a path together with the edge $uv$ would give a second $u$ – $v$ path in $G$ , contradicting uniqueness. So $G^{'}$ splits into exactly two components, $G_{1}$ containing $u$ and $G_{2}$ containing $v$ — exactly two, because every vertex of $G$ reaches $u$ or $v$ in $G^{'}$ along its unique path to $u$ with the edge $uv$ removed. Each $G_{i}$ inherits property (2), since paths inside a component of $G^{'}$ are paths of $G$ . If $G_{1}$ and $G_{2}$ have $n_{1}$ and $n_{2}$ vertices, with $n_{1} + n_{2} = n$ , the inductive hypothesis gives them $n_{1} - 1$ and $n_{2} - 1$ edges, so

m = (n_{1} - 1) + (n_{2} - 1) + 1 = n - 1.

$3 \Rightarrow 4$ . Let $G$ be connected with $n - 1$ edges; we must show it is acyclic. Suppose it contains a cycle $C$ and delete one edge $e$ of $C$ . Deleting an edge of a cycle cannot disconnect the graph: any walk that used $e$ can instead go the other way around $C$ . So $G - e$ is connected on $n$ vertices with $n - 2$ edges. Repeating, we may keep deleting edges of cycles while any cycle remains; the process stops, since the edge count strictly decreases, and leaves a connected acyclic graph — a tree — on $n$ vertices with fewer than $n - 1$ edges. But $1 \Rightarrow 2 \Rightarrow 3$ , already proved, says every tree on $n$ vertices has exactly $n - 1$ edges. This contradiction shows no cycle existed.

$4 \Rightarrow 1$ . Let $G$ be acyclic with $n - 1$ edges, and let its components be $H_{1}, \dots, H_{c}$ with $n_{i}$ vertices each. Each $H_{i}$ is connected and acyclic, hence a tree, hence has $n_{i} - 1$ edges by the implications already proved. Summing,

n - 1 = m = i = 1 \sum c (n_{i} - 1) = n - c,

so $c = 1$ and $G$ is connected. Being also acyclic, it is a tree.∎

Intuition. Read the theorem as a budget. To connect $n$ vertices you must spend at least $n - 1$ edges, because each edge can reduce the number of components by at most one. Spend exactly $n - 1$ and you have no slack: every edge is load-bearing, there is no alternative route anywhere, and any extra edge would create a cycle. A tree is connectivity bought at the minimum price.

Corollary 5.36 (Forests). A forest on $n$ vertices with $c$ components has exactly $n - c$ edges.

Proof. Each component is connected and acyclic, hence a tree, so by the theorem Characterisations of a tree a component with $n_{i}$ vertices has $n_{i} - 1$ edges. Summing over the $c$ components gives $\sum (n_{i} - 1) = n - c$ .∎

Proposition 5.37 (Every tree has at least two leaves). Every tree with at least two vertices has at least two leaves.

Proof. Let $T$ be such a tree. It has an edge, since it is connected with $n \geq 2$ , so it has a path of positive length; among all paths choose one of maximum length, say $P = w_{0}, w_{1}, \dots, w_{k}$ with $k \geq 1$ .

We claim $w_{0}$ is a leaf. It has the neighbour $w_{1}$ , so $de g (w_{0}) \geq 1$ . Suppose it had another neighbour $x \neq = w_{1}$ . If $x$ is not on $P$ then $x, w_{0}, \dots, w_{k}$ is a longer path, contradicting maximality. If $x = w_{i}$ for some $i \geq 2$ , then $w_{0}, \dots, w_{i}, w_{0}$ is a cycle, contradicting acyclicity. So $de g (w_{0}) = 1$ .

The same argument applied to the other end shows $de g (w_{k}) = 1$ , and $w_{0} \neq = w_{k}$ because $k \geq 1$ and $P$ is a path. Hence $T$ has at least two leaves.∎

Example 5.38 (Degrees in a tree). A tree has $10$ vertices, of which one has degree $4$ , one has degree $3$ , and two have degree $2$ . How many leaves does it have?

Solution.

By the theorem Characterisations of a tree, the tree has $10 - 1 = 9$ edges, so by the theorem Handshake lemma the degrees sum to $18$ .
The four listed vertices account for $4 + 3 + 2 + 2 = 11$ , leaving $18 - 11 = 7$ to be shared among the remaining $10 - 4 = 6$ vertices.
Every vertex of a tree with $n \geq 2$ has degree at least $1$ , so six vertices with degree sum $7$ means five of degree $1$ and one of degree $2$ .
Hence there are $5$ leaves.

□

Proposition 5.39 (Edges of a tree are critical). Let $T$ be a tree. Deleting any edge disconnects it, and adding any new edge between two existing vertices creates exactly one cycle.

Proof. For deletion, let $e = uv$ be an edge and suppose $T - e$ were connected. Then it contains a $u$ – $v$ path $P$ , which avoids $e$ , and $P$ together with $e$ forms a cycle in $T$ , contradicting acyclicity. So $T - e$ is disconnected.

For addition, let $u, v$ be non-adjacent vertices of $T$ . By the theorem Characterisations of a tree there is exactly one $u$ – $v$ path $P$ in $T$ , and $P$ together with the new edge $uv$ is a cycle. Conversely any cycle in $T + uv$ must use the new edge, since $T$ itself is acyclic, and removing that edge from the cycle leaves a $u$ – $v$ path in $T$ — which is $P$ , by uniqueness. So the cycle is $P + uv$ , and there is exactly one.∎

Definition 5.40 (Spanning tree). A spanning tree of a connected graph $G$ is a subgraph which is a tree and contains every vertex of $G$ .

Theorem 5.41 (Every connected graph has a spanning tree). Every connected graph $G$ contains a spanning tree.

Proof. Among all connected spanning subgraphs of $G$ — subgraphs containing every vertex and connected — choose one, call it $H$ , with as few edges as possible. At least one such subgraph exists, namely $G$ itself, and the number of edges is a non-negative integer, so a minimum is attained.

We claim $H$ is acyclic. If $H$ contained a cycle $C$ , delete an edge $e$ of $C$ . Any walk in $H$ using $e$ can be rerouted the other way round $C$ , so $H - e$ is still connected and still spans, and it has fewer edges than $H$ — contradicting minimality.

So $H$ is a connected acyclic spanning subgraph, that is, a spanning tree of $G$ .∎

The proof is a specification for an algorithm rather than an efficient algorithm itself; in practice one grows a spanning tree outwards with breadth-first or depth-first search in time proportional to $n + m$ . When the edges carry weights and one wants the cheapest spanning tree, the relevant algorithms are Kruskal's and Prim's, developed in Combinatorial Optimization.

Corollary 5.42 (Edge count of a connected graph). Every connected graph on $n$ vertices has at least $n - 1$ edges.

Proof. By the theorem Every connected graph has a spanning tree it contains a spanning tree, which has $n$ vertices and therefore $n - 1$ edges by the theorem Characterisations of a tree. Those edges are edges of $G$ , so $m \geq n - 1$ .∎

Note. How many trees are there on a labelled vertex set? Cayley's formula answers it: the number of trees on $n$ labelled vertices is $n^{n - 2}$ , so there are $16$ trees on $4$ vertices and $125$ on $5$ . The result is proved by the Prüfer correspondence, a bijection with the sequences of length $n - 2$ over an alphabet of size $n$ ; it is developed in Graph Combinatorics, and used here only as a fact to compute with.

Example 5.43 (Counting trees and spanning trees). How many labelled trees are there on $6$ vertices? How many spanning trees does $C_{6}$ , the cycle on $6$ vertices, have?

Solution.

By Cayley's formula the number of labelled trees on $6$ vertices is $6^{4} = 1296$ .
A spanning tree of $C_{6}$ has $6$ vertices, so $5$ edges, and $C_{6}$ has $6$ edges: a spanning subgraph with $5$ of them is obtained by deleting exactly one edge.
Deleting any single edge of a cycle leaves a path, which is connected and acyclic, hence a tree. All $6$ choices work and they give distinct subgraphs, so $C_{6}$ has $6$ spanning trees.

□

Exercises for §5.4 →

5.5Bipartite graphs and odd cycles

Many graphs come with a natural two-sided structure: students and courses, jobs and machines, applicants and posts. Edges run only between the sides, never inside one. Such graphs are called bipartite, and the striking fact of this section is that this apparently structural property has a purely local characterisation in terms of cycle lengths — and one that an algorithm can check in linear time.

Definition 5.44 (Bipartite graph). A graph $G = (V, E)$ is bipartite if its vertex set can be partitioned as $V = X \cup Y$ with $X \cap Y = \emptyset$ so that every edge has one endpoint in $X$ and one in $Y$ . The pair $(X, Y)$ is a bipartition and $X, Y$ are the parts. The complete bipartite graph $K_{s, t}$ has parts of sizes $s$ and $t$ with every cross pair joined.

Equivalently, $G$ is bipartite exactly when its vertices can be coloured with two colours so that no edge joins two vertices of the same colour: take $X$ to be the vertices of one colour. That reformulation is the one an algorithm implements, and it is the reason bipartiteness is also called $2$ -colourability.

Proposition 5.45 (Size of a complete bipartite graph). $K_{s, t}$ has $s + t$ vertices and $s t$ edges. Every vertex of the part of size $s$ has degree $t$ , and every vertex of the other part has degree $s$ .

Proof. An edge is determined by choosing one endpoint from the part of size $s$ and one from the part of size $t$ , independently, so there are $s t$ edges. A vertex in the first part is joined to every vertex of the second and to none of the first, so its degree is $t$ ; symmetrically for the other part.

As a check, the degree sum is $s t + t s = 2 s t$ , which is twice the edge count, as the theorem Handshake lemma requires.∎

Figure 5.46. Left: a bipartite graph drawn with its two parts in columns, so every edge crosses between them. Right: the

5

-cycle, whose vertices cannot be two-coloured because its length is odd.

Walk round the $5$ -cycle alternating the two colours. After five steps you are back where you started but you have changed colour an odd number of times, so the start vertex would need both colours. The vertex drawn in a third tone is where the attempt breaks down. The next theorem says that this obstruction is the only one.

Theorem 5.47 (Bipartite if and only if no odd cycle). A graph $G$ is bipartite if and only if it contains no cycle of odd length.

Proof. ( $\Rightarrow$ ) A bipartite graph has no odd cycle. Let $(X, Y)$ be a bipartition and let $w_{0}, w_{1}, \dots, w_{k} = w_{0}$ be a cycle. Every edge crosses between the parts, so consecutive vertices of the cycle lie in different parts: the sequence alternates $X, Y, X, Y, \dots$ . Hence $w_{i}$ lies in the same part as $w_{0}$ exactly when $i$ is even. Taking $i = k$ and using $w_{k} = w_{0}$ forces $k$ to be even. So every cycle, in fact every closed walk, has even length.

( $\Leftarrow$ ) A graph with no odd cycle is bipartite. It suffices to prove this for a connected graph, since a graph is bipartite exactly when each of its components is: two-colour the components independently and take the unions of the colour classes.

So assume $G$ is connected and has no odd cycle. Fix a vertex $r$ and colour every vertex by the parity of its distance from $r$ :

X = {v : d (r, v) is even}, Y = {v : d (r, v) is odd} .

Every vertex receives exactly one colour, since $G$ is connected and so $d (r, v)$ is a finite integer. We must show no edge joins two vertices of the same class.

Suppose $uv \in E$ with $d (r, u)$ and $d (r, v)$ of the same parity. Let $P$ be a shortest $r$ – $u$ path and $Q$ a shortest $r$ – $v$ path, of lengths $a$ and $b$ with $a \equiv b (mod 2)$ . Let $x$ be the last vertex lying on both $P$ and $Q$ ; such a vertex exists because both start at $r$ . Write $a^{'}$ for the length of the portion of $P$ from $x$ to $u$ , and $b^{'}$ for the portion of $Q$ from $x$ to $v$ .

A shortest path's initial segments are themselves shortest paths, so the portions of $P$ and of $Q$ from $r$ to $x$ both have length $d (r, x)$ ; call it $c$ . Then $a = c + a^{'}$ and $b = c + b^{'}$ , so

a^{'} + b^{'} = (a - c) + (b - c) = a + b - 2 c,

which is even because $a \equiv b (mod 2)$ . Now assemble the closed walk consisting of the portion of $P$ from $x$ to $u$ , then the edge $uv$ , then the portion of $Q$ from $v$ back to $x$ . Its length is $a^{'} + b^{'} + 1$ , which is odd.

Is it a cycle? The two portions meet only at $x$ , by the choice of $x$ as the last common vertex, and each is a path. The vertices $u$ and $v$ are distinct since $uv$ is an edge of a simple graph. So the closed walk has no repeated vertex apart from its endpoint, and its length is odd and at least $3$ — it cannot be $1$ , which would be a loop. That is an odd cycle, contradicting the hypothesis.

Hence no edge joins two vertices of the same class, and $(X, Y)$ is a bipartition.∎

The hard direction is not just an existence proof; it is an algorithm. Run breadth-first search from $r$ , which computes $d (r, v)$ for every $v$ in time proportional to $n + m$ , and colour each vertex by the parity of its layer. Then scan every edge once. If no edge joins two vertices of the same colour, the colouring is a valid bipartition; if some edge does, the proof run backwards produces an explicit odd cycle, which is a certificate that no bipartition exists. Either way the algorithm answers in linear time and hands back evidence. Very few graph properties are this well behaved.

Example 5.48 (Testing bipartiteness by BFS). Let $G$ have vertices $1, \dots, 6$ and edges $12, 23, 34, 45, 56, 61, 14$ . Is it bipartite?

Solution.

The first six edges form the cycle $1, 2, 3, 4, 5, 6, 1$ , which is even, so it alone is no obstruction. The chord $14$ is the question.
Run the distance colouring from $r = 1$ : $d (1, 1) = 0$ , $d (1, 2) = 1$ , $d (1, 6) = 1$ , $d (1, 4) = 1$ via the chord, $d (1, 3) = 2$ , $d (1, 5) = 2$ .
Colour by parity: $X = {1, 3, 5}$ and $Y = {2, 4, 6}$ . Check every edge: $12, 23, 34, 45, 56, 61$ all cross, and so does $14$ .
No edge lies inside a part, so $G$ is bipartite with bipartition $({1, 3, 5}, {2, 4, 6})$ . Equivalently, every cycle of $G$ — the $6$ -cycle and the two $4$ -cycles created by the chord — is even.

□

Example 5.49 (Finding the odd cycle). The graph on ${1, \dots, 5}$ with edges $12, 23, 34, 45, 51, 13$ is not bipartite. Exhibit an odd cycle.

Solution.

Colour from $r = 1$ : $d (1, 2) = 1$ , $d (1, 5) = 1$ , $d (1, 3) = 1$ via the chord, $d (1, 4) = 2$ .
So $X = {1, 4}$ and $Y = {2, 3, 5}$ . The edge $23$ lies inside $Y$ , so the colouring fails, and the theorem Bipartite if and only if no odd cycle says an odd cycle must be nearby.
Following the proof: shortest paths $1, 2$ and $1, 3$ meet last at $x = 1$ , so the closed walk is $1, 2, 3, 1$ — the triangle $123$ , of length $3$ .
That odd cycle certifies that no bipartition exists.

□

Corollary 5.50 (Trees are bipartite). Every tree, and more generally every forest, is bipartite.

Proof. A tree is acyclic, so it contains no cycle at all, in particular no odd cycle. By the theorem Bipartite if and only if no odd cycle it is bipartite. The same argument applies to a forest.∎

Proposition 5.51 (Edge bound for bipartite graphs). A bipartite simple graph on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ edges.

Proof. Let $(X, Y)$ be a bipartition with $∣ X ∣ = s$ and $∣ Y ∣ = n - s$ . Every edge joins a vertex of $X$ to a vertex of $Y$ , and no such pair carries two edges, so

m \leq s (n - s) .

The function $s \mapsto s (n - s)$ is a downward parabola in $s$ with maximum at $s = n /2$ . If $n$ is even this gives $n^{2} /4$ ; if $n$ is odd the nearest integers are $s = (n \pm 1) /2$ , giving $\frac{n - 1}{2} \cdot \frac{n + 1}{2} = \frac{n ^{2} - 1}{4}$ . In both cases the value is $⌊ n^{2} /4 ⌋$ .∎

Remark. Compare this with the proposition Maximum number of edges: a general graph on $n$ vertices can have about $n^{2} /2$ edges, a bipartite one only about $n^{2} /4$ . Forbidding odd cycles costs half the edges. Asking the same question for other forbidden subgraphs is the subject of extremal graph theory, and the triangle-free case of this bound is Mantel's theorem, proved in Graph Combinatorics.

Definition 5.52 (Proper colouring and chromatic number). A proper colouring of $G$ assigns a colour to each vertex so that adjacent vertices differ. The chromatic number $χ (G)$ is the least number of colours in a proper colouring.

Proposition 5.53 (Chromatic number two). For a graph $G$ with at least one edge, $χ (G) = 2$ if and only if $G$ is bipartite. Moreover $χ (K_{n}) = n$ and $χ (C_{k}) = 3$ for odd $k \geq 3$ .

Proof. A proper colouring with two colours is exactly a bipartition, with the colour classes as the parts, so $χ (G) \leq 2$ if and only if $G$ is bipartite. Since $G$ has an edge, one colour will not do, so $χ (G) = 2$ precisely for bipartite $G$ .

In $K_{n}$ every two vertices are adjacent, so all $n$ colours must differ, and $n$ colours suffice; hence $χ (K_{n}) = n$ . An odd cycle is not bipartite by the theorem Bipartite if and only if no odd cycle, so it needs at least $3$ colours; and $3$ suffice — alternate two colours round the cycle and give the last vertex the third.∎

Example 5.54 (Chromatic numbers of small graphs). Compute $χ (C_{8})$ , $χ (K_{3, 4})$ and $χ (K_{4})$ .

Solution.

$C_{8}$ is an even cycle, so it contains no odd cycle and is bipartite; having an edge, $χ (C_{8}) = 2$ .
$K_{3, 4}$ is bipartite by construction and has edges, so $χ (K_{3, 4}) = 2$ — the number of colours does not grow with the size of the parts.
$χ (K_{4}) = 4$ , since all four vertices are mutually adjacent.

□

Exercises for §5.5 →

5.6Eulerian circuits, Königsberg and the Hamiltonian contrast

In 1736 Euler was asked whether the citizens of Königsberg could walk through the town crossing each of its seven bridges exactly once and returning home. He answered no, and in explaining why he invented graph theory: the shapes and sizes of the land masses are irrelevant, only the pattern of connections matters. What he proved is stronger than the answer to the puzzle — it is a complete characterisation, valid for every graph.

Definition 5.55 (Eulerian trail and circuit). An Eulerian trail in a graph is a trail that uses every edge exactly once. An Eulerian circuit is a closed Eulerian trail. A graph possessing an Eulerian circuit is called Eulerian.

Note that it is edges that must be used once; vertices may be revisited freely, which is what makes the problem tractable. Isolated vertices are a nuisance in the statement rather than in the substance, so we require connectedness of the part of the graph that carries edges.

Theorem 5.56 (Euler's theorem). Let $G$ be a connected multigraph with at least one edge. Then $G$ has an Eulerian circuit if and only if every vertex has even degree.

Proof. ( $\Rightarrow$ ) Necessity. Suppose $C$ is an Eulerian circuit, and fix a vertex $v$ . Traverse $C$ and look at the moments it visits $v$ . Each visit to $v$ that is not the start or the finish uses one edge to arrive and a different one to leave, consuming two edges at $v$ ; the start uses one edge to leave and the finish one edge to arrive, and since $C$ is closed these two also pair up into a single arrival-and-departure at the same vertex. So the edges at $v$ are partitioned into pairs, and $de g (v)$ is even. No edge at $v$ is missed, because $C$ uses every edge, and none is counted twice, because $C$ is a trail.

( $\Leftarrow$ ) Sufficiency. Assume $G$ is connected with every degree even. We first show that any trail can be extended or closed.

Claim: a trail starting at a vertex $u$ and currently at a vertex $w \neq = u$ can always be extended. Indeed, the edges at $w$ used so far consist of one arrival for each visit and one departure for each departure; since $w$ is not the start, the visits and departures so far pair up except for the final arrival, so an odd number of edges at $w$ has been used. As $de g (w)$ is even, an unused edge at $w$ remains, and the trail can step along it.

Therefore a trail that cannot be extended must end where it started: every maximal trail is closed.

Now argue by strong induction on the number of edges $m$ . Start anywhere and walk without repeating edges until stuck; by the claim the resulting trail $C_{1}$ is a closed trail. Remove its edges from $G$ , leaving a graph $H$ . Every vertex of $H$ has even degree, because $C_{1}$ removed an even number of edges at each vertex — again by the pairing argument, applied to the closed trail $C_{1}$ .

If $H$ has no edges, $C_{1}$ used them all and is an Eulerian circuit. Otherwise consider a component $H^{'}$ of $H$ containing an edge. Since $G$ is connected, $H^{'}$ must share a vertex $z$ with $C_{1}$ : otherwise no edge of $G$ would join $H^{'}$ to the rest, contradicting connectedness of $G$ . The component $H^{'}$ is connected, has all degrees even and has fewer edges than $G$ , so by the inductive hypothesis it has an Eulerian circuit $C^{'}$ , which we may start and end at $z$ .

Splice: traverse $C_{1}$ from its start until it first reaches $z$ , then traverse the whole of $C^{'}$ , returning to $z$ , then finish $C_{1}$ . The result is a closed trail — no edge repeats, since $C_{1}$ and $C^{'}$ are edge-disjoint — using every edge of $C_{1}$ and of $H^{'}$ . Repeat the splice for each component of $H$ carrying edges; each splice strictly increases the number of edges used, so the process terminates with a closed trail using every edge of $G$ , which is an Eulerian circuit.∎

Intuition. Even degree is a conservation law. Every time the walk enters a room it must leave again, so the doors of each room get used in pairs — except the room you start and finish in, where the first departure pairs with the last arrival. If some room has an odd number of doors, one door is left over, and the walk must either start there, finish there, or leave that door unused.

Corollary 5.57 (Eulerian trails). A connected multigraph with at least one edge has an Eulerian trail that is not closed if and only if exactly two of its vertices have odd degree. Such a trail must start at one of them and end at the other.

Proof. ( $\Rightarrow$ ) Suppose $T$ is an Eulerian trail from $u$ to $v$ with $u \neq = v$ . At every vertex other than $u$ and $v$ the pairing argument of the theorem Euler's theorem applies unchanged, so those degrees are even. At $u$ the edges pair up except the initial departure, so $de g (u)$ is odd, and likewise $de g (v)$ is odd. So exactly two vertices have odd degree.

( $\Leftarrow$ ) Suppose exactly $u$ and $v$ have odd degree. Add a new edge $e = uv$ to $G$ , obtaining a multigraph $G^{'}$ — a new parallel edge if $uv$ was already present, which is why multigraphs are the right setting. In $G^{'}$ the degrees of $u$ and $v$ have each risen by one and are now even, all other degrees are unchanged and even, and $G^{'}$ is connected. By the theorem Euler's theorem, $G^{'}$ has an Eulerian circuit. Rotate it so that it begins by traversing $e$ from $v$ to $u$ , then delete that first step. What remains is a trail from $u$ to $v$ using every edge of $G$ exactly once: an Eulerian trail.

Finally, the first part shows the endpoints of any non-closed Eulerian trail are vertices of odd degree, and here the only two such are $u$ and $v$ .∎

Corollary 5.58 (The bridges of Königsberg). The seven bridges of Königsberg cannot be walked exactly once each on a single route, closed or not.

Proof. Model the four land masses as vertices and the seven bridges as edges, giving the connected multigraph of the figure below. Its degrees are $5, 3, 3, 3$ : the island meets five bridges and each of the other three land masses meets three.

All four vertices have odd degree. Since not every degree is even, the theorem Euler's theorem rules out a closed route. Since the number of odd vertices is four rather than two, the corollary Eulerian trails rules out an open route as well. No such walk exists.∎

Figure 5.59. Königsberg as a multigraph: four land masses, seven bridges, and every vertex of odd degree. The labels give the degrees, and four odd degrees is two too many for any Eulerian trail.

Example 5.60 (Which of these can be drawn in one stroke?). Decide whether each has an Eulerian circuit, an Eulerian trail, or neither: (a) $K_{5}$ ; (b) $K_{4}$ ; (c) $K_{2, 3}$ ; (d) the graph on ${a, b, c, d}$ with edges $ab, b c, c d, d a, a c$ .

Solution.

(a) $K_{5}$ is connected and $4$ -regular by the corollary Degrees in a complete graph, so every degree is even and it has an Eulerian circuit.
(b) $K_{4}$ is $3$ -regular: four vertices of odd degree, so neither a circuit nor a trail.
(c) $K_{2, 3}$ has two vertices of degree $3$ and three of degree $2$ , by the proposition Size of a complete bipartite graph. Exactly two odd vertices, so by the corollary Eulerian trails it has an Eulerian trail from one degree- $3$ vertex to the other, but no circuit.
(d) The degrees are $de g (a) = 3$ , $de g (b) = 2$ , $de g (c) = 3$ , $de g (d) = 2$ . Exactly two odd vertices, $a$ and $c$ , so there is an Eulerian trail from $a$ to $c$ — for instance $a, b, c, d, a, c$ — and no circuit.

□

Example 5.61 (When is a complete graph Eulerian?). For which $n \geq 3$ does $K_{n}$ have an Eulerian circuit?

Solution.

$K_{n}$ is connected, and every vertex has degree $n - 1$ by the corollary Degrees in a complete graph.
By the theorem Euler's theorem an Eulerian circuit exists exactly when $n - 1$ is even, that is, when $n$ is odd.
So $K_{3}, K_{5}, K_{7}, \dots$ are Eulerian, while $K_{4}, K_{6}, \dots$ are not — and $K_{4}$ , having four odd vertices, has no Eulerian trail either.

□

Definition 5.62 (Hamiltonian path and cycle). A Hamiltonian path in $G$ is a path passing through every vertex exactly once; a Hamiltonian cycle is a cycle doing the same. A graph with a Hamiltonian cycle is Hamiltonian.

The two problems look like mirror images — every edge once, versus every vertex once — and it is natural to expect a matching theorem. There is none.

Remark. No characterisation of Hamiltonian graphs comparable to Euler's theorem is known, and there is strong evidence that none exists: deciding whether a graph has a Hamiltonian cycle is NP-complete, one of Karp's original twenty-one problems. Euler's condition is checkable in time proportional to $n + m$ , while the best known Hamiltonicity algorithms take exponential time in the worst case. What does exist is a supply of sufficient conditions — Dirac's theorem, that $δ (G) \geq n /2$ with $n \geq 3$ forces a Hamiltonian cycle, and Ore's refinement — proved in Graph Combinatorics. None of them is necessary, and none of them settles the general case.

Example 5.63 (Eulerian is not Hamiltonian). Give a graph that is Eulerian but not Hamiltonian, and one that is Hamiltonian but not Eulerian.

Solution.

Take two triangles sharing a single vertex — the "bowtie" on five vertices. Every degree is $2$ , $2$ , $4$ , $2$ , $2$ , all even, and the graph is connected, so by the theorem Euler's theorem it is Eulerian. But any cycle through all five vertices would have to pass through the shared vertex twice, so it is not Hamiltonian.
Take $C_{4}$ with one chord, on vertices $a, b, c, d$ with edges $ab, b c, c d, d a, a c$ . The cycle $a, b, c, d, a$ visits every vertex once, so it is Hamiltonian; but $de g (a) = de g (c) = 3$ are odd, so it is not Eulerian.
The two properties are therefore independent: neither implies the other.

□

Pitfall. "Every vertex has even degree" is not by itself enough. Two disjoint triangles have all degrees equal to $2$ , yet no trail can cross from one triangle to the other, so there is no Eulerian circuit. Connectedness is a genuine hypothesis of the theorem Euler's theorem, not decoration.

Exercises for §5.6 →

Common Mistakes

Confusing walks, trails and paths. A walk may repeat anything; a trail repeats no edge; a path repeats no vertex. Euler's theorem is about trails, Hamiltonicity about paths, and reachability about walks. Stating the wrong one turns a true theorem into a false one.

Forgetting that the handshake lemma runs only one way. An even degree sum is necessary for a graph to exist with a given degree sequence, never sufficient. Always exhibit a graph, or find a second obstruction, before claiming a sequence is realisable.

Counting each edge once in a degree sum. The sum of degrees is $2 m$ , not $m$ . The factor of two is the whole content of the theorem Handshake lemma, and dropping it is the single most common arithmetic slip in this chapter.

Assuming a connected graph with $n - 1$ edges might still have a cycle. By the theorem Characterisations of a tree it cannot: connected plus $n - 1$ edges forces acyclicity, exactly as acyclic plus $n - 1$ edges forces connectedness. Any two of the three conditions imply the third.

Thinking every cycle must be even for bipartiteness, and checking only the short ones. Bipartiteness fails if any odd cycle exists anywhere in the graph, however long. Checking triangles is not enough; run the distance-parity colouring of the theorem Bipartite if and only if no odd cycle, which sees all cycles at once.

Treating a failed two-colouring as an inconclusive result. If BFS from any root produces an edge inside a colour class, the graph is definitely not bipartite, and the proof extracts an explicit odd cycle as proof. A failure is a certificate, not a maybe.

Dropping connectedness from Euler's theorem. All degrees even guarantees an Eulerian circuit only for a connected graph. Two disjoint even-degree components have none.

Expecting an Euler-style test for Hamiltonicity. There is no known degree condition that is both necessary and sufficient, and the problem is NP-complete. Dirac's condition is sufficient only: a graph can be Hamiltonian with minimum degree $2$ , as every cycle $C_{n}$ shows.

Confusing $K_{n}$ with $K_{s, t}$ . $K_{n}$ has $(2 n)$ edges and is complete; $K_{s, t}$ has $s t$ edges and is bipartite. $K_{4}$ has $6$ edges, $K_{2, 2}$ has $4$ and is a $4$ -cycle.

Reading a drawing as the graph. Two drawings that look different can be the same graph, and crossings in a drawing are an artefact of the drawing, not a property of the graph. Every claim must be checkable from $V$ and $E$ alone.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter