Graph Theory

MATH3033
2024–2025 Semester 1
University of Leeds
ii
Contents

Introduction 1

1 Basic notions 3
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Isomorphism of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Matchings 17
2.1 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Maximum matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Matchings in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Hall’s matching theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Connectivity 25
3.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 A characterisation of 2-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Cut-vertices and blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Hamiltonian graphs 33
4.1 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Necessary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Sufficient conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4 Hamiltonian closure and Chvátal’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Algebraic graph theory 39

5.1 Preliminaries from linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2 The adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 Strongly regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.4 The friendship theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 The matrix-tree theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.6 Cayley’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

iii
Contents Contents

iv
Introduction

A graph is a mathematical structure which is useful when we want to study the connections between certain
things. Before giving a precise definition of a graph, we give some motivation and look at some examples
where such a study is useful.

First, we give some historical motivation.

(i) Königsberg. First we consider the problem which is usually considered to be the origin of graph theory:
the bridges of Königsberg. Königsberg is now called Kaliningrad and is part of Russia, located about
30 miles north of Poland, but we will be concerned with Königsberg in the 1700s, when it was part of
Prussia, a precursor of modern-day Germany.

A river ran through the centre of Königsberg, creating an island, and there were seven bridges crossing
this river. The story goes that the citizens of Königsberg wondered whether it was possible to walk
through the city crossing each bridge exactly once. No-one could find such a route. In 1795 Leonhard
Euler showed that it was impossible to make such a walk. His ideas marked the beginning of graph
theory and of topology.

You can easily find old maps of the city of Königsberg on the internet, and can draw a graph representing
the problem, with dots representing the land masses and lines representing the bridges, for yourself.

(ii) Molecules. In chemistry one studies molecules, which are made up of different atoms connected by
chemical bonds. These molecules are often drawn as pictures on the page, with letters representing
the atoms and lines representing the chemical bonds. Note that these pictures do not tell us how the
atoms are arranged in space, but only give us information about the bonds, or connections, between
the atoms. For example, a molecule of methane, which is usually drawn in the following way,

H C H

actually has a tetrahedral structure.

Methane has the chemical formula CH4 . In the 1870s, Arthur Cayley determined the possible structures
of all molecules with chemical formula Cn H2n+2 , known as alkanes or paraffins, using graph theoretic
techniques.

Next, we give some modern motivation.

(iii) The web. We can use the structure of a graph to record links between web pages. Note that, just
using links and without using our browser’s “back” button, there is a concept of direction here: a page
we reach by clicking on a certain link may not have a link back to the page we came from. So our
graph should be directed.

Here is a directed graph which records a small part of the links between web pages on the university’s

1
Contents Contents

website:
University
O of Leeds `

Undergraduate
O [

Learning at Leeds

Research and innovation

Search engines used to work by counting how many times a given word appeared on a webpage. The
insight of the creators of Google was to realize the importance of the links between webpages, and to
consider a web page more important if lots of other web pages linked to it. This graph theoretic idea
lies behind the power of the Google search engine.
(iv) Social media. What is the difference between Facebook and Twitter? On Facebook, you can become
a “friend” of someone, and on Twitter you can “follow” someone. But on Facebook, two people A
and B are either friends or not friends, while on Twitter it is possible for A to follow B but for B not
to follow A. So, graph theoretically, the underlying structure of the users of Facebook is an undirected
graph, while the underlying structure of the users of Twitter is a directed graph.
(v) Mathematics. Consider the integers. We will construct a graph representing even and odd numbers.
Connect two integers if their difference is precisely 2. This gives the following infinite graph:

··· −5 −4 −3 −2 −1 0 1 2 3 4 5 ···

It is easy to see that this graph has precisely two components:

··· −4 −2 0 2 4 ···

and

··· −5 −3 −1 1 3 5 ···

These components are the even and odd integers.

(vi) The Tube. The London Underground consists of various train lines which run between different stations.
At some of these stations you can change trains, joining a different line. Historically, this was mapped
by overlaying the underground train lines on a map of London. However, in 1931, Harry Beck realized
that, for most purposes, the exact geographic positions of the train lines was unimportant: people only
wanted to know how to get from one station to another. With this realization, he designed a new
tube map which wasn’t based on the precise positions of the stations and the lines but instead on the
connections between the stations. His map was topological, rather than geometric, and its underlying
structure is that of a graph. Tube maps are still based on Harry Beck’s design today.
It is remarkable that all these different situations can be studied using the single (although very general) notion
of a graph. Graph theory is the area of mathematics devoted to the study of graphs and their applications.
This module will be a first introduction to graph theory.

2
Chapter 1

Basic notions

1.1 Graphs
We begin by giving a precise definition of a graph and recalling some basic terminology and results. Most of
this material has already been covered in Discrete Mathematics (MATH2230), so please refer to [Elw20] for
additional details and for the proofs that we omit.
While we often think of graphs pictorially, we do not want to be limited to pictures of graphs, both in order
to enable us to prove results about graphs, and so that we can consider large graphs, without having to draw
them. The motivational examples of the Introduction included different types of graphs: some were directed
and some were not, some were finite and some were not, some had values attached to the edges and some
did not. At first, we will consider the most elementary definition. In order to state it, let us introduce some
notation. For a set A, we write A{2} for the set of 2-element subsets of A, i.e.

S ∈ A{2} ⇔ (∃x , y ∈ A) x ̸= y and S = {x , y } .

n
Note that if |A| = n then |A{2} | =


2 .

Definition 1.1.1. A graph is a pair of sets G = (V , E ) such that E ⊆ V {2} .

We use letters G , G ′ , G ′′ , ... , H , H ′ , H ′′ , ... to denote graphs. For a graph G , we write V (G ) and E (G ) for
its set of vertices and edges, respectively. A graph is finite if both the set of vertices and the set of edges are
finite. In this course, all graphs will be assumed implicitly to be finite. Below, for a graph G , we write

v (G ) , e(G )

for the number of vertices and edges of G , respectively.

Let us unfold the abstract definition of a graph given above and explain how it relates to the pictorial
representation of graphs. Let G = (V , E ) be a graph. We call the elements of V vertices and the elements
of E edges. By definition,

e ∈ E ⇔ ∃u, v ∈ V such that u ̸= v and e = {u , v }

Thus, an edge of a graph consists of a set of two distinct vertices, which we will call the endpoints of the
edge. We represent such an edge as follows:

u v

For simplicity, we sometimes write e = uv rather than e = {u , v }. With this notation, uv = vu. Note that
in practice we will almost never write out the full definition of a graph – we will usually just draw a picture –
but it is important to have the precise definition. If we wanted to work with graphs on a computer then we
might need to use such a formal definition, though we will see another way that we could do this later.

3
Chapter 1. Basic notions 1.1. Graphs

The notion of a graph introduced in Definition 1.1.1 is that of a simple graph, in which between any two
vertices there is at most one edge, edges have distinct endpoints, edges do not have directions or weights
attached to them. Occasionally, we will consider other kinds of graph in this module, but we shall focus on
simple graphs and hence refer to them just as graphs.

Example.
(i) Let G = (V , E ) be the graph where

V = {x , y , z , u , v } , E = {xy , xu , xv , yz , yu , zu} .

Then, we can draw G as

x y

v u
Note that there are several possible ways of drawing the same graph. We will return to this point when
we consider the notion of a graph isomorphism.
(ii) An example of a graph is the the cycle graph Cn , which has vertices indexed by the integers modulo n,
for some n ≥ 1, and with edges joining each i to i + 1.
(iii) The Petersen graph is

(iv) Fix k, n ∈ N with 2 ≤ k < n. We define the Johnson graph J(n, k) to be the graph whose vertices are
exactly the k-element subsets of {1, ... , n} (the k-subsets),
with two k-subsets (i.e. vertices) adjacent
if they intersect in a (k − 1)-subset. Observe that it has kn vertices. For example, the graph J(4, 2) is
depicted below:
12 13

J(4, 2) = 23 14

24 34
Here n = 4 and k = 2. The vertex {1, 2} is adjacent to the vertex {1, 3} since {1, 2} ∩ {1, 3} = {1}
which has size 1 = k − 1. On the other hand, {1, 2} is not adjacent to {3, 4} since {1, 2} ∩ {3, 4} = ∅
which has size 0 = k − 2.
One of the nice features of graph theory is that a lot of its terminology is supported a clear pictorial intuition.
Let us introduce some of it. Let G = (V , E ) be a graph. Let e = uv ∈ E be an edge. We can express this
situation by saying that u and v are adjacent, that e joins u and v , that u is a neighbour of v , or that u is
incident with e. If two edges have a common endpoint, we say that they are adjacent.

Degrees
Definition 1.1.2. Let G = (V , E ) be a graph. The degree of a vertex v ∈ V , denoted d(v ), is the number
of edges of G incident with v . We say that a vertex is isolated if it has degree 0, i.e. d(v ) = 0.

4
Chapter 1. Basic notions 1.1. Graphs

Example. Consider the graph

y z

t u v w x

Then w has degree 3 and t is an isolated vertex.

The following is an elementary observation on degrees, which has been proved in MATH2230 [Elw20].
Proposition 1.1.3 (Handshaking Lemma). Let G = (V , E ) be a graph, with V = {x1 , ... , xn }.Then,
n
X
d(xi ) = 2|E | .
i=1

Subgraphs
In many mathematical settings, one has a notion of substructure. For graphs, this is the notion of a subgraph,
which we introduce next.
Definition 1.1.4. Let G = (V , E ) be a graph. A subgraph of G is a graph G ′ = (V ′ , E ′ ) such that

V′ ⊆ V , E′ ⊆ E .

We have a spanning subgraph if V = V ′ . We have a full subgraph if for all u , v ∈ V ′ , if uv ∈ E then

uv ∈ E ′ .

Example. Consider the graphs

1 2 1 2

G= G′ =

4 3 4 3

Here, G ′ is a subgraph of G , but it is not a full subgraph, as there are vertices of G ′ that are adjacent in G
but not in G ′ . Instead, the graph
1 2

G ′′ =

4
is a full subgraph of G .

Special classes of graphs

Definition 1.1.5. Let G = (V , E ) be a graph. We say that G is complete if there is an edge between any
two vertices. We say G is null if it has no edges.
Example. We write Kn for the complete graph with vertex set {1 , ... n}. Note that
 
n n(n − 1)
|V (Kn )| = n , |E (Kn )| = = .
2 2

For example, K4 is
1 2

4 3

5
Chapter 1. Basic notions 1.1. Graphs

Definition 1.1.6. Let G = (V , E ) be a graph. A bipartition of G is a pair of subsets X , Y ⊆ V such that

X ∪ Y = V , X ∩ Y = ∅ and every edge of G has one endpoint in X and the other in Y . A graph is said to
be bipartite if there is a bipartition of it.
Example. The graph G = (V , E ) depicted below

x1 x2 x3

y2 y1

is bipartite, as X = {x1 , x2 , x3 } and Y = {y1 y2 } provide a bipartition for it.

Definition 1.1.7. Let G = (V , E ) a graph. We say that G is complete bipartite if it has a bipartition X , Y
such that every vertex in X is adjacent to every vertex in Y .
Example. We write Km,n for the complete bipartite graph with vertices {1 , ... , m , m + 1 , ... , m + n} and
bipartition
X = {1 , ... , m} , Y = {m + 1 , ... , m + n} ,
in which every i ∈ {1 , ... , m} has an edge to every j ∈ {m + 1 , ... m + n}. For example, K3,2 is

1 2 3

5 4

Note that
|V (Km,n )| = m + n , |E (Km,n )| = mn

Definition 1.1.8. Let G be a graph. For k ∈ N, we say we say that G is k-regular if all the vertices of G
have degree k. We say that G is regular if it is k-regular for some k, i.e. all vertices have the same degree.
Example. The Petersen graph is 3-regular and the Johnson graphs J(n, k) are regular.

Operations on graphs
Recall the following operations on graphs.
• Removing vertices. Let G = (V , E ) be a graph. For a subset V ′ ⊆ V , we define G − V ′ to be the
graph obtained from G by deleting the vertices in V ′ and deleting all edges incident with them. For
v ∈ V , we write G − v instead of G − {v }.
• Removing edges. Let G = (V , E ) be a graph. For a subset E ′ ⊆ E , we define G − E ′ to be the graph
obtained from G by deleting the edges in E ′ . For e ∈ E , we write G − e instead of G − {e}.
• Taking the complement. Let G = (V , E ) be a graph. We define the complement of G , written
G c = (V c , E c ), by letting V c = V and E c = V {2} \ E , so that G c has the same vertex set as G , and
two vertices are adjacent in G c if and only if they are not adjacent in G .
We illustrate these operations with examples.
Example. Consider the graph G drawn as

a b

G = c

e d

Then

6
Chapter 1. Basic notions 1.2. Isomorphism of graphs

• G − a is the graph
b

e d

• G − bd is the graph
a b

e d

• The complement G c is the graph

a b

e d

1.2 Isomorphism of graphs

In mathematics, whenever we study a class of objects, it is important to consider the relationships between
these objects. This usually means that we should study some special functions. For example, if we are
studying vector spaces, it is important to also study the linear maps between them. If we are studying subsets
of Euclidean space, it is important to consider continuous functions between them. If we are studying groups,
it is important to consider the homomorphisms between them. We will now consider the analogous concept
for graphs, but in fact only consider the notion of an isomorphism, which is analogous to a one-to-one and
onto linear transformation.

Definition 1.2.1. Let G = (V , E ) and G ′ = (V ′ , E ′ ) be graphs. An isomorphism f : G → G ′ is a bijective

function f : V → V ′ such that u and v are adjacent in G if and only if f (u) and f (v ) are adjacent in G ′ , for
all u , v ∈ V .
For example, the Petersen graph is isomorphic to the complement of the Johnson graph J(5, 2). See below
for a labelling that makes this clear:
12
c
J(5, 2)
34
35 14 23 45

15 25

24 13
Hence the Petersen graph is part of an infinite family, determined by the parameters n, k.
If there exists an isomorphism between G and G ′ then we say that G and G ′ are isomorphic and write G ∼
= G ′.
We will often treat isomorphic graphs as if they were equal.

7
Chapter 1. Basic notions 1.2. Isomorphism of graphs

Example.
• A first kind of exercise on isomorphism involves checking whether a given function is an isomorphism
of graphs. For instance, let G = (V , E ) and G ′ = (V ′ , E ′ ) be the graphs below:
v 2

u w 1 3
G= G′

y x 5 4
′
and let us consider the function f : V → V defined by letting

f (u) = 1 ,
f (v ) = 3 ,
f (w ) = 5 ,
f (x) = 2 ,
f (y ) = 4 .

We wish to check whether f is an isomorphism. To do this, we need to check two things: that f is
bijective and that uv ∈ E if and only if f (u)f (v ) ∈ E ′ . Verify this as an exercise.
• A second kind of exercise on isomorphisms involves defining the required function as well. For instance,
let H and H ′ be the graphs below:
u v w 6 1

H= H′ = 5 2

x y z 4 3
We are asked to prove that they are isomorphic. This involves first defining a function f : V → V ′ and
then checking that it is an isomorphism of graphs. We can begin by trying to define f on u. Since H ′ is
quite symmetrical, our choice does not really matter so let us define f (u) = 1. Since adjacent vertices
in H need to be mapped to adjacent vertices in H ′ , we need to map the neighbours of u in H to the
neighbours of 1 in H ′ . Let’s try

f (x) = 2 , f (y ) = 4 , f (z) = 6 .

It now remains to define f on v and w . We cannot map them to 1, 2, 4, 6, as otherwise f would not be
bijective. Also, v is neighbour of x , y , z in H, so f (v ) should be a neighbour of 2 , 4 , 6 in H ′ . Thus,
we can let
f (v ) = 3 .
We are left with f (w ) = 5. To see quickly that this is an isomorphism, observe that in H all vertices of
{u, v , w } are adjacent to all of {x, y , z} with no other edges, and in H ′ , all of {1, 3, 5} are adjacent to
all of {2, 4, 6} with no other edges.
• A third kind of exercise on isomorphism asks to determine whether two graphs are isomorphic or not.
To prove two graphs are isomorphic, we know what to do: find an isomorphism. But how do we
prove that two graphs are not isomorphic? If two finite graphs are isomorphic then they have the same
number of vertices of each degree. So graphs with different number of vertices of some degree must be
non-isomorphic. Thus, a general strategy to show that the two graphs are not isomorphic is to show
that do not share a property that is shared by isomorphic graphs.
Recall the following result from MATH2230 [Elw20].
Lemma 1.2.2.
(i) G ∼
=G

8
Chapter 1. Basic notions 1.2. Isomorphism of graphs

(ii) If G1 ∼= G2 and G2 ∼
= G3 then G1 ∼
= G3 .
(iii) (G c )c ∼
= G.
= H then G c ∼
(iv) If G ∼ = Hc .
Example. As mentioned above, if two finite graphs are isomorphic then they have the same number of vertices
of each degree. However, the converse is false: there can be graphs with the same number of vertices of each
degree which are not isomorphic. For example, consider G1 and G2 , defined as follows:

G1 G2

Both have 8 vertices, and each vertex has 5 neighbours, but they are not isomorphic. To prove that they are
not isomorphic, it is helpful to look at their complements:

G1c G2c

Note that G1c is disconnected (two squares) and G2c is connected (an octagon). We haven’t defined connect-
edness yet, but the idea is clear. From this we can show that G1c ̸∼
= G2c , and so G1 ̸∼
= G2 by Lemma 1.2.2.

Vertex-transitive graphs
An isomorphism of a graph G to itself is called an automorphism of G .
Definition 1.2.3. Let G = (V , E ) be a graph. We say that G is vertex-transitive if for any u, v ∈ V there
is an automorphism α : G → G with α(u) = v .
The idea is that a vertex-transitive looks the same ‘from each vertex’, that is, G is highly symmetrical.
Example. The Johnson graphs J(n, k) are vertex-transitive. Given two vertices {i1 , ... , ik } and {j1 , ... , jk }
(that is, two k-subsets), there exists a permutation of {1, ... , n} such that

π(i1 ) = j1 , ... , π(ik ) = jk .

In fact, there are many such permutations. Like any permutation of {1, 2, ... , n}, π induces a permutation
of the set of k-subsets of {1, ... , n} and preserves the size of intersections, so it induces an automorphism
of J(n, k). Therefore π induces an automorphism of J(n, k) which maps the vertex {i1 , ... , ik } to the ver-
tex {j1 , ... , jk }, as required.
Proposition 1.2.4. Let G = (V , E ) be a graph. Assume G is vertex-transitive graph. Then,
(i) G is regular,
(ii) the complement G c of G is also vertex-transitive.

Proof.
(i) Let u v ∈ V . By the assumption that G is vertex-transitive, there is an automorphism α : G → G such
that α(u) = v . But then d(u) = v and so G is regular.
(ii) Let u, v ∈ V (G c ). Since V (G c ) = V (G ) and G is vertex-transitive, there is an automorphism α : G →
G such that α(u) = v . Then by part (ii) of Lemma 1.2.2, αc : G c → G c is an automorphism of G c
and αc (u) = v .

9
Chapter 1. Basic notions 1.3. Paths and cycles

1.3 Paths and cycles

Definition 1.3.1 (Edge sequences and paths). Let G = (V , E ) be a graph.
• An edge sequence in G is a sequence of vertices

v0 v1 ... vk

such that v0 v1 , v1 v2 , ... vk−1 vk ∈ E . We then call v0 the initial vertex of the edge sequence and vk the
final vertex of the edge sequence. The length of an edge sequence is the number of edges in it.
• We say that an edge sequence is a path if all the vertices in it, except possibly its initial and final vertex,
are distinct.
Note that we allow an edge sequence to have length 0, going from a vertex v to itself, denoted v .
Example. Consider the graph

4 3 7 8 10

9
5
1 2 6
In this graph, 12324 is an edge sequence and 1234 is a path.
Let G = (V , E ) be a graph. For u, v ∈ V , the distance between u and v , written d(u, v ), is the length of
the shortest path from u to v . If no such path exists, we set the distance to be ∞. The diameter of G is
max{d(u, v ) | u , v ∈ V }.
We sometimes call such an edge sequence with initial vertex v0 and final vertex vk a a v0 vk -edge sequence.
The next lemma will be useful to reduce reasoning about edge sequences to reasoning about paths.
Lemma 1.3.2. Let G = (V , E ) be a graph and u , v ∈ V . Then every uv -edge sequence contains a uv -path.

Proof. By induction on the length of the edge sequence.

• Base case. For length 0, the result is trivial.
• Induction step. Assume the result holds for edge sequences of length < n and prove it for edge sequences
of length n. So let
v0 v1 v2 ... vn−1 vn
be an edge sequence of length n which is not a path. Then there are 0 ≤ i < j ≤ n such that vi = vj .
Suppose 0 < i < j < n (other cases are similar). Then

v0 v1 ... vi−1 vj vj+1 ... vn−1 vn

is a v0 vn -edge sequence of shorter length. This contains a v0 vn -path by induction, and hence so does
the original edge sequence.

Definition 1.3.3 (Closed edge sequences and cycles).

• We say that an edge sequence is closed if its initial and final vertex are the same.
• A closed path is called a cycle.
Example. Consider the graph
b d

e
a c
Then abcdba is a closed edge sequence and bcdb is a cycle.
The girth of G is the length of the shortest cycle in G . Like the diameter, the girth can be ∞.

10
Chapter 1. Basic notions 1.3. Paths and cycles

Definition 1.3.4. Let G = (V , E ) be a graph. We say G is connected for any two vertices u, v of G there
is a path from u to v . If a graph is not connected, we say it is disconnected.
Definition 1.3.5. Let G = (V , E ) be a graph. We say that an edge e ∈ E is a bridge if removing e from G
disconnects the graph, i.e. G − e is disconnected.
Example. Let G be the graph

b c f

a d e g

Here, the edge de is a bridge.

Notice that removing an edge from a cycle in a connected graph does not disconnect the graph. That is,
if G = (V , E ) is a connected graph, C is a cycle in G , and e = (a, b) is an edge of C , then G − e is still
connected. Let x, y ∈ V . Then x and y are connected via a path P in G . If P does not use edge e, then P is
also a path in G − e. If P does use edge e, then removing e breaks P into either an xa-path and a by -path or
an xb-path and an ay -path in G − e, depending on which way the path travels through edge e. For the sake
of argument, say that removing e breaks P into an xa-path and a by -path in G − e. Then x is connected to
a and b is connected to y in G − e. However, a is also connected to b in G − e by traveling along cycle C in
the direction that does not pass through e. So x and y are connected in G − e too.
It follows that an edge e in a connected graph G = (V , E ) is a bridge if and only if e does not lie on a cycle
in G . If e lies on a cycle, then it is not a bridge by the above. If e = (a, b) is not a bridge, then vertices a
and b are still connected in G − e, so there is an ab-path P in G − e. Adding edge e completes path P to a
cycle C in G on which e lies.
Definition 1.3.6. A connected component of G is a maximal connected subgraph of G .
We write c(G ) for the number of connected components of G . A graph is connected if and only if it has one
connected component.
Recall the following result from MATH2230 [Elw20].
Proposition 1.3.7. Let G = (V , E ) be a graph with n vertices and e edges. If G is connected, then e ≥ n−1.

Proof. This proposition follows from Theorem 1.4.3 below, so read that first.
Now let G = (V , E ) be a connected graph with n vertices and e edges. Repeatedly remove edges from cycles
until terminating at a set F ⊆ E of edges such that G − F is connected and acyclic. Then G − F is a tree
with n vertices, so it has n − 1 edges by Theorem 1.4.3. Therefore e = |E | ≥ |E \ F | = n − 1, so e ≥ n − 1
as desired.

One way to understand this proposition is to think that one needs at least n − 1 edges to ‘connect’ n
vertices.
Bipartite graphs can be characterized in terms of the lengths of their cycles.
Theorem 1.3.8. A graph is bipartite if and only if it has no cycles of odd length.

Proof. First suppose that the graph G contains a cycle C of odd length with vertices v0 v1 v2 · · · v2n v0 . Suppose
for a contradiction that G is bipartite with bipartition X , Y , and suppose for the sake of argument that v0 ∈ X .
Then the vertices of C must alternate between X and Y . That is, v2i+1 ∈ Y and v2i+2 ∈ X for all i < n. So
v2n ∈ X . But v0 is also in X , and v2n v0 is an edge. This contradicts that X , Y bipartitions G . So G cannot
be bipartite.
Conversely, suppose that the graph G = (V , E ) does not contain an odd cycle. We define a bipartition X , Y
of G . Do the following on each connected component D of G . Choose any vertex w in D as a base point.
Then for every v ∈ V (D), put v in X if d(w , v ) is even, and put v in Y if d(w , v ) is odd. We show that
X , Y is indeed a bipartition. Suppose for a contradiction that there are u, v ∈ X with (u, v ) ∈ E . The
argument for u, v ∈ Y is analogous. Vertices u and v are in the same connected component, so let w be

11
Chapter 1. Basic notions 1.4. Trees

the base point chosen for that component. For the sake of argument, suppose that d(w , u) ≤ d(w , v ). If
d(w , u) ̸= d(w , v ), then d(w , v ) ≥ d(w , u) + 2 because u and v are in X , so both distances are even. Let
P be a wu-path of length d(w , u). Then wPuv is a wv -walk of length d(w , u) + 1, which contradicts that
d(w , v ) ≥ d(w , u) + 2. Therefore, it must be that d(w , u) = d(w , v ).
Let k = d(w , u) = d(w , v ). Let P be a wu-path of length k, and let Q be a wv -path of length k. Let z
be the last vertex of P that is also on Q. Let ℓ be the length of the path zPu. Then the path wPz has
length k − ℓ. We show that the path zQv also has length ℓ. If zQv has length ℓ′ < ℓ, then wPzQv is a
wv -walk of length (k − ℓ) + ℓ′ < k, contradicting that d(w , v ) = k. If zQv has length ℓ′′ > ℓ, then wQz has
length k − ℓ′′ . In this case, wQzPu is a wu-path of length (k − ℓ′′ ) + ℓ < k, contradicting that d(w , u) = k.
Thus zPu and zQv both have length ℓ. Therefore zPuvQ −1 z is a cycle of length 2ℓ + 1 because zPu and
vQ −1 z each have length ℓ, and uv has length 1. (Q −1 denotes the path Q but traversed in the opposite
direction.) Thus G has a cycle of odd length, which is a contradiction. Therefore (u, v ) cannot be an edge.
This completes the proof.

1.4 Trees
This section will consider trees, which are a special kind of connected graphs. Trees are extremely important
in applications as they allow us to model mathematically a variety of concrete phenomena: think of family
trees, of directory trees of files on a computer, decision trees, etc...
Definition 1.4.1. We say that a graph is a forest if it has no cycles. We say that a graph is a tree if it is
connected and has no cycles.
Example.

T1 T2

Given a tree T , a leaf in T is a vertex of degree 1. The following lemma makes possible many induction
arguments on trees, where we remove leaves.
Lemma 1.4.2. Let G be a tree with n ≥ 2 vertices.
(i) G has at least two leaves.
(ii) If v is a leaf, then G − v is a tree with n − 1 vertices.

Proof.
(i) Consider a maximal path in G , with endpoints u, v . Then as G has no cycles, u ̸= v , and the only
neighbour of u is its neighbour in the path, so u (and likewise v ) is a leaf.
(ii) Observe that v lies on no path containing two other vertices. Hence G − v is connected, and clearly
has no cycles, and has n − 1 vertices.

Recall from MATH2230 the following characterisations of trees [Elw20].

Theorem 1.4.3. Let G be a graph with n ≥ 1 vertices. Then the following conditions are equivalent.
(i) G is a tree.
(ii) G has no cycles and has n − 1 edges.
(iii) G is connected and has n − 1 edges.
(iv) G is connected, and every edge is a bridge.
(v) each pair of vertices in G is connected by a unique path.

12
Chapter 1. Basic notions 1.4. Trees

(vi) G has no cycles, but adding any one edge creates a cycle.

Proof. The theorem is really several theorems put together, so it will take a number of steps to prove.
The first step is to prove by induction on n that a tree with n ≥ 1 vertices has n − 1 edges. For the base case
n = 1, there is only one tree (indeed, only one simple graph) with 1 vertex, and that graph has 0 edges.
Inductively assume that a tree with n ≥ 1 vertices has n − 1 edges. Consider a tree T with n + 1 ≥ 2 vertices.
T has at least one leaf x by Lemma 1.4.2, and removing x produces a tree T − x with n vertices, again by
Lemma 1.4.2. T − x then has n − 1 edges by the inductive hypothesis. Leaf x has degree 1 in T , so removing
x from T only removed one edge. Thus T has n edges. This completes the induction.
We now have that (i)⇒(ii) and (i)⇒(iii) because a tree is acyclic and connected by definition and has n − 1
edges by the above.
For (iii)⇒(i), consider a connected graph G = (V , E ) with n vertices and n − 1 edges. If G has a cycle,
choose an edge e on the cycle and remove it. The resulting graph G − e is still connected because edges on
cycles are not bridges. Repeat this process of removing edges from cycles until terminating at a set F ⊆ E
such that G − F is connected and acyclic. Then G − F is a tree with n vertices, so it has n − 1 edges. But
G had n − 1 edges to begin with, so it must be that F = ∅ and that G = G − F was a tree all along.
For (ii)⇒(i), let G be an acyclic graph with n vertices and n − 1 edges. Let C0 , ... , Ck−1 be the k connected
components of G , for some k. Then each Ci is a tree because it is connected and acyclic. Therefore
e(Ci ) = v (Ci ) − 1 for each i < k, where v (Ci ) and e(Ci ) denote the number of vertices and edges of
component Ci . Every vertex of G appears in exactly one Ci , every edge of G appears in exactly one Ci , there
are n vertices, and there are n − 1 edges. Therefore:
X X
X 
n − 1 = |E | = e(Ci ) = v (Ci ) − 1 = v (ci ) − k = n − k.
i<k i<k i<k

Thus k = 1, which means that G = C0 is connected. Thus G is a connected acyclic graph, so G is a tree.
At this point, we have that items (i), (ii), and (iii) are equivalent.
For (i)⇒(v), suppose that T is a tree, and let x and y be distinct vertices of T . (If x = y , then clearly the
only xx-path is the length 0 path starting and ending at x.) T is connected, so there is at least one xy -path
in T . Suppose for a contradiction that there are two distinct xy -paths

P : x = v0 , v1 , ... , vk = y
Q : x = u0 , u1 , ... , uℓ = y .

The goal is to find a cycle in T , which contradicts that T is a tree. Notice that neither path P nor Q can
be an extension of the other. For example, if Q were an extension of P, meaning that ℓ > k and ui = vi
for all i ≤ k, then Q would not be a path because y would appear on Q twice (at both uk and uℓ ). As
paths P and Q are different, this means there must be a first place where they differ. That is, there is a least
i ≤ min{k, ℓ} such that vi ̸= ui . Note that i > 0 because v0 = u0 = x. Both paths P and Q eventually
meet back up at vk = uℓ = y , so there must be a first place along Q past ui−1 = vi−1 where Q intersects P
past vi−1 = ui−1 . So let j be the least member of {i, i + 1, ... , ℓ} such that uj ∈ {vi , vi+1 , ... , vk }, and let n
be such that uj = vn . Then vi−1 , vi , ... , vn , uj−1 , ... , ui−1 is a cycle in T , which contradicts that T is a tree.
This is the cycle that starts at vi−1 = ui−1 , then follows P to vn = uj , then follows Q back to ui−1 = vi−1 .
Thus there is a unique xy -path in T .
For (v)⇒(iv), assume that G is a graph in which every pair of vertices is connected by a unique path. Consider
an edge e = (x, y ). Then x, y must be the unique path connecting vertices x and y . Therefore x and y must
not be connected in G − e. Therefore e is a bridge in G . Thus G is a connected graph in which every edge
is a bridge.
For (iv)⇒(i), suppose that G is a connected graph in which every edge is a bridge. If G has a cycle, then
none of the edges on the cycles are bridges. Therefore G can have no cycles. Thus G is a connected acyclic
graph, so G is a tree.
We now have that items (i), (iv) and (v) are equivalent and therefore that items (i)–(v) are equivalent.

13
Chapter 1. Basic notions 1.5. Eulerian graphs

For (i)⇒(vi), suppose that T = (V , E ) is a tree, and let x, y ∈ V be distinct vertices where (x, y ) ∈
/ E . T is
connected, so there is an xy -path P in T . Adding edge e then completes P to a cycle. Thus we have shown
that adding any one edge to T creates a cycle.
For (vi)⇒(i), let G = (V , E ) be an acyclic graph with the property that adding any one edge creates a cycle.
We want to show that G is connected. Let x, y ∈ V be distinct vertices. If (x, y ) ∈ E , then x and y are
connected in G by a path of length 1. If (x, y ) ∈ / E , then adding edge (x, y ) creates a cycle C . Label the
vertices around the cycle by starting and ending at x in the direction away from y :
x = v0 , v1 , ... , vn−1 , vn = x
where vn−1 = y . Then (vn−1 , vn ) is the new edge (y , x), and all the other edges are from E . Thus
x = v0 , v1 , ... , vn−1 = y
is an xy -path in G . Thus G is connected. Thus G is a tree because it is connected and acyclic.
We now have that items (i) and (vi) are equivalent and therefore that items (i)–(vi) are equivalent. This
completes the proof.

1.5 Eulerian graphs

Definition 1.5.1. Let G = (V , E ) be a graph. We say that G is an Eulerian graph if G has an Eulerian tour,
i.e. a closed edge sequence that contains every edge of G exactly once.
Example. Consider the graphs G1 and G2 below:

G1 = G2 =

Then G1 is Eulerian and G2 is not.

Lemma 1.5.2. Let G be a graph such that every vertex has degree at least 2. Then G has a cycle.

Proof. Let v be a vertex. We build a path from v0 = v of the form v0 v1 , v1 v2 , ... inductively, as follows. At
each i, choose vi+1 adjacent to vi but not equal to vi−1 . This is always possible, by the degree assumption.
At some stage, since G is finite, there is a repetition of form vi+1 = vj for some j < i − 1, giving a cycle.

Theorem 1.5.3 (Euler, 1736). Let G be a connected graph. Then G is Eulerian if and only if every vertex
has even degree.

Proof. We fix G = (V , E ) a connected graph. We prove the two implications separately.

“⇒” Let P be an Eulerian tour. Recall that every edge of G appears exactly once in P.
Whenever P passes through a vertex, it contributes 2 to its degree. Since every edge occurs exactly once in
P, the degree of every vertex is given by an expression of the form
2 + 2 + ... + 2 ,
and therefore it is even.
“⇐” Assume that each degree is even. We use induction on the number of edges of G . By connectedness,
every vertex has degree at least 2, so by Lemma 1.5.2, G has a cycle C . If C passes through all edges, we are
finished, so suppose it does not. Remove the edges of C to obtain a new graph H, possibly disconnected, but
still with all degrees even. By induction, each component of H has an Eulerian tour. Also, by connectedness
of G , each component of H has at least one vertex in C .
Now build an Eulerian tour for G by going round C until you reach a vertex in a component of H which has
more than one vertex, going round this component on the Eulerian tour of H, then continuing on G to the
next such vertex in a new component, and so on. (For a given component of H, only use its Eulerian tour on
the first time C visits it.)

14
Chapter 1. Basic notions 1.5. Eulerian graphs

Example. We illustrate how the “⇐” direction of the theorem works in an example. Every vertex of the
following graph has even degree:
8

1 9
2
6

4 3

7
5
We have a cycle C = 12, 23, 34, 41. Removing C , we have the graph:
8

1 9
2
6

4 3

7
5
We obtain an Eulerian tour 13, 35, 51, 12, 28, 89, 92, 23, 34, 46, 67, 74, 41 in our original graph.

Example. Euler’s Königsberg’s bridge problem asks whether you can cross each bridge exactly once and
return to the starting point? To model this question mathematically, one is led to consider the graph
C

A D

B
This is not a simple graph, as it has more than one edge between A and B and between A and C . However,
Euler’s theorem remains true also for this kind of graph and thus the answer to the Königsberg Bridge Problem
is negative, as the graph contains a vertex of odd degree.

15
Chapter 1. Basic notions 1.5. Eulerian graphs

16
Chapter 2

Matchings

2.1 Matchings
This chapter deals with the important notion of a matching, which has several interesting practical appli-
cations. In particular, we will state and prove some fundamental results of graph theory, including Berge’s
characterisation of maximum matchings (1957), Hall’s Theorem (1935) and the min-max theorem of König
and Egerváry (1931). The material in this chapter is taken, sometimes verbatim, from [Wes18, Chapter 3],
[AG07, Chapter 10], [CZ12, Chapter 8] and [Die17, Chapter 2].

To begin with, let us give some practical motivation and consider the following problems.

Problem 1. As a result of doing well in an exam, six students Ashley (A), Bruce (B), Charles (C), Duane
(D), Elke (E) and Faith (F) have earned the right to receive a complimentary textbook in either algebra
(a), calculus (c), differential equations (d), geometry (g), history of mathematics (h), programming (p) or
topology (t). There is only one book on each of these subjects. The preferences of the students are

A : d, h, t; B : g , p, t; C : a, g , h; D : h, p, t; E : a, c, d; F : c, d, p.

Can each of the students receive a book he or she likes?

Problem 2. A certain company has five different jobs labelled Ji , where 1 ≤ i ≤ 5, and wants to hire people
for these positions. The seven applicants labelled Aj , where 1 ≤ j ≤ 7 are qualified for some jobs but not for
others. The applicants and the jobs for which they are qualified are as follows:

A1 : J5 , A2 : J1 , J2 , J4 , A3 : J2 , J3 , A4 : J5 , A5 : J2 , J3 , A6 : J5 , A7 : J5

Is it possible for the company to hire qualified applicants for all of its current openings?

The two problems are intuitively similar. In both cases, we are trying to ‘match’ two sets (students with books
or applicants with jobs) according to some constraints (preference and qualifications, respectively). Situations
of this kind can be modelled using bipartite graphs and looking for ‘matchings’ in them, For example, for the
first problem, we draw a graph having a bipartition consisting of the set of students and the set of subjects
and we draw an edge between a student and a subject if the student expressed a preference for a book in that
subject. The graph can be drawn as follows:

A B C D E F

a c d g h t p

17
Chapter 2. Matchings 2.2. Maximum matchings

To solve Problem 1, we need to ‘match’ students to books so that no student gets two books and no book
is given to more than one student and each students gets a book in subject they expresses a preference for.
This amounts to selecting edges in the graph so that no student is the endpoint of more than one edge, no
book appears as the endpoint of more than one edge and every student appears as the endpoint of one of
these edges. This is the idea of a perfect matching, which we will introduce precisely later. We begin with
the more general notion of a matching.
Although a lot of problems regarding matchings concern bipartite graphs, we start by considering more general
graphs.
Definition 2.1.1. Let G = (V , E ) be a graph. A set of edges M is said to be independent if no two elements
in M have an endpoint in common. A matching is an independent set of edges.
Example 2.1.2. Consider the graph G below:
b c
a

d f

e
Then M = {ad, be} is a matching, while N = {ad, bd, ce} is not.
In the next lemma and again further below, we shall make use of the operation of symmetric difference of
two sets A, B, written A△B, defined by
A△B = (A \ B) ∪ (B \ A) .
That is, the elements of A△B are the elements that are in either A or B, but not both. Indeed, we have
A△B = (A ∪ B) \ (A ∩ B). With Venn diagrams, A△B is the shaded area below, where A and B are
represented by two circles:

A B

Lemma 2.1.3. Let G = (V , E ) be a graph. Let M1 , M2 be matchings in G . Then every component of the
symmetric difference M1 △M2 = (M1 \ M2 ) ∪ (M2 \ M1 ) is either a cycle of even length or a path.

Proof. Let F = M1 △M2 . Since M1 and M2 are matchings, every vertex has at most one incident edge in
each of them. Thus, F has at most two edges at each vertex. Since the degree of every vertex of F is at
most 2, every component is either a cycle or a path. Furthermore, every cycle must alternate between edges
of M1 \ M2 and M2 \ M1 . Thus, each cycle has even length.

2.2 Maximum matchings

Definition 2.2.1. Let G = (V , E ) be a graph.
(i) A matching M is maximal if there is no matching M ′ such that M ⫋ M ′ ,
(ii) A matching M is maximum if there is no matching M ′ such that |M| < |M ′ |.
(iii) A matching M is perfect if every vertex of G is the endpoint of an edge in M.
Clearly, a perfect matching is also a maximum matching and a maximum matching is also a maximal matching.
However, a maximal matching is not necessarily a maximum matching and a maximum matching is not
necessarily a perfect matching, as the next examples show.

18
Chapter 2. Matchings 2.2. Maximum matchings

Example.
• For an example of a matching that is maximum but not perfect, see

x1 x2 x3 x4

(2.2.1)

y1 y2 y3

Then M = {x2 y1 , x3 y2 , x4 y3 } is a maximum matching, but it is not perfect. In fact, the graph above
does not have any perfect matching.
• For an example of a matching that is maximal, but not maximum, consider the graph

x1 x3

(2.2.2)

x2 x4

Then M = {x2 x3 } is a maximal matching, since it cannot be extended any further without using an edge
with endpoints different from x2 and x3 . However, it is not a maximum matching since M ′ = {x1 x2 , x3 x4 }
is a matching with strictly more elements. Note how we obtained M ′ from M by replacing the edges of
M with those not in M.
Definition 2.2.2. Let G = (V , E ) be a graph and M be a matching in G .
(i) We say that a path P is M-alternating if it starts at an unmatched vertex and contains, alternately,
edges from E \ M and from M.
(ii) We say that a path P is M-augmenting if it is M-alternating and ends at an unmatched vertex.
Example.
• Consider the graph G and the matching M in (2.2.2). The path P = (x1 x2 x3 x4 ) is M-augmenting.
• More generally, consider the path graph P2n given by

V (P2n ) = {x1 , ... x2n } , E (P2n ) = {xi xi+1 | 1 ≤ i ≤ 2n − 1} .

Thus, P2n can be depicted as

x2n−1
x1

x2 x2n

The following are two maximal matchings for P2n :

M = {x2 x3 , x4 x5 , ... , x2n−2 x2n−1 } , M ′ = {x1 x2 , x3 x4 , ... , x2n−1 x2n } (2.2.3)

Note that
|M| = n − 1 , |M ′ | = n .
In both of these, the edges are alternatively contained in the matching or not. The path P = (x1 , ... , x2n )
is M-augmenting.
We use augmenting paths to characterise maximum matchings.
Theorem 2.2.3 (Berge, 1957). Let G = (V , E ) be a graph and M a matching in G . Then the following are
equivalent:
(i) M is a maximum matching.

19
Chapter 2. Matchings 2.2. Maximum matchings

(ii) There is no M-augmenting path in G .

Proof. We prove the equivalence between the following statements:

(i)’ There exists a matching M ′ such that |M| < |M ′ |.

(ii)’ There exists an M-augmenting path in G .

(i)’ ⇒ (ii)’. Let M ′ be a matching such that |M| < |M ′ |. We construct an M-augmenting path as follows.
Let
F = M△M ′ = (M ′ \ M) ∪ (M \ M ′ ) = (M ∪ M ′ ) \ (M ∩ M ′ ).

Since |M| < |M ′ |, the graph F must have a component with more edges of M ′ than of M. Indeed, if all the
components of F had the same number of edges of M and M ′ , then F would have the same number of edges
of M and M ′ , but then M and M ′ would have the same number of elements, which is a contradiction to our
assumption that |M| < |M ′ |.

The graph F is made of cycles of even length and paths by Lemma 2.1.3. Since the cycles of even length
must have the same number of edges of M and M ′ , the only possibility is that there is a path with more
edges of M ′ than of M, say

xn−2 xn−1 xn
x1 x2 x3
···

Since M and M ′ are matchings, the edges in the path must be alternating between them. Thus, the only way
for such a path to have more edges of M ′ than of M is to start and ends with edges in M ′ . So we have an
M-augmenting path, as required.

(ii)’ ⇒ (i)’. Suppose that there is an M-augmenting path P in G , say

xn−1
x1 x3

P= ···

x2 xn−2 xn

Here, the thicker edges (such as x2 x3 and xn−2 xn−1 ) are in M. We use P to define a new matching M ′ by
letting M ′ be the symmetric difference of M and P, i.e.

M ′ = M△P = (P \ M) ∪ (M \ P) = (M ∪ P) \ (M ∩ P) .

We can describe M ′ more explicitly. It has some edges that are in P (given by P \ M) and some that are not
(given by M \ P). The edges of M ′ that are in P are exactly the edges of P that are not in M (such as x1 x2
and xn−1 xn ). The edges of M ′ outside P are precisely the same as the edges of M that are not in P. In other
words, M ′ looks like the complement of M inside P (and in particular M ′ contains the initial and final edge
of P) and it is the same as M elsewhere.

The set M ′ is again a matching (for this, observe that no vertex can be the endpoint of two edges in M ′ ,
recalling that that x1 and xn are unmatched, as P is M-augmenting) and the set of edges has increased by
one (inside P we gained one edge and outside P we mantained the same number). Thus |M ′ | = |M| + 1, as
required.

Checking that a matching M is maximum using theorem 2.2.3 is somewhat inconvenient, as we need to
inspect all possible paths and check that none of them is M-augmenting. For this reason, it is desirable to
have ways of knowing what is the size of a maximum matching in a graph. We will develop some results to
help us in this task in the special case of bipartite graphs, which we consider next.

20
Chapter 2. Matchings 2.3. Matchings in bipartite graphs

2.3 Matchings in bipartite graphs

As from now on we shall be particularly interested in matching in bipartite graphs, so let us unfold more
explicitly what a matching is in such graphs. Let G = (V , E ) be a bipartite graph, with bipartition X , Y . A
matching in G is a set
M = {x1 y1 , ... , xk yk }
where xi yi are edges (for 1 ≤ i ≤ k), the xi ’s are distinct elements of X and the yj ’s are distinct elements of
Y . In this situation, we say that M matches the set {x1 , ... , xk } to the set {y1 , ... , yk }. Note that {x1 , ... , xk }
and {y1 , ... , yk } need not be the whole of X and Y , respectively.
Example 2.3.1. We give some examples of matchings in bipartite graphs.
(i) The matching M = {x1 y2 , x3 y1 } in the bipartite graph

x1 x2 x3

y1 y2 y3 y4

(ii) The matching in (2.2.1), as the graph is bipartite, with X = {x1 , x2 , x3 , x4 } and Y = {y1 , y2 , y3 }.
(iii) The matching in (2.2.2), as the graph is bipartite with X = {x1 , x3 } and Y = {x2 , x4 }.
(iv) The matchings in 2.2.3, as the graph therein is bipartite with X = {x2i−1 | 1 ≤ i ≤ n} and Y =
{x2i | 1 ≤ i ≤ n}.
The notion of a perfect matching has a kind of ‘dual’, known as a vertex cover, which we define next.
Definition 2.3.2. Let G = (V , E ) be a graph. A set of vertices U ⊆ V is said to be a vertex cover of G if
every edge of G has at least one endpoint in U.
In a graph representing a road network, a vertex cover can be thought of as a set of locations that allow
us to watch every road. Thus, it is an interesting question to find the minimum number of elements that a
vertex cover can have. As the next theorem shows, this is also directly relevant for our study of maximum
matchings.
Theorem 2.3.3 (König 1931, Egerváry 1931). Let G be a bipartite graph. Then the maximum size of a
matching in G equals the minimum size of a vertex cover in G .

Proof. Let G have bipartition X , Y . Consider a vertex cover U and a matching M. Since a vertex cover must
contain at least one endpoint for each edge in M and these need to be all distinct (as M is a matching),
|M| ≤ |U|. Since M and U are arbitrary, the maximum size of a matching in G is less or equal to the minimum
size of a vertex cover in G .
Let us now consider a matching M of maximum cardinality. We shall construct a vertex cover U such that
|M| = |U|, thus showing that the required equality holds. We define the set U according to the following
rule: for every edge xy ∈ M, with x ∈ X and y ∈ Y ,


 y ∈ U, if there exists an M-alternating path starting in X
and ending with y ,



x ∈ U, otherwise.


Clearly, the elements of U are in bijective correspondence with elements of M and so |M| = |U|, as required.
It now remains to show that U is a vertex cover of G . In order to do this, let us first observe that if P is an
M-alternating path starting in X that ends with y ∈ Y , then y ∈ U. Indeed, since M is maximum, P cannot
be M-augmenting by theorem 2.2.3. So its final vertex y has to be matched to some x by some edge xy ∈ M
(note that xy is not in P). But, according to the definition of U, when we consider the edge xy ∈ M, we let
y ∈ U since there exists an M-alternating path starting in X and ending with y , namely P.
To show that U covers G , let xy ∈ E . We need to show that either x ∈ U or y ∈ U. If x ∈ U, we are done.
If x ∈
/ U, we show y ∈ U. For this, it suffices to show that there is some M-alternating path starting in X

21
Chapter 2. Matchings 2.4. Hall’s matching theorem

and ending with y . If x is unmatched by M, then xy is such a path. If x is matched, there is some y ′ ∈ Y
such that xy ′ ∈ M. Since x ∈/ U, there is an M-alternating path P ending with y ′ , say

P = (y1 y2 ... yk )

with yk = y ′ . We now distinguish two cases, depending on whether y ∈ P or y ∈ / P and show that in both
cases there is an M-alternating path ending with y . If y ∈ P, i.e. there is 1 ≤ i ≤ k such that yi = y , then
y1 ... yi is an M-alternating path ending in y , as required. If y ∈
/ P, then

(y1 y2 ... yk xy )

is an M-alternating path (note that yk x = y ′ x ∈ M and xy ∈

/ M since M is a matching) ending in y .

Example 2.3.4. Consider the following graph G = (V , E ), with bipartition X = {x1 , ... , x5 } and Y =
{y1 , ... , y4 }.
x1 x2 x3 x4 x5

y1 y2 y3 y4

This graph has a maximum matching M = {x1 y1 , x2 y2 , x3 y3 , x4 y4 }. Then, the vertex cover U constructed in
the proof of Theorem 2.3.3 is U = {x1 , x2 , y3 , y4 }. Indeed, inspecting the edges in M, we have:
• for x1 y1 , x1 ∈ U since there is no M-alternating path ending in y1 ,
• for x2 y2 , x2 ∈ U since there is no M-alternating path ending in y2 ,
• for x3 y3 , y3 ∈ U since x5 y4 x4 y3 is an M-alternating path,
• for x4 y4 , y4 ∈ U since x5 y4 is an M-alternating path.
Remark 2.3.5. Theorem 2.3.3 is an example of a ‘min-max’ theorem, in which the maximum over a set is
shown to be equal to the minumum of another, dual, set. We will encounter other examples of such results
in the module.

2.4 Hall’s matching theorem

We now examine the question of whether a bipartite graph can have a maximum matching, thus allowing us
to solve problems like Problem 1 and Problem 2 in Section 2.1. Recall that, for a graph G = (V , E ) and a
vertex x ∈ V , we write N(x) for the set of neighbours of x and extend this notation to subsets S ⊆ V by
letting N(S) be the union of the sets of neighbours of the elements of S.
Let us now fix a bipartite graph G = (V , E ) with bipartition X , Y and suppose that |X | ≤ |Y |. First of all,
observe that a matching of size |X | establishes a bijection between the vertices of X and some vertices of Y .
Thus, it is a maximum matching. Secondly, observe that if such a matching exists, then

|S| ≤ |N(S)|, for every S ⊆ X . (2.4.1)

Indeed, for S ⊆ X , the edges in the matching with endpoints in S have other endpoints necessarily distinct
elements of Y . Thus, the condition in (2.4.1) is a necessary condition for a matching of size |X | to exist.
Thus, if it fails, we know that no such matching can exist. Hall’s Theorem, below, shows that this is also a
sufficient condition, i.e. that if (2.4.1) holds, then a matching of size |X | exists.
Theorem 2.4.1 (Hall’s Theorem). Let G = (V , E ) be a bipartite graph with bipartition X , Y . Suppose that
|X | ≤ |Y | and let k = |X |. Then, the following conditions are equivalent.
(i) There is a maximum matching of G of size k.
(ii) For every S ⊆ X , |S| ≤ |N(S)|.

22
Chapter 2. Matchings 2.4. Hall’s matching theorem

Proof. We have already shown (i) ⇒ (ii). So we only need to show (ii) ⇒ (i). We show that the minimum
size of a vertex cover of G is |X |. By Theorem 2.3.3, this will imply that the maximum size of a matching is
|X |, as required. By contradiction, suppose that there is a vertex cover U with |U| < |X |. Let X ′ = X ∩ U
and Y ′ = Y ∩ U. We have U = X ′ ∪ Y ′ and thus

|X ′ | + |Y ′ | = |U|.

Since |U| < |X |, we obtain

|Y ′ | < |X | − |X ′ | = |X \ X ′ |
The neighbours of the vertices in X \ X ′ must be in Y ′ , as U is a vertex cover. But then

|N(X \ X ′ )| ≤ |Y ′ | < |X \ X ′ |

in contradiction to the our assumption (ii).

Corollary 2.4.2. For k > 0, every k-regular bipartite graph has a perfect matching.

Proof. Let G be a regular k-bipartite graph, with bipartition X , Y . We claim that |X | = |Y |. This follows
from k|X | = k|Y |, which in turn follows by counting the number of edges of G in two ways: by counting the
edges by either their endpoints in X or by their endpoints in Y . If we satisfy the condition in Hall’s Theorem,
we will obtain a maximum matching of size |X |, thus giving us a perfect matching for G .
So let S ⊆ X . Let A be the the set of edges from S to N(S), and let B be the set of edges incident to N(S).
Clearly, A ⊆ B, so |A| ≤ |B|. Since G is k-regular, |A| = k|S| and |B| = k|N(S)|. Thus, k|S| ≤ k|N(S)|,
which gives |S| ≤ |N(S)|, as required.

23
Chapter 2. Matchings 2.4. Hall’s matching theorem

24
Chapter 3

Connectivity

3.1 Connectivity
This chapter is devoted to investigating the idea of connectivity of a graph, which can be informally described
as a measure of how connected a graph is. The material in this chapter is taken, sometimes verbatim,
from [Wes18, Chapter 4], [Wil10, Chapter 6], [Die17, Chapter 3], [CZ12, Chapter 5].

Let us begin with some practical motivation. Think of a communication network (telephone lines, Internet,
etc.). We want the network to be fault-tolerant, i.e. to remain functioning (i.e. connected) even if some of
its nodes (i.e. vertices) fail. Since communication lines (i.e. edges) may be expensive or difficult to repair, it
is desirable to achieve this goal with the least number of edges. Intuitively, this is somehow related to the
number of possible disjoint paths between two vertices. As we will see in Whitney’s Theorem (Theorem 3.2.2)
and Menger’s Theorem (Theorem 3.4.6), this intuition is correct and the number of vertices that can fail
without affecting the network and the number of possible disjoint paths between two vertices are intimately
related.
Definition 3.1.1. Let G = (V , E ) be a graph and k ≥ 1. We say that G is k-connected if the following
conditions hold:
(i) |V | > k,
(ii) for every S ⊆ V with |S| < k, the graph G − S is connected.
More informally, a graph is k-connected if removing fewer than k vertices does not disconnect it. Equivalently,
a graph is k-connected if no two vertices can be separated by less than k vertices. Let us consider what k-
connected means explicitly for k = 1, 2.
• For k = 1, to say that a graph is 1-connected is to say that removing zero vertices results in a connected
graph. This amounts to saying that G is connected.
• For k = 2, to say that a graph G is 2-connected is to say that removing either zero or one vertex from
it results in a connected graph, i.e. not only that G is connected, but also that G − v is connected for
every v ∈ V .
Thus, the higher the number k is, the ‘more connected’ a graph is. This motivates us to introduce to define
the connectivity of G , written κ(G ), as

κ(G ) = max{k | G is k-connected} .

Example 3.1.2.
• If G is a tree with at least 3 vertices, then κ(G ) = 1.
• If G is cycle then κ(G ) = 2.
• κ(Kn ) = n − 1.

25
Chapter 3. Connectivity 3.2. A characterisation of 2-connected graphs

3.2 A characterisation of 2-connected graphs

We now look more closely at 2-connected graphs. Recall that a graph G is 2-connected if it has more than
2 vertices, it is connected and G − w is connected for every vertex w . Now consider two vertices u, v of G .
Since G is connected, there is at least one uv -path. But since removing a vertex w of this path from G results
in a graph G ′ = G − w that is still connected, there is also a uv -path in G ′ . But this means that there must
have been another uv -path in G . As we will see, this idea leads to a characterisation of 2-connected graphs,
known as Whitney’s Theorem (theorem 3.2.2 below). In section 3.4, we will prove Menger’s theorem which
generalises Whitney’s theorem to an arbitrary k. In order to state Whitney’s Theorem, we need the following
definition.
Definition 3.2.1. Let G = (V , E ) a graph. Let u, v ∈ V . We say that two uv -paths are internally disjoint
if they have no internal common vertex, i.e. no common vertex other than their endpoints u and v .
Theorem 3.2.2 (Whitney). Let G = (V , E ) be a graph with at least three vertices. Then the following are
equivalent:
(i) G is 2-connected,
(ii) For every u, v ∈ V , there exist two internally disjoint uv -paths in G .
(iii) For every u, v ∈ V , there exists a cycle in both u and v lie.

Proof. The equivalence of (ii) and (iii) is clear, so we only prove the equivalence of (i) and (ii). We prove
the two implications separately.
For one implication, let us assume that for any two vertices of G there exist two internally disjoint paths
between them. and show that G is 2-connected. For this, we consider w ∈ V and show that G − w is
connected. So let u, v be two distinct vertices of G − w . There are two internally disjoint paths between
them in G , and therefore still lie in the same component of G − w , as removing w destroys at most one of
these two paths.
For the converse implication, let us assume that G is 2-connected and show for any two vertices u, v of G
there exist 2 internally disjoint paths in G from u to v . We do this by induction on d(u, v ), the distance
between u and v .
• Base case: d(u, v ) = 1. Then e = uv is an edge, but it is not a bridge by 2-connectedness of G . So
there exists a uv -path P not using e. Thus P and e give two disjoints uv -paths.
• Inductive step. Let d(u, v ) ≥ 2 and assume that the result holds for pairs at smaller distance. Let P be a
uv -path of length d(u, v ), and suppose that w immediately precedes v on P. Since d(u, w ) < d(u, v ),
by the induction hypothesis there are two internally disjoint uw -paths, say P1 and P2 . Since G is
2-connected, G − w is connected and therefore there is a uv -path Q in G − w .
Let z be the last vertex of Q that is in either P1 or P2 . Such z exists since u is in both P1 and Q
(as well as in both P2 and Q). We may suppose z ∈ P1 (the case z ∈ P2 is analogous). We can now
construct the two required internally disjoint uv -paths in G , as follows:
– a uz-path using P1 followed by a zv -path using Q,
– a uw -path using P2 followed by the edge wv
(or the uv portion of P2 if v already appears on P2 ).
These are internally disjoint, since P1 and P2 are disjoint, Q is a path in G − w and, and the zv -path
in Q does not intersect either P1 or P2 (as z was the last vertex that Q had in common with either of
them).

3.3 Cut-vertices and blocks

Just as we can decompose a graph into connected components (i.e. its maximal 1-connected subgraphs),
we could try to decompose a connected graph (i.e. a 1-connected graph) into its maximal 2-connected
subgraphs. However, maximal 2-connected subgraphs need not be disjoint or cover the whole of the graph
(since a 2-connected graph needs to have more than 2 elements, we would not account for isolated vertices
and bridges). Thus, we need to generalise the notion of a maximal 2-connected subgraph in order to allow

26
Chapter 3. Connectivity 3.3. Cut-vertices and blocks

such a decomposition. The appropriate notion is that of a block, introduced in Definition 3.3.2 below. As we
will see, blocks provide an approximation of the structure of a graph, as we will see in Theorem 3.3.7.
Definition 3.3.1. Let G = (V , E ) be a graph. We say that a vertex v ∈ V is a cut-vertex of G if C − v is
disconnected, where C is the connected component of G containing v .
Thus, in a connected graph G , a cut-vertex is a vertex v such that G − v is disconnected. We can then
rephrase the definition of a 2-connected graph equivalently by saying that a graph G is 2-connected if it has
more than 2 vertices, it is connected and has no cut-vertices.
Definition 3.3.2. Let G be a graph. We say that a subgraph B of G is a block of G if the following hold:
(i) B is a subgraph of G that, as a graph on its own, is connected and has no cut-vertex;
(ii) B is maximal among such subgraphs of G . More precisely, if B ′ is a subgraph of G that, as a graph on
its own, is connected, has no cut-vertex, and B ⊆ B ′ , then B = B ′ .
Note that condition (ii) in Definition 3.3.2 can be stated equivalently as saying that there is no subgraph B ′
of G that, as a graph on its own, is connected, has no no cut-vertex and B ⊊ B ′ . In other words, a subgraph
B is a block if, as a graph on its own, it is connected, has no no cut-vertex, and extending B to a larger
subgraph leads to a subgraph that either is disconnected or has a cut-vertex.
Example 3.3.3. In the example below, A, B, C , D, E are blocks:

C D E
A

Consider for example the subgraph C . As a graph on its own, it is clearly connected and does not contain
any cut-vertices. We can try to extend C and create a larger subgraph C ′ in essentially two ways. If we add
a vertex that is adjacent to one of the two vertices in C , then that vertex of C becomes a cut-vertex for C ′ .
If we add a vertex that is not adjacent to either of the two vertices in C , then C ′ is disconnected (unless we
also add more vertices and edges, in which case we end up in the first case). So C is a block.
Proposition 3.3.4. Let G be a graph. A subgraph of G is a block if and only if it has one of the following
three forms:
(i) an isolated vertex of G ;
(ii) a bridge of G ;
(iii) a maximal 2-connected subgraph of G with at least 3 vertices.

Proof. We leave as an exercise to show that isolated vertices, bridges and maximal 2-connected subgraphs
with at least 3 vertices are blocks. We prove the other implication. Let B be a block. We distinguish three
cases depending on whether V (B) has 1, 2 or at least 3 vertices. If V (B) = {v }, then v has no neighbour
in G , for if u, v are adjacent then the edge uv is connected with no cut-vertex, contradicting maximality of
B. If V (B) = {u, v }, then u, v are adjacent and uv does not lie on any cycle so is a bridge. If |V (B)| ≥ 3,
then for any w ∈ V (B), as B is connected and w is not a cut-vertex of B, B − w is connected, so B is
2-connected. Since a 2-connected graph has no cut-vertex, B is maximal 2-connected.

Now, just as we can decompose a graph into connected components, we can decompose a graph into blocks.
As it turns out, cut-vertices and blocks of a graph G can be organised in an interesting mathematical
structure of its own: a graph! We define block graph of G as the bipartite graph BL(G ) with vertices X ∪ Y ,
where
X = {v | v is a cut-vertex of G } Y = {B | B is a block of G },
and with edges vB if and only if v ∈ B.

Example 3.3.5. Consider the graph G with blocks A1 ... A6 , given as follows:

27
Chapter 3. Connectivity 3.3. Cut-vertices and blocks

A6
A1

x2 x3
x1

A2 A5

x4
A3

A4

Then its block graph BL(G ) is given as follows:

A1
x1

A2

x2
A3

A4
x3

A5
x4
A6

We want to show that a block graph is a tree (Theorem 3.3.7). The next lemma provides all the necessary
ingredients.

Lemma 3.3.6.

(i) Let G be a graph and B1 , B2 distinct blocks in G . Then B1 and B2 they share at most one vertex,
which is a cut-vertex of G .

(ii) Let G be a graph. Every edge of G lies in a unique block of G .

(iii) G is the union of its blocks.

(iv) The cycles of G are precisely the cycles of its blocks.

Proof.

(i) Suppose B1 , B2 have two common vertices u, v . We will show that B1 ∪ B2 is connected with no
cut-vertices, contradicting maximality of B1 and B2 . Connectedness is clear. To show that it has no
cut-vertex, let w ∈ V (B1 ∪ B2 ) and show that (B1 ∪ B2 ) − w is connected. We may suppose that u ̸= w
(as otherwise we could use v instead of u in the ensuing argument). For any vertex x ∈ V (B1 )\{w },
there is an xu-path in B1 − w . Likewise, for any vertex y ∈ V (B2 )\{w } there is a yu-path in B2 − w .
Hence, for any x ∈ V (B1 )\{w } and y ∈ V (B2 )\{w } there is an xy -path in (B1 ∪ B2 ) − w . This easily
implies connectedness of (B1 ∪ B2 ) − w .

For the second claim, suppose u is the unique vertex of B1 ∩ B2 . We show u is a cut-vertex of G . Now
B1 ∪ B2 is connected, but not a block, so it has a cut-vertex of itself, which must be u. If u is not a
cut-vertex of G there is a path P in G between B1 and B2 not going via u, and B1 ∪ B2 ∪ P is connected
with no cut-vertex, contradicting maximality of B1 and B2 .

28
Chapter 3. Connectivity 3.3. Cut-vertices and blocks

(ii) Let e be an edge. We distinguish two cases, depending on whether e is a bridge or not. If e is a bridge
it is a block. If e is not a bridge, it lies on a cycle, which is connected and has no cut-vertices, so is
contained in a block. In either case, by part (i), e lies in at most one block.
(iii) Every isolated vertex lies in this union by Proposition 3.3.4. Every vertex which is not isolated and every
edge lie in this union by part (ii).
(iv) If a cycle is in a block then clearly the cycle is in G ; the difficult part is to prove that every cycle in
G is contained in one block. Suppose v1 , v2 , ... , vs , v1 is a cycle C of G . The vertices v1 and v2 and
the edge v1 v2 must lie in a single block by part (ii), which we’ll call B. B ∪ C contains no cut-vertex,
because B contains no cut-vertex and cycles are 2-connected. Also, it is clear that B ∪ C is connected.
Therefore, by maximality of blocks, C is contained in B.

Theorem 3.3.7. Let G be a graph. If G is connected, then its block graph BL(G ) is a tree.

Proof. We first show that BL(G ) is connected. If G consists of a single block B, then G has no cut-vertices
and BL(G ) is the trivial graph with exactly one vertex, which is connected. If G has multiple blocks, then
every block contains at least one cut-vertex. This is because G is connected, so if B is a block that is not all
of G , then there is an edge (x, y ) where x is in B and y is not. However, edge (x, y ) must lie in some other
block B ′ by Lemma 3.3.6 item (ii). Thus x is in both blocks B and B ′ , so x is a cut-vertex by Lemma 3.3.6
item (i). Thus every block is adjacent to some cut-vertex in BL(G ). Therefore, to show that BL(G ) is
connected, it suffices to show that for any two distinct cut-vertices x and y of G , there is an xy -path in
BL(G ).
Let x and y be distinct cut-vertices of G . We show that there is an xy -path in BL(G ) by induction on the
distance dG (x, y ) between x and y in G . The base case is dG (x, y ) = 1, meaning that (x, y ) is an edge of
G . Then there is a block B containing x and y by Lemma 3.3.6 item (ii), so x B y is an xy -path in BL(G ).
This completes the base case. Inductively assume that, for all pairs of distinct cut-vertices a and b in G ,
if dG (a, b) ≤ n, then a and b are connected in BL(G ). Consider distinct cut-vertices x and y in G with
dG (x, y ) = n + 1. Let

P: x = v0 v1 · · · vn vn+1 = y

be an xy -path of length n + 1 in G .
If no internal vertex vi for 1 ≤ i ≤ n is a cut-vertex of G , then all vertices of the path (including x and
y ) must be in the same block B. This is because P can only transition between blocks at cut-vertices. For
example, if edges (vi , vi+1 ) and (vi+1 , vi+2 ) were in different blocks, then vertex vi+1 would be in two different
blocks and so would have to be a cut-vertex. In particular, x and y are in the same block B, so x B y is an
xy -path in BL(G ).
Suppose instead that an internal vertex vi for some 1 ≤ i ≤ n is a cut-vertex of G . Then we can apply the
induction hypothesis to Pvi (the initial segment of P up to vi ) and to vi P (the final segment of P starting at
vi ) because both of these paths have length ≤ n. The induction hypothesis yields that x is connected to vi
in BL(G ) and that vi is connected to y in BL(G ). Therefore x is connected to y in BL(G ) too, as desired.
Now we show that BL(G ) is acyclic. Suppose for a contradiction that

C: x0 B0 x1 · · · xn Bn x0

in BL(G ). Notice that the cycle must have length at least 4 (i.e., n ≥ 1) because BL(G ) is bipartite.
is a cycle S
Let H = i≤n Bi be the subgraph of G induced by the union of the blocks appearing in C . It is not difficult
to see that H is connected via the xi for i ≤ n. We show that H has no cut-vertex when considered as a
graph on its own. Let w ∈ V (H). Then w ∈ V (Bi ) for some i ≤ n. To make the ensuing argument more
convenient, relabel the xi and Bi for i ≤ n as

C: y0 A0 y1 · · · yn An y0

in such a way so that w ∈ v (A0 ) and w ̸= y1 . (That is, take A0 = Bi , y0 = xi , A1 = Bi+1 , y1 = xi+1 , and
so on around the cycle. If w = xi+1 , instead relabel the cycle in the opposite direction by taking A0 = Bi ,
y0 = xi+1 , A1 = Bi−1 , y1 = xi , A2 = Bi−2 , and so on.) Let a, b ∈ V (H) \ {w }. We may assume (by swapping
a and b if needed) that a ∈ V (Ai ) and b ∈ V (Aj ) for some i ≤ j. Note that A0 − w is connected because
A0 is a block. Now let

29
Chapter 3. Connectivity 3.4. Menger’s theorem

• P be an ayi+1 -path in Ai (in Ai − w if i = 0);

• Qk be a yk yk+1 -path in Bk for all i < k < j;
• R be a yj b-path in Aj (in Aj − w if j = 0).
Then

a P yi+1 Qi+1 yi+2 · · · yj−1 Qj−1 yj R b

is an ab-walk in H − w . This walk starts at a, follows path P to yi+1 , then follows path Qi+1 to yi+2 , and
so on until finally following path R to b. Thus a and b are connected in H − w . This shows that H − w is
connected, so w is not a cut-vertex of H. Thus H has no cut-vertices. Ultimately, this contradicts that the
Bi for i ≤ n are blocks because they are all contained in the strictly larger subgraph H that is connected and
has no cut-vertices. Therefore there can be no such cycle C , so BL(G ) is acyclic.

3.4 Menger’s theorem

We now return to the question, mentioned in the Introduction, of finding out information on graphs that
represent fault-tolerant communication networks, i.e. in which removing a certain number of vertices does
not disconnect the graph. Such results amount to characterisations of k-connected graphs, extending the
characterisation of 2-connected graphs in Whitney’s Theorem (theorem 3.2.2).
We conclude this chapter with Menger’s theorem, which provides a characterisation of k-connected graphs.
This is a central result in Graph Theory, which can be used to derive Hall’s theorem (although we will not
see this). We give an expanded version of the proof in [Gör00], which is probably the shortest of the many
known proofs (6 lines in the published version!), using also [Die17, Doc19]
Definition 3.4.1. Let G = (V , E ) be a graph. Let A, B ⊆ V .
• An AB-path is a path with start point in A and endpoint in B.
• We say that two AB-paths are disjoint if they have no vertices in common.
• We say that a subset S ⊆ V is an AB-separator if every AB-path contains a vertex in S.
Note that in Definition 3.4.1 we do not allow AB-disjoint paths to have any vertex in common, not even
their endpoints. Thus, for A = {u} and B = {v }, this is a different, more restrictive, notion than that of
internally disjoint paths given in Definition 3.2.1. Also note that, since we allow paths consisting of a single
vertex, A ∩ B ⊆ S for every AB-separator S. The following result was proved by Menger in 1927.
Theorem 3.4.2 (Menger’s Theorem for sets of vertices). Let G = (V , E ) be a graph and A, B ⊆ V . Then
the minimum number of vertices of an AB-separator equals the maximum number of disjoint AB-paths.

Proof. Throughout the proof, let k be the minimum number of elements of an AB-separator in G . Clearly,
an AB-path meets an AB-separator in at least one vertex and disjoint AB-paths meet an AB-separator in
distinct vertices, so the maximum number of disjoint AB-paths is at most k. Thus, the claim follows once
we show that there are k disjoint AB-paths in G .
We prove this by induction on the number of edges in G . The base case is when G has no edges. In this
case, the minimum AB-separator is A ∩ B, so k = |A ∩ B|. The elements of A ∩ B then provide also k disjoint
AB-paths in G , as required.
For the induction step, let e = (x, y ) be an edge in G and consider the graph G ′ = G − e. We distinguish
two cases. If the minimum number of elements of an AB-separator in G ′ is also k, then by the induction
hypothesis there exist k disjoint AB-paths in G ′ and hence in G , so we are done. If instead there is an
AB-separator S in G ′ with fewer than k elements, we will use S to construct k disjoint paths in G . For this,
let us define Sx = S ∪ {x} and Sy = S ∪ {y }.

Claim 1. The sets Sx and Sy are AB-separators in G .

Proof of Claim 1. Consider an AB-path P in G . If P uses edge e = (x, y ), then P contains both x and y
and so meets both Sx and Sy . If P does not use e, then P is an AB-path in G ′ and hence meets S and hence
also meets of both Sx and Sy .

30
 Chapter 3. Connectivity 3.4. Menger’s theorem

Claim 1 implies that |S| = k − 1 and that |Sx | = |Sy | = k. This is because |S| < k, but adding either vertex x
or vertex y yields AB-separators Sx and Sy in G , each of which must have at least k vertices by assumption.
Claim 2. In G ′ − S, exactly one of the following two cases hold.
Case (x → y ): Vertex x is connected to A but not to B; and vertex y is connected to B but not to A.
Case (y → x): Vertex x is connected to B but not to A; and vertex y is connected to A but not to B.

Proof of Claim 2. The set S is not an AB-separator in G because |S| < k and AB-separators in G have at
least k vertices. Therefore there is an AB-path P in G − S. However, path P must use edge e = (x, y ). If
not, then P would be an AB-path in G ′ − S, which cannot exist because S is an AB separator in G ′ = G − e.
Suppose that P traverses edge e in the x → y direction (that is, x immediately precedes y on P). Then the
segment Px (stopping at x) connects x to A in G ′ − S, and the segment yP (starting at y ) connects y to B
in G ′ − S. Furthermore, there can be no path Q starting at x and ending in B in G ′ − S because otherwise
PxQ would be an AB-walk in G ′ − S, which contradicts that S is an AB-separator in G ′ − S. Similarly, there
can be no path R starting at y and ending in A in G ′ − S. Thus we are in case (x → y ).
If P traverses edge e in the y → x direction (that is, y immediately precedes x on P), then a symmetric
argument shows that we are in case (y → x).

For the rest of the argument, we assume that we are in Case (x → y ) of Claim 2. The argument in Case
(y → x) is symmetric.
Claim 3.
• Every ASx -separator in G ′ is an an AB-separator in G .
• Every Sy B-separator in G ′ is an AB-separator in G .

Proof of Claim 3. Both items are proved in the same way, so we only show that every ASx -separator in G ′ is
an an AB-separator in G . Thus let D be an ASx -separator in G ′ . We want to show that it is an AB-separator
in G . Let P be an AB-path in G . By Claim 1, Sx is an AB-separator in G , so P meets Sx . Let w be the first
vertex on P that is in Sx . Vertex y cannot lie on the segment Pw as otherwise the segment would connect
y to A in G ′ − S, which cannot happen because we are in Case (x → y ). This means that segment Pw does
not use edge e and therefore that Pw is an ASx -path in G ′ = G − e. The set D is an ASx -separator in G ′ ,
so Pw meets D. Thus P meets D. Therefore D is an AB-separator in G .

(Beware that if we are in Case (y → x) of Claim 2, then the roles of Sx and Sy swap in Claim 3. In this case,
Claim 3 says that every ASy -separator in G ′ is an an AB-separator in G , and that every Sx B-separator in G ′
is an AB-separator in G .)
It follows from Claim 3 that the minimum number of elements of an ASx -separator and of an Sy B-separator
in G ′ is at least k, which we assumed to be the minimum number of elements of an AB-separator in G . Thus,
by the induction hypothesis, there is a collection P of k disjoint ASx -paths in G ′ and a collection Q of k
disjoint Sy B paths in G ′ . Furthermore, no path of P meets any path of Q outside of S because this would
produce an AB-walk in G ′ − S, which contradicts that S is an AB-separator in G ′ . As |Sx | = |Sy | = k (see
the comment following Claim 1), for every s ∈ Sx there is a path P in P that ends at s; and for every s ∈ Sy
there is a path Q in Q that starts at s. We can now construct our k disjoint AB-paths in G as follows. For
each s ∈ S, let P be the path of P ending at s, let Q be the path of Q starting at s, and join them to create
the AB-path PsQ. This gives k − 1 disjoint paths. For the k th path, let P be the path of P ending at x, let
Q be the path of Q starting at y , and use edge e = (x, y ) to join them to the AB-path PxyQ.

Remark 3.4.3. If we try to apply Theorem 3.4.2 directly to A = {u} and B = {v }, where u, v ∈ V , we do
not get much information. Indeed, the maximum number of disjoint {u}{v }-paths is either 1 or 0, depending
on whether u and v are connected or not, respectively. This is because two {u}{v }-paths necessarily share
the endpoints u and v and therefore cannot be disjoint. Similarly, the minimum number of elements of a
{u}{v }-separator is either 1 or 0, depending on whether u and v are connected. Indeed, if they are connected
we can take S = {u} or S = {v }, while if they are not then S = ∅ is a {u}{v }-separator, since there is no
{u}{v }-path.

31
Chapter 3. Connectivity 3.4. Menger’s theorem

In order to get more information on the case A = {u} and B = {v }, we need to make additional restrictions
on the side of the paths, considering only internally disjoint paths (in the sense of definition 3.2.1), and on
the side of separators, not allowing u and v to be used. To make this precise, let us introduce the following
definition.
Definition 3.4.4. Let G = (V , E ) be a graph. Let u, v ∈ V . We say that a subset S ⊆ V is a uv -separator
if S is a {u}{v }-separator but u, v ∈
/ S.
More explicitly, a subset S ⊆ V is a uv -separator if u, v ∈
/ S and every uv -path contains a vertex in S. With
this definition in place, we can prove a counterpart of Theorem 3.4.2 for vertices.
Theorem 3.4.5 (Menger’s Theorem for vertices). Let G = (V , E ) be a graph. Let u, v be distinct non-
adjacent vertices of G . Then the minimum number of elements of an uv -separator equals the maximum
number of internally disjoint uv -paths.

Proof. Apply Theorem 3.4.2 to G − {u, v } with A and B the sets of neighbours of u and v , respectively, in
G.

We finally arrive at the characterisation of k-connected graphs.

Theorem 3.4.6 (Global version of Menger’s Theorem). Let G = (V , E ) be a graph. For every k ≥ 2, the
following are equivalent:
(i) G is k-connected,
(ii) For every two distinct vertices u, v of G , there are k internally disjoint uv -paths in G .

Proof. If G contains k internally disjoint paths between any two vertices, then |V | > k and G cannot be
disconnected by removing fewer than k vertices, so G is k-connected.
Conversely, suppose that G is k-connected, and let u and v be distinct vertices of G .
Case 1: (u, v ) is not an edge. Consider the neighbors N(u) and N(v ) of u and v . Note that v ∈ / N(u) and
u∈/ N(v ) because (u, v ) is not an edge. The minimum size of an N(u)N(v )-separator is at least k because
G is k-connected. Thus by Theorem 3.4.2 there are k disjoint N(u)N(v )-paths P0 , ... , Pk−1 , and we may
assume that none of these paths meet u or v . Then uP0 v , ... , uPk−1 v are k internally disjoint uv -paths.
Case 1: (u, v ) is an edge. Let e = (u, v ). Then G − e is k − 1 connected (see Exercise Sheet 3 #6). Apply
the argument of Case 1 to G − e to get k − 1 internally disjoint uv -paths P0 , ... , Pk−2 in G − e. Adding the
final path uv gives k internally disjoint uv -paths P0 , ... , Pk−2 , uv in G .

32
Chapter 4

Hamiltonian graphs

4.1 Hamiltonian graphs

We have seen in section 1.5 the notion of an Eulerian graph. Recall that, by definition, we say that a graph
G is Eulerian if there is closed edge sequence that contains every edge of G exactly once. A useful way to
remember this notion is by recalling that Eulerian graphs have something to do with edges. Informally, a graph
is Eulerian if we can walk around it using every edge and return to our starting point, but allowing ourselves
the possibility of passing by some vertices more than once. The fundamental result on Eulerian graphs was
that a connected graph is Eulerian if and only if every vertex in it has even degree (theorem 1.5.3).
In this chapter, we consider the subtler notion of a Hamiltonian graph. Informally, a graph is Hamiltonian
if we can walk around it visiting every vertex and return to our starting point, but without allowing ourselves
the possibility of passing by a vertex more than once.
Clearly, such a notion is of great practical importance, e.g. in questions about logistics. Clearly, checking
whether a graph is Hamiltonian by brute force, inspecting every cycle in it, is not practical if the graph is
large. This motivates the study of conditions that ensure that a graph is Hamiltonian and are easier to verify
in practice. The main results in this chapter will provide such conditions.
The material in this chapter is taken, sometimes verbatim, from [Wes18, Chapter 7], [Die17, Chapter 10],
[CZ12, Chapter 6] and [Wil10, Chapter 2].
Definition 4.1.1. Let G be a graph.
• A Hamiltonian cycle is a cycle that contains every vertex of G . We say that G is Hamiltonian if it
has a Hamiltonian cycle.
• A Hamiltonian path is a path that contains every vertex of G . We say that G is semi-Hamiltonian
if has a Hamiltonian path, but no Hamiltonian cycle.
Note that a Hamiltonian cycle contains every vertex of G exactly once.
Example 4.1.2. Consider the following graphs:

G1 G2 G3
a b a b a b

c d c d c d

Then,
• G1 is Hamiltonian, as we have the Hamiltonian cycle abdca.
• G2 is semi-Hamiltonian, as we have the Hamiltonian path badc.

33
Chapter 4. Hamiltonian graphs 4.2. Necessary conditions

• G3 is neither Hamiltonian nor semi-Hamiltonian.

Example 4.1.3.
• For n ≥ 3, the cycle graph Cn is Hamiltonian.
• For n ≥ 3, the complete graph Kn is Hamiltonian.
• For n ≥ 2, the complete bipartite graph Kn,n is Hamiltonian.

We note below a simple result, whose proof is immediate and hence omitted. Intuitively, it says that if
we start from a Hamiltonian graph G and add some edges to create a new graph G ′ , then G ′ is again
Hamiltonian.
Lemma 4.1.4. Let G and G ′ be graphs. Assume that G is a subgraph of G ′ with V (G ) = V (G ′ ). If G is
Hamiltonian so is G ′ .

4.2 Necessary conditions

We begin to explore Hamiltonian graphs by looking at their connectivity (in the sense of chapter 3). Suppose
that G is a Hamiltonian graph and let C be a Hamiltonian cycle in it, i.e. a cycle in G that contains every
vertex of G exactly once. Clearly, G is connected. Also, since every vertex lies on C , the graph G is 2-
connected by Whitney’s Theorem (every vertex lies in a cycle, namely C ). The next result asserts that if we
remove vertices from a Hamiltonian graph, the result cannot have ‘too many’ connected components.
Proposition 4.2.1. Let G = (V , E ) be a graph. If G is Hamiltonian, then for any non-empty S ⊆ V , the
graph G − S has at most |S| components.

Proof. Let S ⊆ V be a non-empty set of vertices. Since G is Hamiltonian, there is a Hamiltonian cycle C
in G . Since C is a subgraph of G that contains all the vertices of G , the number of components of G − S is
less or equal to the number of components of C − S. But since C is a cycle, the number of components of
C − S is less or equal to |S|.

Proposition 4.2.1 can be useful to show that a graph G = (V , E ) is not Hamiltonian. Indeed, if we find
S ⊆ V such that G − S has more than |S| components, then G cannot be Hamiltonian. In particular, if a
graph contains a cut-vertex then it is not Hamiltonian. We illustrate this idea with two examples.
Example 4.2.2. We can apply Proposition 4.2.1 to show that the graphs

x
x y

are not Hamiltonian. For the first, observe that x is a cut-vertex. For the second, consider S = {x, y } and
observe that G − S has three connected components.

4.3 Sufficient conditions

There are no nice necessary and sufficient conditions for a graph to be Hamiltonian, analogous to Euler’s
Theorem (theorem 1.5.3) characterising when a graph is Eulerian. However, there are various theorems saying
that a graph with ‘enough’ edges is Hamiltonian. We now explore some of these conditions.
For the next result, recall that for a graph G and non-adjacent vertices u, v of G , we write G ∪ uv for the
graph obtained by adding the edge uv to G .
Lemma 4.3.1. Let G be a graph with n vertices. Assume u and v are non-adjacent vertices such that
d(u) + d(v ) ≥ n. Then G ∪ uv is Hamiltonian if and only G is Hamiltonian.

Proof. Let u and v be non-adjacent vertices in G such that d(u) + d(v ) ≥ n.

“⇒” Suppose G is Hamiltonian. Then so is G ∪ uv by Lemma 4.1.4.

34
Chapter 4. Hamiltonian graphs 4.3. Sufficient conditions

“⇐” Suppose that G ∪ uv is Hamiltonian. This means that there is a Hamiltonian cycle C in G ∪ uv . Either
C contains the edge uv or not. If it does not, then C is a Hamiltonian cycle in G and we are done. If
it does, then G contains a Hamiltonian uv -path, say

v1 v2 v3 ... vn−1 vn (4.3.1)

with v1 = u and vn = v . To construct the required cycle, it will be sufficient to modify this path so as
to avoid the edge uv . For this, we need to find edges uvi+1 and vvi for some 2 ≤ i ≤ n − 2.

Claim. There is some 2 ≤ i ≤ n − 2 such that uvi+1 and vvi are edges.

Proof of Claim. Let

S = {1 ≤ i ≤ n − 2 | uvi+1 ∈ E } , T = {2 ≤ i ≤ n − 1 | vvi ∈ E }.

The claim follows once we show that |S ∩ T | ≥ 1. Observe that

|S ∪ T | + |S ∩ T | = |S| + |T | = d(u) + d(v ) ≥ n .

Here, |S| = d(u) since (4.3.1) is a Hamiltonian path and thus passes through all the vertices of G
and uv ∈/ E . Similarly, |T | = d(v ). Now, S ∪ T ⊆ {1, ... , n} but n ∈ / S ∪ T , so |S ∪ T | < n.
Therefore |S ∩ T | ≥ 1, as required, since otherwise we could not have |S ∪ T | + |S ∩ T | ≥ n.

By the Claim, we obtain a Hamiltonian cycle

u vi+1 vi+2 ... vn−1 v vi vi−1 ... v2 u ,

as required.

Theorem 4.3.2 (Ore, 1960). Let G = (V , E ) be a graph with n ≥ 3 vertices. If

d(u) + d(v ) ≥ n , for all non-adjacent u, v ∈ V (G ) , (∗)

then G is Hamiltonian.

Proof. By contradiction, assume that there is a graph G on n vertices satisfying (∗) but that is not Hamilto-
nian. Without loss of generality, we may suppose that if G becomes Hamiltonian if we add one more edge to
it. Indeed, if this is not the case, we can replace G with a graph G ′ obtained by repeatedly adding edges until
adding just one more edge makes it Hamiltonian. Such a graph G ′ must exist, since the complete graphs
Kn are Hamiltonian for n ≥ 3, and it satisfies the assumptions of the theorem if G does. But now since G
becomes Hamiltonian if we add one more edge uv to it, G is Hamiltonian by lemma 4.3.1.

Theorem 4.3.3 (Dirac, 1952). Let G be a graph with n ≥ 3 vertices. If

n
d(v ) ≥ , for each v ∈ V (G ),
2
then G is Hamiltonian.

Proof. Given the assumption, d(u) + d(v ) ≥ n for all vertices u, v , so the conclusion is an immediate
consequence of Ore’s theorem.

Example 4.3.4. The Johnson graph J(5, 2) (the complement of the Petersen graph) has vertex set of size
5


2 = 10. The vertex 12 is joined to the vertices 13 , 14 , 15 , 23 , 24 , 25 so d(12) = 6. In fact, we have
d(v ) = 6 for all vertices v . As d(v ) > 10 2 , J(5, 2), theorem 4.3.3 implies that J(5, 2) is Hamiltonian. For
example, the cycle
12 , 23 , 34 , 45 , 25 , 24 , 41 , 13 , 35 , 15 , 12 .
is a Hamiltonian cycle in J(5, 2).

35
Chapter 4. Hamiltonian graphs 4.4. Hamiltonian closure and Chvátal’s theorem

4.4 Hamiltonian closure and Chvátal’s theorem

The theorems of Dirac and Ore were the starting point of a series of results providing more and more
refined sufficient conditions to prove that a graph is Hamiltonian. Although we will not give the proof of
the result that culminates this series, namely Chavtál’s Theorem, we discuss the main ideas involved in this
development.
Lemma 4.3.1 suggests the following strategy to check if a graph G with n ≥ 3 vertices is Hamiltonian. Instead
of focusing on G , we take two non-adjacent vertices u, v such that d(u) + d(v ) ≥ n and check if G1 = G ∪ uv
is Hamiltonian. If this is difficult, we repeat the same process, adding one more edge at the time, so as to
produce a sequence of graphs
G , G1 , ... Gi , ... (4.4.1)

If eventually we reach the complete graph Kn , which is Hamiltonian, then G is Hamiltonian by repeated
applications of Lemma 4.3.1. In this way, we reduced the problem of finding conditions on G that make it
Hamiltonian to the problem of finding conditions on G that make such a sequence eventually reach Kn . We
now make these ideas precise.

Let G be a graph with n vertices. We define its Hamilton closure Cl(G ) to be obtained from G by
iteratively adding edges joining pairs of non-adjacent vertices whose degree sum is at least n, until no such
pair exists.
Example 4.4.1. Consider
1 1 1
G1 G2 G3

5 2 ⇝ 5 2 ⇝ 5 2

4 3 4 3 4 3
1 1
G4 G5

⇝ 5 2 ⇝ 5 2

4 3 4 3

Then G5 is a Hamilton closure of G1 .

From our definition, it is not immediately obvious that there cannot be different Hamilton closures of a graph,
depending on which edges we choose to add. The following result says that this cannot happen and therefore
we can speak of the Hamilton closure of a graph.
Lemma 4.4.2. Let G be a graph. The closure Cl(G ) is well-defined, i.e., if we close G in different ways, we
obtain the same graph.

Proof. Suppose that, in forming the closure in two different ways, we form Cl1 (G ) by adding successively edges
e1 , ... , er and we form Cl2 (G ) by adding edges f1 , ... , fs . We will use induction to show that {e1 , ... , er } ⊆
{f1 , ... , fs }, and then arguing in the other direction will show that {f1 , ... , fs } ⊆ {e1 , ... , er }, so {e1 , ... , er } =
{f1 , ... , fs }.
If e1 has endpoints u, v , then the degrees in G of u and v must sum to at least n. Adding edges to a graph
can only increase the degrees of the vertices, so the edge e1 must be added at some point in the construction
of Cl2 (G ). Hence e1 ∈ {f1 , ... , fs }.

36
Chapter 4. Hamiltonian graphs 4.4. Hamiltonian closure and Chvátal’s theorem

Now suppose that e1 , ... , ei ∈ {f1 , ... , fs } for some 1 ≤ i < r . Then after adding f1 , ... , fs , we have added
e1 , ... , ei . Now after adding e1 , ... , ei the degrees of the endpoints u, v of ei+1 sum to at least n, so the same
holds after adding f1 , ... , fs . Thus, since Cl2 (G ) is closed, ei+1 ∈ {f1 , ... , fs }.

Theorem 4.4.3 (Bondy and Chvátal). Let G be a graph. Then G is Hamiltonian if and only if Cl(G ) is
Hamiltonian.

Proof. We prove the two directions separately.

“ ⇒” Assume that G is Hamiltonian. Then Cl(G ) is Hamiltonian by Lemma 4.1.4.
“ ⇐” Assume that Cl(G ) is Hamiltonian. For a contradiction, suppose that G is non-Hamiltonian. Then
there is a sequence
G0 , G1 , ... , Gn
as in (4.4.1) with G0 = G and Gn = Cl(G ). There has to be some i such that Gi is non-Hamiltonian
but Gi+1 is Hamiltonian. Then Gi+1 = Gi ∪ uv , where u, v are non-adjacent in Gi but adjacent in Gi+1 .
But this contradicts Lemma 4.3.1.

Theorem 4.4.3 can be used to obtain the following result, which asserts that a graph is Hamiltonian even if
some vertices can have small degrees, provided that other vertices have sufficiently large ones.
Theorem 4.4.4 (Chvátal, 1972). Let G be a graph with n ≥ 3 vertices and assume that the vertices of G
have degrees d1 ≤ ... ≤ dn . Assume that, for every 1 ≤ i < n2 , if di ≤ i then dn−i ≥ n − i. Then Cl(G ) = Kn
and so G is Hamiltonian.

Proof. Suppose for a contradiction that Cl(G ) ∼ ̸ Kn . For a vertex x of G , let d(x) denote the degree of
=
x in G , and let d ∗ (x) denote the degree of x in Cl(G ). Notice that d(x) ≤ d ∗ (x) for every vertex x. Let
d1∗ ≤ d2∗ ≤ · · · ≤ dn∗ be the degree sequence for Cl(G ). Then dj ≤ dj∗ for every j ≤ n. The goal is to find an
i < n2 such that

di∗ ≤ i and ∗
dn−i < n − i.

Then

di ≤ di∗ ≤ i and ∗
dn−i ≤ dn−i < n − i,

so this i contradicts the assumption di ≤ i ⇒ dn−i ≥ n − i.

We show how to find the desired i. As Cl(G ) ∼ ̸ Kn , there are pairs of distinct vertices of Cl(G ) that are not
=
adjacent. Let x and y be distinct non-adjacent vertices of Cl(G ) where the quantity d ∗ (x) + d ∗ (y ) is as large
as possible, and further assume that d ∗ (x) ≤ d ∗ (y ). Then d ∗ (x) + d ∗ (y ) < n because otherwise edge (x, y )
would have been added when forming Cl(G ). Let i = d ∗ (x) and observe that i < n2 .
We show that di∗ ≤ i. To see this, consider the vertices that are distinct from y and not adjacent to y in
Cl(G ). There are

n − 1 − d ∗ (y ) ≥ (d ∗ (x) + d ∗ (y )) − d ∗ (y ) = d ∗ (x) = i

such vertices. For each such w ̸= y that is not adjacent to y in Cl(G ), we have that d ∗ (w ) + d ∗ (y ) ≤
d ∗ (x) + d ∗ (y ) because d ∗ (x) + d ∗ (y ) is the maximum sum of degrees of non-adjacent vertices. Therefore
d ∗ (w ) ≤ d ∗ (x) = i when w ̸= y is not adjacent to y . What we have shown is that there are ≥ i many
vertices whose degrees in Cl(G ) are ≤ i. Thus the i th largest degree in Cl(G ) is ≤ i. That is, di∗ ≤ i.
∗
Now we show that dn−i < n − i via a similar argument. Consider now the vertices that are distinct from x
and not adjacent to x in Cl(G ). There are

n − 1 − d ∗ (x) = n − 1 − i

such vertices. For each such z ̸= x that is not adjacent to x in Cl(G ), we have that

d ∗ (x) + d ∗ (z) ≤ d ∗ (x) + d ∗ (y ) < n,

37
Chapter 4. Hamiltonian graphs 4.4. Hamiltonian closure and Chvátal’s theorem

so

d ∗ (z) < n − d ∗ (x) = n − i.

Therefore d ∗ (z) < n − i when z ̸= x is not adjacent to x. Also, d ∗ (x) = i < n − i because i < n2 . All
together, there are (at least) n − i vertices (including x) whose degrees in Cl(G ) are < n − i. Thus the
∗
(n − i)th largest degree in Cl(G ) is < n − i. That is, dn−i < n − i. This completes the proof.

38
Chapter 5

Algebraic graph theory

5.1 Preliminaries from linear algebra

We now introduce a new way of studying graphs. The idea is to attach to a graph a particular matrix, in
the sense of linear algebra, and note that some of the properties of the graph are reflected in properties of
the associated matrix, which can then be studied using linear algebra. In fact, we will not need much linear
algebra in our study. The material in this chapter is taken, sometimes verbatim, from [AG07, Chapter 4] and
[Wes18, Chapter 2].

We begin by recalling some notation and basic facts.

• For a vector (x1 , ... , xn ), its transpose (x1 , ... , xn )T is the vector
 
x1
x2 
 
 .. 
.
xn

• Let A be an n × n matrix over R. We say that x = (x1 , ... , xn )T ̸= 0 is an eigenvector of A with

eigenvalue r if
Ax = rx .

• Let A be an n × n matrix over R. For an eigenvalue k, the set of eigenvectors of A with eigenvalue k,
together with the zero vector, is a subspace of Rn , called the eigenspace of eigenvalue k. The dimension
of this space, which is the number of linearly independent eigenvectors of eigenvalue k, is called the
multiplicity of the eigenvalue k.

• If A is a diagonal block matrix of the form

 
A1 0 ... 0
0 A2 ... 0 
A= .
 
.. .. ..
 ..

. . . 
0 0 ... An

the eigenvalues and multiplicities of of A are obtained as the union of the eigenvalues of A1 , A2 , ... , An
adding up multiplicities in case of duplicates.

• The trace Tr(A) of a square matrix A is the sum of its diagonal entries. It satisfies the formula
Tr(AB) = Tr(BA).

39
Chapter 5. Algebraic graph theory 5.2. The adjacency matrix

5.2 The adjacency matrix

Let G = (V , E ) be a graph with V = {v1 , ... , vn }. The adjacency matrix A(G ) is the n × n matrix with
entries A(G )ij given by

1 if vi vj ∈ E
A(G )ij =
0 otherwise
for 1 ≤ i, j ≤ n. The adjacency matrix depends on an ordering of the vertices of G . However, this ordering
is not really important, as explained in remark 5.2.5.
Example 5.2.1. For the graph G :
 
0 1 0 0 1 0 0
v5 1 0 0 0 1 0 0
v3 v7  
0 0 0 1 0 0 0
 
v6 0
AG =  0 1 0 0 0 0
G v1 1
 1 0 0 0 0 1
v4 0 0 0 0 0 0 0
v2 0 0 0 0 1 0 0

Remark 5.2.2. For a graph G = (V , E ) with V = {v1 , ... , vn },

(i) The adjacency matrix A(G ) is symmetric, i.e. A(G ) = A(G )T . Explicitly, this means that A(G )ij =
A(G )ji for all 1 ≤ i, j ≤ n.
(ii) The entries of A(G ) are real.
(iii) By (i) and (ii), as an instance of a general fact about real symmetric matrices from linear algebra, all
eigenvalues of its adjacency matrix A(G ) are real and eigenvectors for distinct eigenvalues are orthogonal
with respect to the inner product on Rn .
Lemma 5.2.3. Let G = (V , E ) be a graph with V = {v1 , ... , vn }. For k ≥ 1, the (i, j)-entry of Ak is the
number of edge sequences of length k from vi to vj in G .

Proof. We use induction on k.

Base case. The result is trivial if k = 1.

Inductive step. Given vertices vi , vk , a vi vj -edge sequence of length k consists of an edge sequence of length
k − 1 from vi to vℓ for some ℓ, followed by an edge vℓ vj . By induction, the number of vi vl -edge sequences of
length k − 1 equals (Ak−1 )iℓ . So the number of vi vj -edge sequences of length k equals
n
X
(Ak−1 )iℓ Aℓj = (Ak )ij .
ℓ=1

Lemma 5.2.4. Let G = (V , E ) be a graph with V = {v1 , ... , vn }. Assume that G is k-regular. Then,
(i) Jn = (1, 1, ... , 1)T is an eigenvector of A = A(G ) with eigenvalue k,
(ii) if G is connected, the eigenvalue k has multiplicity 1.

Proof.
(i) We must show AJn = kJn . We check that for every 1 ≤ i ≤ n, the i-th entry of both vectors is the
same. The i th entry of AJn equals the number of 1s in the i th row of A, which equals k since G is
k-regular. Clearly, the i th entry of kJn is k, as required.
(ii) Suppose that G is connected. We want to show that the space of eigenvectors of eigenvalue k has
dimension 1. Since we already have a vector of eigenvalue k, namely Jn , it suffices to show that, if
x = (x1 , ... , xn )T is an eigenvector with eigenvalue k, then x is a multiple of Jn . For this, it suffices to
show that x1 = ... = xn . So let x = (x1 , ... , xn )T be such that

Ax = kx .

40
Chapter 5. Algebraic graph theory 5.3. Strongly regular graphs

Let j be such that |xi | ≤ |xj | for all i = 1, ... , n. We may assume xj > 0. Then we have

(Ax)j = (kx)j . (∗)

P
The right hand side is kxj , and the left hand side is i∈I xi , where the sum is over

I = {1 ≤ i ≤ n | vi is a neighbour of vj } .

We know that vj has exactly k neighbours, so equation (∗) tells us that the sum of k numbers less than
or equal to xj is equal to kxj . The only way that this can happen is if each xi = xj for all i ∈ I . So we
have shown that whenever vi and vj are neighbours, xi = xj . But since G is connected, any vi and vj
must be connected by a path and hence we have xi = xj for any i , j.

Remark 5.2.5. We conclude this section with a remark that explains in what sense the adjacency matrix of a
graph is independent of the choice of ordering of its vertices. Note that when we order the rows and columns
of A(G ) we assume to be given an ordering V = {v1 , ... , vn } of the vertices of G . It is therefore natural to
wonder to what extent A(G ) will change if we change the ordering of the vertices.
So let G = (V , E ) be a graph with V = {v1 , ... , vn } and assume that we are given another ordering
V = {v1′ , ... , vn′ }, where
vi′ = vσ(i)
for some permutation σ of {1, ... , n}. Writing A(G )′ for the adjacency matrix of G relative to the ordering
V = {v1′ , ... , vn′ }, we have
A(G )′ij = A(G )σ(i)σ(j)
This means that A(G )′ is obtained by swapping the i-th and σ(i)-th row and the j-th and σ(j)-th column in
A(G ). This fact can be expressed as the equation

A(G )′ = P T A(G )P

where P is the permutation matrix associated to σ. This is the matrix

P = σ̃1 σ̃2 · · · σ̃n

where σ̃i is the column vector with 1 in the σ(i)-th row and 0 in all the other rows. Permutation matrices
such as P are orthogonal matrices, in the sense that their inverse is given by their transpose, so P −1 = P T .
It is a standard fact of linear algebra that in this situation if x is an eigevector of A(G ) with eigenvalue λ
and multiplicity m, then P T x is an eigenvalue of A(G )′ with eigenvalue λ and multiplicity m. Indeed, we
have A(G ) = PA(G )′ P T and therefore

A(G ) x = λx ⇒ PA(G )′ P T x = λx
⇒ A(G )′ P T x = λ P T x

The claim about multiplicities follows by a similar reasoning. In particular, if Jn = (1, ... , 1)T is an eigenvector
of A(G ) with eigenvalue λ and multiplicity m, it is also an eigenvector of A(G )′ with eigenvalue λ and
multiplicity m.

5.3 Strongly regular graphs

Definition 5.3.1. Let G be connected graph. We say that G is strongly regular if it is k-regular and
there are parameters λ and µ such that any two adjacent vertices have λ common neighbours and any two
non-adjacent vertices have µ common neighbours.
Example 5.3.2. The Johnson graph J(m, 2) (with vertex set the set of 2-subsets of {1, ... , m}, two vertices
adjacent if they intersect in a 1-element set) is strongly regular, with

k = 2(m − 2) , λ = (m − 3) + 1 = m − 2 , µ = 4.

Lemma 5.3.3. Let G be a connected graph. Assume that G is strongly regular on n vertices with parameters
k, λ, µ. Then its adjacency matrix A = A(G ) has three eigenvalues:

41
Chapter 5. Algebraic graph theory 5.3. Strongly regular graphs

• k, with multiplicity 1,
 
• r+ = 21 λ − µ + (λ − µ)2 + 4(k − µ) , with multiplicity
p

!
1 2k + (n − 1)(λ − µ)
m+ = n−1− p ;
2 (µ − λ)2 + 4(k − µ)

 
• r− = 1
p
2 λ−µ− (λ − µ)2 + 4(k − µ) , with multiplicity
!
1 2k + (n − 1)(λ − µ)
m− = n−1+ p .
2 (µ − λ)2 + 4(k − µ)

In particular, m+ and m− are positive integers.

Proof. By Lemma 5.2.4 we know that k is an eigenvalue of G and that it has multiplicity 1.
Next, we show that r+ and r− as in the statement are eigenvalues. Consider the matrix A2 , where A is the
adjacency matrix of G . By Lemma 5.2.3, (A2 )ij is the number of edge sequences from i to j of length 2. As
G k-regular,
(A2 )ii = k
For i ̸= j, the assumption that G is strongly regular with parameters k, λ, µ imply that

2 λ if vi vj ∈ E ,
(A )ij =
µ if vi vj ∈
/E.

Writing I for the n × n identity matrix and J for the n × n all-1 matrix, we obtain

A2 = kI + λA + µ(J − I − A) .

Hence, after rearranging,

A2 = (k − µ)I + (λ − µ)A + µJ.
Let x be an eigenvector of A with eigenvalue r ̸= k. Applying both sides of the above equation to x gives

r 2 x = (k − µ)x + (λ − µ)rx + µJx .

But because (Jx)i = Jn .x for all i and the eigenvalues of A with eigenvectors x and Jn are distinct, Remark 5.2.2
implies that Jn and x are orthogonal, so Jx = 0. So

r 2 x = (k − µ)x + (λ − µ)rx

and as x ̸= 0 we see that

r 2 − (λ − µ)r − (k − µ) = 0.
The two solutions
1 p 
r± = λ − µ ± (λ − µ)2 + 4(k − µ)
2
of this equation give all the eigenvalues of A other than k.
We now show that r+ and r− have the appropriate multiplicities. Since the matrix A is real and symmetric,
it is diagonalizable, i.e. there is an invertible n × n matrix P such that P −1 AP is a diagonal matrix, and
the entries of this diagonal matrix are precisely the eigenvalues, counted with multiplicity. Let m± be the
multiplicity of r± . As the diagonal of P −1 AP consists of n entries, we have

m+ + m− + 1 = n .

Using the formula for the trace of product of matrices, we get

0 = Tr(A) = Tr(PP −1 A) = Tr(P −1 AP) = k + m+ r+ + m− r− .

Let us now write

s = r+ , t = r− , a = m+ , b = m−

42
Chapter 5. Algebraic graph theory 5.4. The friendship theorem

Solving the equations a + b + 1 = n and k + as + bt = 0 gives

k + (n − 1)t k + (n − 1)s
a= and b = .
t −s s −t
p
Writing D for the discriminant (λ − µ)2 + 4(k − µ), we see that s − t = D and t − s = −D, and so

(n−1)
(λ − µ ∓ D)
 
k+ 2 1 2k + (n − 1)(λ − µ)
m± = = n−1∓ ,
∓D 2 D

as required.

5.4 The friendship theorem

Our next result is known as the Friendship Theorem, as it can be informally rephrased as saying that in a
party in which any two distinct people have exactly one common friend, there is at least one person who is a
friend of everybody.
Theorem 5.4.1 (Friendship Theorem). Let G be graph. Assume that any two distinct vertices of G have
exactly one common neighbour. Then there is at least one vertex which is adjacent to all the others.

Proof. Let G be a graph such that any two distinct vertices have exactly one common neighbour. We
distinguish two cases, depending on whether G is regular or not.
For the first case, suppose that G is k-regular for some k. We cannot have k = 1, as this would contractict
the assumption that any two distinct vertices have exactly one common neighbour. So we must have k > 1.
Then G is strongly regular, with parameters

k > 1, λ = 1, µ = 1.

Indeed, every two vertices (adjacent or not) have exactly one common neighbour. Now,
 
1 k
Lemma 5.3.3 ⇒ n−1± √ ∈Z
2 k −1
k
⇒ √ ∈ Z.
k −1
⇒ ∃u ∈ Z (k − 1 = u 2 )

u2 + 1 1
⇒ =u+ ∈Z
u u
⇒ u = ±1
⇒ k = 2.

Therefore, we must have G ∼

= K3 so every vertex is adjacent to all the others.

For the second case, suppose that G is not regular.

Claim 1. G does not have any 4-cycles.

Proof of Claim 1. If that was the case, there would be two distinct vertices which have at least two common
neighbours.

Claim 2. If u, v are not adjacent, then d(u) = d(v ).

Proof of Claim 2. If u = v then the statement is obvious, so assume that u ̸= v . Then u and v have a unique
common neighbour which we call w . Also u and w have a unique common neighbour, which we’ll call a, and

43
Chapter 5. Algebraic graph theory 5.4. The friendship theorem

v and w have a unique common neighbour, which we’ll call b. Note that a ̸= b, as otherwise we would have
a 4-cycle ua, bv , vw , wu.

f (x)
u v
a b

Let N(u) denote the neighbours of u. We define a function

f : N(u)\{a, w } → N(v )\{b, w }

Given x ∈ N(u)\{a, w }, x and v must be distinct, as v is assumed to be non-adjacent to u. We define f (x)

to be the unique neighbour of x and v . Note that f (x) ̸= w (or else u and w would have two common
neighbours) and f (x) ̸= b (or else we would have a 4-cycle).
Let us now observe that the function f is injective. Indeed, if x1 ̸= x2 are both elements of N(u)\{a, w } such
that f (x1 ) = f (x2 ) then we would have a 4-cycle ux1 , x1 f (x1 ), f (x1 )x2 , x2 u, a contradiction. Therefore

|N(u)\{w }| ≤ |N(v )\{w }| ,

so d(u) ≤ d(v ). Arguing in the other direction, we see that d(v ) ≤ d(u), so we have d(u) = d(v ) and we
have proved Claim 2.

We can now conclude the proof of the Friendship Theorem.

Since G is not regular, there must be two vertices x and c with d(x) ̸= d(c). By Claim 2, they must be
adjacent. Let y be their unique common neighbour. Then d(y ) cannot be equal to both d(x) and d(c), as
otherwise d(x) = d(c). So either d(y ) ̸= d(c) or d(y ) ̸= d(x). Without loss of generality, we may assume
that d(y ) ̸= d(c).
We now show that the vertex c is adjacent to all vertices. By contradiction, suppose there is a vertex z which
is not adjacent to c. Then we must have d(z) = d(c) by Claim 2. So d(z) ̸= d(x) (or else d(x) = d(c))
and d(z) ̸= d(y ) (or else d(y ) = d(c)) and so, again by Claim 2, we must have edges zx and zy .

x c

z y

So there is a 4-cycle zy , yc, cx, xz, which we know can’t happen. Hence z can’t exist and therefore every
vertex is adjacent to c, as required.

Remark 5.4.2. From the Friendship Theorem it is easy to deduce that every graph that satisfies the “friendship
condition”, i.e., where every pair of vertices has exactly one common neighbour, must be a “windmill graph”,
i.e., it consists of 2m + 1 vertices forming m triangles which have a unique common node.

44
Chapter 5. Algebraic graph theory 5.5. The matrix-tree theorem

5.5 The matrix-tree theorem

The aim of this section is to describe a second surprising application of methods of linear algebra to graph
theory, known as the Matrix Tree Theorem.
Definition 5.5.1. Let G be a graph. A spanning tree of G is spanning subgraph of G that is a tree.
Proposition 5.5.2. Let G be a graph. If G is connected, then it has at least one spanning tree.

Proof. If G is not already a tree, pick any cycle C of G , and remove an edge uv of C . The resulting graph is
still connected, for any v0 vm -path which uses the edge uv can be replaced by an edge sequence using C − uv ,
and hence by a v0 vm -path by lemma 1.3.2. Keep doing this until there are no more cycles. What remains is
a tree.

Example. In the graph G below, a spanning tree for G is shown in bold.

v1 v2 v3

G = v4 v5
v6

v7 v8 v9

Of course, there may be more than one spanning tree in a connected graph. How many spanning trees does
a connected graph have? The Matrix-Tree theorem provides the answer. In order to state this theorem, we
need to introduce some other matrices associated to a graph, namely the degree matrix and the Laplacian
matrix.
For a graph G = (V , E ) with V = {v1 , ... , vn }, the degree matrix D(G ) is the n × n diagonal matrix in
which the i-th diagonal entry is the degree of vi .
Example 5.5.3.

v1 v2
 
3 0 0 0 0
0 4 0 0 0
 
G
v5 0
D(G ) =  0 3 0 0
0 0 0 3 0
0 0 0 0 1
v3 v4

For a graph G = (V , E ) with V = {v1 , ... , vn }, the Laplacian matrix L(G ) is defined by

L(G ) = D(G ) − A(G )

Example 5.5.4. For G the graph of Example 5.5.3, we have

   
3 0 0 0 0 0 1 1 1 0
0 4 0 0 0 1 0 1 1 1
   
0 0 3 0
L(G ) =  0 − 1 1 0 1 0


0 0 0 3 0 1 1 1 0 0
0 0 0 0 1 0 1 0 0 0

 
3 −1 −1 −1 0
−1 4 −1 −1 −1
 
−1
= −1 3 −1 0
−1 −1 −1 3 0
0 −1 0 0 1

45
Chapter 5. Algebraic graph theory 5.6. Cayley’s theorem

Remark 5.5.5. Let G be a graph.

(i) The Laplacian matrix L(G ) is symmetric, since D(G ) and A(G ) are so.

(ii) The entries ℓi,j of Laplacian matrix admit the following more direct description:

d(vi ) if i = j,

ℓi,j = −1 if vi is adjacent to vj

0 if vi is not adjacent to vj .


(iii) By (ii), all rows and columns of L(G ) sum to zero. This means that L(G )(1, ... , 1) = 0. This shows
that 0 is an eigenvalue of the Laplacian matrix.

In order to state the Matrix-Tree Theorem, we need some terminology. For an n ×n matrix A and 1 ≤ i, j ≤ n,
the (i, j)-th cofactor of A is
(−1)i+j det(Ci,j ),

where Ci,j denotes the matrix obtained by removing the i-th row and the j-th column from A. The Matrix-Tree
theorem, due to Kirchoff, can then be stated as follows.

Theorem 5.5.6 (Matrix Tree Theorem). Let G = (V , E ) be a graph with V = {v1 , ... , vn }. Then the number
τ (G ) of spanning trees of G equals the (i, j)-th cofactor of the Laplacian matrix L(G ) for every 1 ≤ i, j ≤ n.
In particular, all the cofactors of L(G ) are equal.

We will not prove the Matrix-Tree theorem. The proof involves introducing an additional matrix M(G ),
called the oriented incidence matrix of G , depending on an orientation of the edges of G , which has the
property that L(G ) = M(G )M(G )T . With this, we can calculate the (i, j)-cofactors of L(G ) via applications
of the so-called Cauchy-Binet formula for determinants of product of matrices, as well as other facts of linear
algebra [AG07, Section 4.5] or [Wes18, Section 2.2]. Instead, we show how the Matrix-Tree theorem can be
used to derive the number labelled of trees on n vertices.

5.6 Cayley’s theorem

Cayley’s Theorem tells us the number of labelled trees on n vertices. This is not the same as counting non-
isomorphic trees on n vertices. Up to isomorphism there is just one tree on 3 vertices, but there are 33−2 = 3
distinct labelled trees on 3 vertices. We will give two proofs of Cayley’s Theorem, one obtained by applying
the Matrix Tree Theorem and another using a combinatorial bijection.

Theorem 5.6.1 (Cayley, 1889). Let n > 1. There are nn−2 disinct labelled trees on n vertices.

First proof. Observe that labelled trees on n vertices are the same thing as spanning trees in Kn , so we can
calculate their number by applying the Matrix-Tree Theorem. Note that

L(Kn ) = D(Kn ) − A(Kn )

   
n−1 0 0 ··· 0 0 1 1 ··· 1
 0
 n − 1 0 ··· 0  1
  0 1 ... 1 
= 0
 ··· n−1 ··· 0  1
− 1 0 ··· 1 
 .. .. .. .. ..   .. .. .. .. .. 
 . . . . .  . . . . .
0 0 0 ··· n−1 1 1 1 ··· 0

 
n−1 −1 −1 ··· −1
 −1 n−1 −1 ··· −1
 
=  −1 −1 n−1 ··· −1
 

 .. .. .. .. ..

 . . . . .

−1 −1 −1 ··· n−1

46
Chapter 5. Algebraic graph theory 5.6. Cayley’s theorem

To find the number of spanning trees of Kn , we find a cofactor of L(Kn ). By considering the (1, 1)-th cofactor
of L(Kn ), we get  
n − 1 −1 −1 · · · −1
 −1 n − 1 −1 · · · −1
 
τ (Kn ) = det  −1 −1 n − 1 · · · −1
 

 .. .. .. .. ..

 . . . . .

−1 −1 −1 ··· n−1
where the matrix has size (n − 1) × (n − 1). We now use some standard linear algebra to compute this
determinant. By subtracting the first row from all the successive rows, we get
 
n − 1 −1 −1 · · · −1
 −n 
 
 −n n · In−2
τ (Kn ) = det 


 .. 
 . 
−n

where nIn−2 denotes the (n − 2) × (n − 2)-identity matrix multiplied by n. Adding columns 2, ... , n − 1 to the
first column, we get  
1 −1 −1 · · · −1
0 
 
0
τ (Kn ) = det  n · In−2  = nn−2

 .. 
. 
0
which the required claim.

Second proof. We fix labels L = {1, 2, ... , n}. Let A be the set of of trees with our labels. The strategy of
the proof is to establish a bijection between A and and another set B that we know has nn−2 elements. For
this, we let
B = {(b1 , ... , bn−2 ) | ∀i ∈ {1, ... , n − 2}bi ∈ L}
Clearly, |B| = nn−2 . We now define a function

f : A→B.

and then prove that it is bijective. For a tree, T , we define the sequence f (T ) = (b1 , ... , bn−2 ) as follows:
(1) Let T0 = T ,
(2) For 1 ≤ i ≤ n − 2,
• Let ai be the leaf in Ti−1 with least value,
• Let bi be the unique neighbour of ai in Ti−1 ,
• Let Ti = Ti−1 − ai ,
(3) Let f (T ) = (b1 , ... , bn−2 ).
The sequence f (T ) is called the Prüfer code of the tree T .
For example, given the tree T
3 6

1 5

4
we have f (T ) = (2, 5, 2, 5).

47
Chapter 5. Algebraic graph theory 5.6. Cayley’s theorem

One way of understanding the definition of the function is via the recursive formula

f (T ) = (b1 , f (T1 )) , (5.6.1)

where b1 is the vertex adjacent to the leaf x of T with least value and f (T1 ) is the Prüfer code of the tree
T1 = T − x. Note that T1 is a tree on {1, ... , n} \ {x} and does not include the edge xb1 . We make two
general remarks before proving that f is bijective.

Claim 1. If f (T ) = b, then {v | v leaf of T } = {1, ... , n} \ {b1 , ... , bn−2 }.

Proof of Claim 1. We prove the equivalent statement

{v | v not a leaf of T } = {b1 , ... , bn−2 }. The inclusion ‘⊆’ can be proved by induction on n ≥ 2. The
inclusion ‘⊇’ holds by construction of b, as none of its entries is a leaf.

Claim 2. If f (T ) = b, then the least element of {1, ... , n} \ {b1 , ... , bn−2 } equals the leaf adjacent to b1 in
T.

Proof of Claim 2. If f (T ) = b then b1 is adjacent in T to the leaf of T v with least value, but by Claim 1,
this is the least element of {1, ... , n} \ {b1 , ... , bn−2 }.

The combination of Claim 2 and the formula in (5.6.1) provides a way of constructing a tree whose Prüfer
code is a given sequence. We use this idea to show that the map f is bijective. For this, we show that for
each b ∈ B, there exists a unique T ∈ A such that f (T ) = b. We do this by induction on n.

Base case: n = 2. Then L = {1, 2}. The set of sequences in {1, 2} with n − 2 = 0 entries has only one
element, the empty sequence ( ) and there is only one tree on {1, 2}, so the claim is true.

Inductive step. Assume that n > 2 and that the result holds for the trees with less than n labels and prove it
for trees with labels L = {1, ... , n}. Let b = (b1 , ... , bn−2 ) be a sequence in B. We want to show that there is
a unique tree T such that f (T ) = b. For this, let x be the least element of {1, ... , n} \ {b1 , ... , bn−2 }. Then,
by the induction hypothesis, there exists a unique tree T1 on {1, ... , n} \ {x} such that f (T1 ) = (b2 , ... , bn−2 ).
We then define T as the graph obtained by adding the edge xb1 to T1 .
We claim that T is the unique tree such that f (T ) = b. First, we check that T is a tree. Note that b1 is a
vertex of T1 since T1 is a tree on {1, ... , n} \ {x}, b1 ∈ {1, ... , n} and x ̸= b1 . Since x is not a vertex of T1 ,
adding the edge xb1 to T1 returns a tree. Secondly, we check that f (T ) = b. For this, observe that x, which
was defined as the least element of {1, ... , n} \ {b1 , ... , bn−2 }, is the leaf of T with least value. Indeed, by
Claim 2 the leaves of T1 are ({1, ... , n} \ {x}) \ {b2 , ... , bn−2 } and so the the leaves of T are

{1, ... , n} \ {b1 , b2 , ... , bn−2 } .

by construction of T . The claim that f (T ) = b then follows from (5.6.1) since b1 is adjacent to x and f (T1 ) =
(b2 , ... , bn−2 ). Finally, we show that T is the unique tree such that f (T ) = b. Let T ′ be a tree such that
f (T ′ ) = b. Then, the leaf adjacent to b1 in T ′ is x by Claim 2. But then f (T ′ − x) = (b2 , ... , bn−2 ) and so,
by the induction hypothesis, T ′ − x = T1 . But then both T and T ′ are obtained by adding xb1 to the same
tree and therefore they are equal.

Remark 5.6.2. The proof of Cayley’s Theorem provides a way to find the tree associated to a given sequence.
For example, let n = 3 so that L = {1, 2, 3}. Let us fix a sequence of length n − 2 = 3 − 2 = 1 with entry
in {1, 2, 3}, say b = (1). To find the tree T such that f (T ) = b, we proceed in three steps. First, let
x be the least element of L \ {b1 } = {1, 2, 3} \ {1} = {2, 3}. Secondly, let T1 the the unique tree on
L \ {x} = {1, 2, 3} \ {2} = {1, 3}. Thus, T1 is the tree

1 3
Finally, we let T be the tree obtained by adding the edge xb1 = 21 to T1 , i.e.

2 1 3

You can check that f (T ) = (1), as required.

48
Chapter 5. Algebraic graph theory 5.6. Cayley’s theorem

Remark 5.6.3. For another example of the above process, let n = 4 and fix a sequence of length n − 2 = 2,
with entries in {1, 2, 3, 4}, say b = (1, 3). First, let x be the least element of {1, 2, 3, 4} \ {b1 , b2 } =
{1, 2, 3, 4} \ {1, 3} = {2, 4}, so x = 2. Then let T1 be the unique tree on {1, 2, 3, 4} \ {x} such that
f (T1 ) = (3). This can be done as in Remark 5.6.2, so as to obtain that T1 is

1 3 4

We then let T be the result of attaching the edge xb1 = 21 to T1 , thus getting

2 1 3 4

Again, you can check that f (T ) = (1, 3).

49
Chapter 5. Algebraic graph theory 5.6. Cayley’s theorem

50
Bibliography

[AG07] Geir Agnarsson and Raymond Greenlaw. Graph theory: modeling, applications, and algorithms.
Pearson Prentice Hall, 2007.
[CZ12] Gary Chartrand and Ping Zhang. A first course in graph theory. Dover, 2012.
[Die17] Reinhard Diestel. Graph Theory. Springer, 5th edition, 2017.
[Doc19] Christian Doczkal. Short proof of Menger’s theorem in Coq. Technical Report hal-02086931, https:
//[Link]/hal-02086931, 2019.
[Elw20] Richard Elwes. MATH2230/1 Discrete Maths, 2020. University of Leeds.
[Gör00] Frank Göring. A short proof of Menger’s theorem. Discrete Mathematics, 219:295–296, 2000.
[Wes18] Douglas West. Introduction to graph theory. Pearson Prentice Hall, 2nd edition, 2018.
[Wil10] Robin J. Wilson. Introduction to graph theory. Prentice Hall, 2010.

51