# 辅导案例-MAT3043

MAT3043: GRAPHS AND NETWORKS
Lectures
Spring Semester 2019/20
Contents
1 Graphs: basic properties and particular types 3
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Some specific graphs . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.5 Isomorphic graphs . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.6 Walks, trails, paths and cycles . . . . . . . . . . . . . . . . . . 8
1.1.7 Complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.8 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.9 Degree sequences and the Havel-Hakimi condition . . . . . . . 12
1.1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Connectedness of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Definition of connectedness . . . . . . . . . . . . . . . . . . . . 16
1.2.2 Separating and disconnecting sets . . . . . . . . . . . . . . . . 17
1.2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Eulerian and Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . 22
1.3.1 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.2 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.2 Prufer sequences . . . . . . . . . . . . . . . . . . . . . . . . . 30
1
1.4.3 Spanning trees and forests . . . . . . . . . . . . . . . . . . . . 33
1.4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Planar graphs, colouring, matching and flows 37
2.1 Planar graphs and dual graphs . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.2 Kuratowski’s theorem . . . . . . . . . . . . . . . . . . . . . . 40
2.1.3 Geometric dual . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.1.4 Maximal planar graphs . . . . . . . . . . . . . . . . . . . . . . 44
2.1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2 Graph colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.1 The chromatic number and the greedy algorithm . . . . . . . 47
2.2.2 The five and four colour theorems . . . . . . . . . . . . . . . . 48
2.2.3 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.4 Chromatic polynomials . . . . . . . . . . . . . . . . . . . . . . 51
2.2.5 Chromatic index and Vizing’s theorem . . . . . . . . . . . . . 54
2.2.6 Ko¨nig’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.3 Matchings and flows . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.3.1 Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.3.2 Hall’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.3.3 Transversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.4 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3 Graphs and matrices 65
3.1 Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3 Degree and Laplacian matrices . . . . . . . . . . . . . . . . . . . . . . 72
3.4 Matrix tree theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
2
Chapter 1
Graphs: basic properties and
particular types
1.1 Graphs
1.1.1 Basic definitions
Definition 1.1 A graph G consists of a non-empty set V (G) of vertices (or nodes)
and a set E(G) of edges, such that each edge joins a vertex to a vertex.
V (G) is the vertex set and E(G) is the edge set of G.
The order of G is |V (G)|, the number of vertices.
We shall consider only finite graphs, i.e. V (G) and E(G) will be finite sets.
A graph can be represented by a diagram called a drawing of the graph, in which
elements of V (G) and E(G) are shown as points and lines respectively. The vertices
will usually be denoted by lower-case letters and the edges by pairs of letters, such as
uv, which at present are unordered so vu = uv. We can also use a single letter for an
edge, e.g. e = uv. Position and distance do not matter; only the connections between
the vertices and edges are important. Thus the same graph can have several different
drawings.
The following all represent the same graph, having
four vertices with a single edge joining each pair:
3
Definition 1.2
If e = uv is an edge in a graph, we say that e and u are incident, as are e and v.
The vertices u and v are then adjacent, and each is a neighbour of the other.
Edges are adjacent if they are incident to the same point.
A set of vertices (or edges) is independent if no two of them are adjacent.
If edges e1, e2 join the same vertices u and v, they are parallel or multiple edges.
A loop is an edge of the form vv, i.e. it joins a vertex to itself.
A graph is a simple graph if it has no multiple edges or loops, and a multigraph
otherwise.
A directed graph or digraph is a graph in which a direction is assigned to each
edge; the edges are then called arcs. The direction is indicated by an arrow.
Example
This graph G is not a simple graph.
V (G) = {v1, v2, v3, v4}, E(G) = {e1, e2, . . . , e10}.
All pairs of vertices are adjacent except for v1 and v4.
e3 and e4 are adjacent edges. v1 is incident to e1, e2, e3, e4.
e1 is a loop at v1. e2, e3 are parallel edges.
1.1.2 Some specific graphs
Definition 1.3 The null graph Nn is the graph with n vertices and no edges.
The complete graph Kn is the simple graph with n vertices and an edge joining
every pair of distinct vertices.
The path graph Pn is the simple graph which can be represented by a straight line
connecting n points.
For n ≥ 3, the cycle graph Cn is the simple graph which can be represented by the
vertices and edges of an n-sided polygon. C1 is a loop, C2 is a pair of parallel edges.
For n ≥ 4, the wheel Wn is the graph formed by joining each vertex of Cn−1 to one
more vertex.
The complete graphs
K1(= N1), K2(= P2), K3(= C3), K4, K5.
4
The null graph N6, cycle graph C6,
wheel graph W6 and path graph P6:
It is clear that the number of edges in Kn is
(
n
2
)
, which equals
n(n− 1)
2
. This is
therefore the greatest possible number of edges in any simple graph with n vertices.
A particular set of graphs can be obtained from the five regular three-dimensional
figures known as the Platonic solids: the tetrahedron, cube, octahedron, icosahe-
dron and dodecahedron. These Platonic graphs preserve the incidence of vertices
and edges in the solids. The faces of the solid are represented by the regions bounded
by edges, except for one face which corresponds to the infinite exterior region of the
graph. The right-hand diagram shows how the graph of the cube is obtained by
projecting the vertices and edges onto a plane.
1.1.3 Degree
Definition 1.4 Let v be a vertex of a graph G. The degree (or local degree or
valency) of v, denoted by d(v) or deg(v), is the number of edges which are incident
to v, except that a loop at v contributes 2 to d(v).
δ(G) and ∆(G) denote the minimum and maximum degree, respectively, of any vertex
in G.
An isolated vertex is a vertex of degree 0.
An end vertex or terminal vertex or pendant vertex is a vertex of degree 1.
A regular graph is a graph in which every vertex has the same degree. If this degree
is r then the graph is r-regular, or regular of degree r. A 3-regular graph is cubic.
5
Examples
(i) In Example 1.1.1, d(v1) = 5, d(v2) = 6, d(v3) = 6, d(v4) = 3. Thus δ(G) = 3
and ∆(G) = 6. There are no isolated or end vertices. G is not regular.
(ii) In Nn, all vertices are isolated. Nn is regular of degree 0, for each n ∈ N.
(iii) Kn can be drawn as a regular n-sided polygon with all its diagonals, but the
points where these diagonals cross are not vertices of the graph. In Kn, every vertex
has degree n− 1, so Kn is (n− 1)-regular. K2 has two end vertices.
(iv) The graph shown here is called the Petersen graph.
It is cubic (3-regular), as each of its 10 vertices has degree 3.
It has 15 edges. Note that some edges cross in the diagram at
points which are not vertices. We can think of these lines as
being on different horizontal levels, so they do not intersect at all.
Proposition 1.1
(i) Let G be a graph with m edges. Then

v∈V (G)
d(v) = 2m.
(ii) The number of vertices of odd degree in any graph is even.
Proof
(i) In calculating the sum of the degrees, each edge uv is counted in both d(u) and
d(v). Also by definition a loop is counted twice, so the sum of the degrees is twice
the number of edges.
(ii) Suppose there are p odd-degree vertices and q even-degree vertices. Then the
sum of the degrees is the sum of p odd numbers and q even numbers. By (i) this sum
is even, so p must be even.
The above result is attributed to Euler. Part (i) is often called the handshaking
lemma, since it shows that if a number of people all shake hands with one another
then the total number of hands shaken is even.
1.1.4 Subgraphs
Definition 1.5 A subgraph of a graph G is a graph whose vertex and edge sets are
subsets of V (G) and E(G) respectively.
A spanning subgraph of G is a subgraph H such that V (H) = V (G).
An induced subgraph of G is a subgraph H which contains every edge of G that is
incident only to vertices in V (H).
6
Let S be a subset of V (G). Then G− S is the graph obtained from G by deleting all
the vertices in S and all edges incident to them. G − v is obtained by deleting a
single vertex v and all its incident edges.
Let F be a subset of E(G). Then G− F is the graph obtained from G by deleting all
the edges in F . G−e is obtained by deleting a single edge e. No vertices are deleted.
G \ e is the graph obtained by contracting the edge e, i.e. deleting e and replacing
its endpoints u and v with a single vertex incident to all edges that were incident to
u or v in G.
Given graphs G1 and G2, their union G1 ∪G2 is the graph which has vertex set
V (G1) ∪ V (G2) and edge set E(G1) ∪ E(G2).
Note that contracting an edge can introduce multiple edges. These may be removed
if a simple graph is required.
Examples
Here are some subgraphs of the graph G in Example 1.1.1
Contraction of the edge e to give a multi-
graph or a simple graph.
7
1.1.5 Isomorphic graphs
Definition 1.6 Two graphs G1, G2 are isomorphic (written G1 ∼= G2) if there is a
bijection φ : V (G1) → V (G2) such that for any u, v ∈ V (G1), the number of edges
joining u and v in G1 equals the number of edges joining φ(u) and φ(v) in G2. The
map φ is then a graph isomorphism.
In particular, an isomorphism must preserve essential properties of a graph such as
the number of vertices of a given degree and the number of loops (if any).
The three graphs on Page 1 are isomorphic, as they are different drawings of the
same graph. For unlabelled graphs, ‘isomorphic’ can be taken to mean ‘the same’.
However, we can also consider labelled graphs, in which a name is assigned to each
vertex.
Regarded as labelled graphs, the following are isomorphic but only the first two are
the same. An isomorphism from either of the first two graphs to the third is given
(not uniquely) by A 7→ D, B 7→ B, C 7→ C, D 7→ A.
The following diagram shows eight distinct labelled simple graphs with three vertices
1, 2, 3. If we were considering unlabelled graphs, only four of these would be distinct:
N3, P2 ∪N1, P3, C3.
1.1.6 Walks, trails, paths and cycles
Definition 1.7 A walk (or edge sequence) in a graph is a finite ordered list of
edges e1, e2, . . . , er in which consecutive edges are adjacent or the same. It can also be
denoted by v0v1v2 · · · vr where v0, v1, etc, are the vertices in the order in which they
are encountered. v0 is the initial vertex and vr is the final vertex of the walk,
which has length r (the number of edges).
A trail is a walk in which all the edges are distinct.
A path is a trail in which all the vertices are distinct (an open path), or all distinct
except for the initial and final vertex (a closed path, also called a cycle or circuit).
8
The distance `(u, v) between vertices u and v is the number of edges in the shortest
path between u and v.
A connected graph is a graph in which there is a walk between any two vertices.
Cycles of length 1, 2 and 3 are respectively a loop, a pair of parallel edges and a
triangle.
Example
In Example 1.1.1, e2, e3, e4, e6, e6, e9, e10 is a walk of length 7 from v1 to v3.
e1, e3, e6, e7, e8, e10, e4, e2 is a trail of length 8 from v1 to v2.
e2, e8, e9, e4 is a closed path from v1 to v1. It is a cycle of length 4.
`(v1, v2) = 1, `(v1, v4) = 2.
Proposition 1.2 Every simple graph G contains a path of length δ(G).
Proof
Let v0 · · · vr be a path of maximal length r in G. Every vertex adjacent to vr must lie
on this path, otherwise the path could be extended to such a vertex, so r ≥ d(vr) ≥
δ(G). Hence this maximal-length path, or a path contained in it, has length δ(G).
Proposition 1.3 Let G be a graph with no isolated or terminal vertices. Then G
contains a cycle. If G is simple then there is a cycle of length at least δ(G) + 1.
Proof
The existence of a cycle is clear if G has any loops or multiple edges. Suppose G is
simple. Let v0 · · · vr be a path of maximal length r in G. Every vertex adjacent to vr
must lie on this path. Let i be the smallest of 0, . . . , r for which vi is adjacent to vr.
d(vr) ≥ 2, so i ≤ r − 2. Then vi · · · vrvi is a cycle containing all the vertices adjacent
to vr so its length (the number of edges) is not less than d(vr) + 1, which in turn is
not less than δ(G) + 1.
1.1.7 Complement
Definition 1.8 The complement of a simple graph G is the graph G with the same
vertex set V (G), such that two vertices are adjacent in G if and only if they are not
A graph which is isomorphic to its complement is self-complementary.
9
It is clear that the complement of G is G.
Examples
(i) A graph G and its complement G:
(ii) C5 and C5 are the same graph.
Thus C5 is self-complementary.
Example
Show that in any set of at least six people there are either three mutual acquaintances
or three mutual strangers.
Represent the n people by vertices of a simple graph G, with an edge joining two of
them if and only if they are acquainted.
In the complete graph Kn = G ∪G, each vertex v is adjacent to all the others. Thus
v is adjacent to at least three vertices of a graph G′ which is either G or G.
If two of these three vertices are adjacent in G′ then, together with v, they form a
triangle in G′; otherwise they form a triangle in G′. Thus at least one of G and G
contains a triangle, so in G there are either three vertices all adjacent to one another,
or three vertices with no edges between any of them. The result follows.
1.1.8 Bipartite graphs
Definition 1.9 A graph G is bipartite if V (G) is the union of disjoint sets U and
W such that every edge of G joins an element of U to an element of W . Such a graph
can be denoted by G(U,W ). The sets U and W form a bipartition of V (G).
Let U and W have orders r, s respectively. If there is exactly one edge from each
vertex in U to each vertex in W , and no other edges, then G(U,W ) is the complete
bipartite graph Kr,s (or Ks,r - the order does not matter).
A bipartite graph; the complete bipartite graph K3,2; the complete bipartite graph
K1,5, also known as the star S6 (or S5 in some books).
Note that isolated vertices can be included in U or W . A null graph with two or more
vertices is bipartite.
10
Proposition 1.4 A graph with at least two vertices is bipartite if and only if it con-
tains no cycle of odd length.
Proof
(⇒): Suppose G(U,W ) is bipartite. If there is a cycle in G, it can be written in
the form u1w1u2w2 · · ·urwru1. Then the number of edges in the cycle is 2r, which is
even, so there can be no odd cycles.
(⇐): Suppose G does not contain an odd cycle. Then no connected subgraph of G
contains an odd cycle, so we may assume that G is connected.
If G has only one edge, it joins two vertices (as G has no loops) so G is bipartite.
Make the inductive hypothesis that all graphs with no odd cycles and fewer edges
than G are bipartite.
Let uv be any edge of G. By hypothesis, the graph G − uv has a bipartition into
vertex sets X and Y .
Suppose u, v ∈ X (the reasoning is identical if both are in Y ). If there is a path
P from u to v in G − uv, it alternates between X and Y so has even length. Then
P ∪ uv is a closed walk of odd length in G, so it contains an odd cycle by Exercises
1.1 Question 18. But G is assumed to contain no odd cycles.
Thus one of u and v is in X and the other in Y , so X and Y form a bipartition of G.
The result follows by induction.
It may not be obvious whether a given graph is bipartite. It will be so if there is a
way of assigning two colours (or other labels) to the vertices such that no two vertices
have the same colour. If we can find an odd cycle, the graph is certainly not bipartite.
Example
The first two of the following graphs are bipartite, as the alternating black and white
vertices show; in fact they are both K3,3 in disguise. The third graph is not bipartite
as it contains a triangle, which is an odd cycle.
11
1.1.9 Degree sequences and the Havel-Hakimi condition
Definition 1.10 The degree sequence of a graph is an ordered list of the degrees
of the vertices.
A list of integers is graphical if it is the degree sequence of a simple graph.
In Example 1.1.1, the degree sequence is 6, 6, 5, 3. (Some books write the sequence in
non-decreasing rather than non-increasing order.)
By Proposition 1.1, a degree sequence must contain an even number of odd terms.
It can be shown that any such sequence is the degree sequence of some graph or
multigraph (not necessarily unique).
To determine whether a degree sequence represents a simple graph, we can use:
Proposition 1.5 (The Havel-Hakimi condition)
A non-increasing list of integers s0, s1, . . . , sn, where s0 = d, is graphical if and only
if the list s1 − 1, s2 − 1, . . . , sd − 1, sd+1, sd+2, . . . , sn is graphical.
The proof of this result (omitted) establishes that some graph with non-increasing
degree sequence s0, . . . , sn has a vertex of degree d = s0 adjacent to d vertices of
degrees s1, . . . , sd. This need not be true for every graph with the given degree
sequence, but at least one must exist. It can be constructed by successively applying
the condition until a recognisable sequence is obtained.
Examples
(i) 4, 3, 2, 1, 1 is not graphical, because the number of odd numbers is not even.
(ii) Consider the list 5, 5, 4, 3, 2, 1. Successively applying the Havel-Hakimi condition
gives 4, 3, 2, 1, 0, then 2, 1, 0,−1. This is not graphical, as −1 cannot be the degree of
a vertex, so 5, 5, 4, 3, 2, 1 is not the degree sequence of a simple graph.
However, a multigraph with degree sequence 4, 3, 2, 1, 0 can be constructed. Then
joining a new vertex of degree 5 to each of these five vertices produces a multigraph
of order 6 with degree sequence 5, 5, 4, 3, 2, 1:
12
(iii) Consider the list 4, 3, 3, 3, 1. Successively applying the Havel-Hakimi condition
gives 2, 2, 2, 0, then 1, 1, 0. This is graphical since it is the degree sequence of a single
edge together with an isolated vertex. From this we can construct simple graphs with
degree sequences 2, 2, 2, 0 and finally 4, 3, 3, 3, 1, as shown.
13
1.1.10 Exercises
1. Consider the following multigraph G
(a) State the degree of each vertex.
(b) Verify each part of Proposition 1.1 for G.
(c) Draw the following graphs:
(i) G− uw, (ii) G− x, (iii) G− {u,w}, (iv) G \ wz,
(v) the subgraph H of G induced by {v, w, y, z},
(vi) the complement of the simple graph H − `, where ` is the loop at y.
(d) Find a connected spanning subgraph of G with the smallest possible num-
ber of edges.
(e) Find each of the following: (i) a trail of length 7 from t to y,
(ii) a path of length 6 from u to x, (iii) a cycle of length 6.
(f) Show that G is not bipartite.
2. Which of the following are regular? For those that are, state the degree of
regularity. (a) Nn, (b) Kn, (c) Pn, (d) Wn, (e) Kr,s.
3. Let G be an r-regular graph with n vertices and m edges. Find a relationship
between m,n and r.
Deduce that there are no 5-regular graphs with 7 vertices.
4. For each of the Platonic graphs on Page 5, state whether the graph is regular,
and if so of what degree.
5. Find the largest possible number of vertices in a graph with 19 edges in which
every vertex has degree at least 3.
6. G is a graph of order 9 in which each vertex has degree 5 or 6. Prove that G
has either at least five vertices of degree 6 or at least six vertices of degree 5.
7. The pigeon-hole principle states that if n objects are put into fewer than n
boxes then at least one box has more than one object in it.
Use this to show that in a finite simple connected graph with more than one
vertex, there are at least two vertices which have the same degree.
8. Show that the number of distinct labelled simple graphs with n vertices is
2n(n−1)/2.
14
9. Draw each of the following graphs and its complement: N3, K4, P3, W5, K3,2.
Are any of these graphs self-complementary?
10. Show that a self-complementary simple graph of order n has
n(n− 1)
4
edges.
Deduce that the order of such a graph is congruent to 0 or 1 (modulo 4).
11. Show that Cn is bipartite if and only if n is even.
12. Draw the eleven non-isomorphic unlabelled simple graphs with four vertices.
Give the degree sequence of each one.
13. Determine whether each of the following is the degree sequence of (i) a simple
graph, (ii) a multigraph, and draw the graph if one exists.
(a) 7, 5, 3, 1, (b) 3, 2, 2, 1, (c) 4, 3, 3, 2, 1, (d) 5, 5, 4, 3, 3, 2.
14. n people go on separate holidays. Each sends a postcard to exactly three of the
others. For each of n = 4, 5, 6, 7, 8, is it possible that each person receives a
card from precisely the three to whom they sent cards?
15. Let G be a 2-regular connected finite graph. By induction on the number of
edges in G, prove that G is a cycle.
16. e is an edge which is common to two cycles in a graph G. Prove that G contains
a cycle that does not include e.
17. Suppose r < s. Show that Kr+1,s−1 has no fewer edges than Kr,s.
Hence show that the maximum number of edges in Kr,s, where r + s = n, is⌊
n2
4

.
18. Prove that any closed walk of odd length contains a cycle of odd length.
15
1.2 Connectedness of graphs
1.2.1 Definition of connectedness
Definition 1.11 Vertices u and v are connected in a graph G if there is a walk
from u to v in G.
A connected graph is a graph G in which every two vertices are connected. If this
is not the case then G is disconnected.
For any v ∈ V (G), the set of all vertices of G that are connected to v is the compo-
nent of G containing v.
Examples
(i) Nn is disconnected. It has n components, each consisting of a single vertex.
(ii) The following graph has four components:
Proposition 1.6 Let G be a simple graph with n vertices, m edges and c components.
Then n− c ≤ m ≤ (n− c)(n− c+ 1)
2
.
Proof
For the lower bound: clearly m ≥ n− c when m = 0, since c = n in that case.
Starting from the null graph Nn, we can construct G by successively adding edges.
Each new edge increases m by 1 and either keeps c the same or reduces it by 1 (by
connecting two components), so the inequality m ≥ n− c is preserved at each stage.
The upper bound holds when G is connected, since then c = 1 and G is a subgraph
of Kn. If G is disconnected, let H1, . . . , Hc be the components of G and, for each i,
let Hi have ni vertices. The maximum number of edges of Hi occurs when it is the
complete graph Kni , so we may assume Hi has order
ni(ni − 1)
2
.
Suppose there are two components Hi, Hj with more than one vertex: say ni ≥
nj ≥ 2. Replacing Hi and Hj by complete graphs with ni + 1 and nj − 1 vertices
respectively will keep n and c unchanged, while the number of edges is increased by
(ni + 1)ni
2
+
(nj − 1)(nj − 2)
2
− ni(ni − 1)
2
− nj(nj − 1)
2
= ni − nj + 1 > 0.
16
This procedure can be repeated until some component can be made no larger. Thus
for any given n and c, the maximum value of m occurs when one component is the
complete graph Kn−c+1 and the other c− 1 components are isolated vertices. In this
case m =
(n− c)(n− c+ 1)
2
.
For a connected graph, c = 1. Then Proposition 1.6 gives n− 1 ≤ m ≤ n(n− 1)
2
, as
1.2.2 Separating and disconnecting sets
Definition 1.12 A separating set of a graph G is a set of vertices whose removal
(together with their incident edges) increases the number of components of G.
A cut vertex or cutpoint of G is a single vertex which forms a separating set.
The (vertex) connectivity κ(G) is the order of the smallest separating set in G. If
κ(G) ≥ k then G is k-connected.
A disconnecting set of a graph G is a set of edges whose removal increases the
number of components of G. A cutset is a disconnecting set which has no proper
subset that is a disconnecting set. A bridge is a single edge which forms a cutset.
The edge connectivity λ(G) is the order of the smallest disconnecting set in G. If
λ(G) ≥ k then G is k-edge-connected.
Thus a connected graph is k-connected/k-edge connected if the number of vertices/edges
that must be removed to disconnect it is k or more.
There is no separating set in Kn. We define κ(Kn) to be n−1, as removing this many
vertices reduces it to an isolated vertex. κ(Nn) and λ(Nn) are defined to be 0.
In a graph other than P2, at least one end-vertex of a bridge must be a cut vertex.
Examples
(i) In the graph G of Example 1.1.1, the smallest separating set is {v2, v3}, so
κ(G) = 2. Thus G is 2-connected, and hence also 1-connected, but not 3-connected.
{e4, e5, e6, e7, e8} is a disconnecting set, and indeed a cutset. {e2, e3, e4, e5} is a dis-
connecting set but not a cutset. The smallest cutsets are {e2, e3, e4} and {e8, e9, e10},
so λ(G) = 3. Thus G is 3-edge-connected, and also 1- and 2-edge connected, but not
4-edge-connected.
(ii) In the following graph G, κ(G) = λ(G) = 1. e, x and y are cut vertices.
Each of ex and yw is a bridge. If either is removed, the resulting graph has two
components. If both are removed then we get a graph with three components, one
being an isolated vertex.
17
Proposition 1.7 Let G be a connected graph with minimum vertex degree δ(G).
Then κ(G) ≤ λ(G) ≤ δ(G).
Proof
If G = Kn for some n, then κ(G) = λ(G) = δ(G) = n− 1. Now suppose G 6= Kn.
The set of all edges incident with any vertex is a disconnecting set (as their removal
isolates that vertex), so in any graph, λ(G) ≤ δ(G).
Assume G is a simple graph. If G = N1 then κ(G) = λ(G) = 0.
Otherwise λ(G) ≥ 1. Let {e1, . . . , eλ(G)} be a cutset, so G has subgraphs H1, H2
which become disonnected components when the cutset is removed.
Let x be the number of vertices of H1 that are incident to an edge in the cutset.
Clearly x ≤ λ(G).
If x < λ(G), then deleting these x vertices, with their incident edges, disconnects G
so κ(G) ≤ x. Hence κ(G) ≤ λ(G).
If x = λ(G), then consider any vertex in H1, v, say. Since G is simple, H1 is simple
so in H1, d(v) ≤ x− 1. Since x = λ(G), in G, exactly one of the edges in the cutset
is incident to v. Hence in G, d(v) = x. Therefore, we can construct a separating set
of size x by deleting all the adjacent vertices to v, so again κ(G) ≤ λ(G).
If G is not a simple graph, removing loops and multiple edges will produce a simple
graph G′ such that κ(G) = κ(G′) ≤ λ(G′) ≤ λ(G), so the result holds for G.
Proposition 1.8 Let G be a connected graph with at least three vertices. Then G
has a cut vertex if and only if there is a pair of vertices in G that do not lie on the
same cycle.
Proof
Suppose v is a cut vertex of G. Then G− v has two components; let u be in one and
w in the other. If u and w lie on a cycle in G then v must also lie on the cycle. With
the path u · · · v · · ·w removed, the rest of the cycle is another path from u to w which
connectes the two components in G− v. This is impossible, so u and w do not lie on
a cycle in G.
Conversely, assume G has no cut vertex. We need to show that every two vertices lie
on some cycle. Let u and w be distinct vertices of G.
18
If `(u,w) = 1, there is an edge e = uw which is not a bridge, since neither u nor w is
a cut vertex. Thus there is another path from u to w, which together with e forms a
cycle that includes u and w.
Make the inductive hypothesis that any two vertices u,w where `(u,w) < r lie on
some cycle. Now suppose `(u,w) = r.
Let P = v0v1 · · · vr be a path from u = v0 to w = vr. As `(v0, vr−1) < r, there is a
cycle C in G containing v0 and vr−1 by the hypothesis. C can be split into two paths
P1 and P2 from v0 to vr−1 which have no other vertices in common.
G − vr−1 is connected, as G has no cut vertex, so there is a path P3 from u to w in
G− vr−1. Let x be the last vertex of P3 that lies in C; assume x ∈ P1.
Let P ′1 be the part of P1 from u to x and Q

1 the part from x to vr−1.
Let P ′3 be the part of P3 from u to x and Q

3 the part from x to w.
Then P ′1 ∪Q′3 ∪wvr−1 ∪ P2 is a cycle in G containing u and w. The result follows by
induction.
This result can also be stated as follows:
G has no cut vertex if and only if every two distinct vertices are connected by two
paths that are internally-disjoint, i.e. they have no common vertices except their
initial and final vertices. In the above proof, P ′1 ∪Q′3 and P2 ∪ vr−1w are such paths.
19
1.2.3 Exercises
1. G is a simple graph with four components and ten vertices. Find the possible
numbers of edges of G.
2. Use Proposition 1.6 to show that a simple graph with 7 vertices and 16 edges
must be connected.
3. For each of the following graphs, identify all cut vertices and bridges (if any).
State the connectivity and the edge connectivity. In (b), find cutsets of order
λ(G) + 1 and λ(G) + 2.
4. State the connectivity and the edge connectivity of the following graphs.
5. Draw a connected graph G (not necessarily simple) in each of the cases:
(a) κ(G) = 1, λ(G) = δ(G) = 2, (b) κ(G) = 2, λ(G) = δ(G) = 3.
6. G is a finite graph (not necessarily connected) which has exactly two vertices u
and v of odd degree. Show that there is a path from u to v in G.
7. G is a graph in which every vertex has even degree. Show that there are no
bridges in G. Deduce that if G is connected, it is 2-edge-connected.
8. c is a cut vertex of a connected graph G. Prove that there are vertices u and v,
distinct from c, such that c lies on every path from u to v.
9. e is a bridge in a connected graph G. Prove that e does not lie in a cycle in G.
10. (a) Prove that the complement of a disconnected simple graph is connected.
(b) Show that the complement of a connected simple graph may or may not
be connected.
11. Show that if v is a vertex of a simple connected graph G then G− v = G− v.
Using this and the result of Question 10 (a), show that no vertex can be a cut
vertex of both G and G.
20
12. G is a simple graph of order n, such that δ(G) ≥
⌊n
2

.
(a) Show that G is connected.
(b) Suppose λ(G) < δ(G). Show that if λ(G) edges of G are deleted, each
component of the resulting graph has at least δ(G) + 1 vertices. Deduce
that λ(G) = δ(G) in this case.
21
1.3 Eulerian and Hamiltonian graphs
1.3.1 Eulerian graphs
The origin of Graph Theory is usually regarded as being Euler’s solution of the
Ko¨nigsberg Bridges problem in 1736. The Prussian city of Ko¨nigsberg (now Kalin-
ingrad in Russia) has four land areas linked by seven bridges. The problem was
whether it was possible to start in one of the four regions and cross each bridge
exactly once before returning to the starting point.
Euler’s model represents the land areas by the vertices of a graph and the bridges by
edges. The question is then whether this graph contains a trail that is closed (i.e. the
initial and final vertex are the same) and includes each edge.
Definition 1.13
An Eulerian trail in a graph is a closed trail which includes every edge.
An Eulerian graph is a graph which has an Eulerian trail.
Thus an Eulerian graph is one which can be drawn in a plane, starting and finishing
at the same point, without retracing any edge and without lifting the pen.
Note that while in general a trail need not be closed, an Eulerian trail is. For that
reason, some books call it an Eulerian tour, and use ‘Eulerian trail’ to mean any
trail (open or closed) that includes all the edges.
Proposition 1.9 For a non-trivial connected graph G, the following are equivalent:
(i) G is Eulerian, (ii) every vertex of G has even degree,
(iii) G is a union of edge-disjoint cycles.
Proof
(i) ⇒ (ii) If G is Eulerian then clearly it must be connected. An Eulerian trail
passes in and out of each vertex v, contributing 2 to d(v) each time it does so. As
every edge incident to v is in the trail, d(v) is even.
22
(ii) ⇒ (iii) The result is clearly true for the smallest connected graph satisfying
(ii), namely a loop, which is a single cycle. Make the inductive hypothesis that it is
true for all graphs that satisfy (ii) and have fewer edges than G.
As G is connected, no vertex has degree 0 so every vertex has degree ≥ 2. Thus by
Proposition 1.3 G contains a cycle C, say. If G = C we have the result. Otherwise
remove all the edges of C from G. The resulting graph H (which may be disconnected)
has fewer edges than G. Every vertex of H has even degree, since the vertex degrees
are either unchanged or reduced by 2. By the hypothesis each non-trivial component
of H is a union of edge-disjoint cycles, hence so is G. The result follows by induction.
(iii) ⇒ (i) Let C and H be as above. By traversing C, following each cycle in H
when it is first encountered, an Eulerian trail in G is obtained.
The solution of the Ko¨nigsberg Bridges problem is now immediate. The graph has
vertices of odd degree (indeed they are all odd) so no Eulerian trail exists. The pro-
posed tour of the city is impossible.
Given an Eulerian graph G, an Eulerian trail can be found as follows (Hierholzer’s
algorithm): start at any vertex. By Proposition 1.9 (iii), v lies on a cycle. If there
is a vertex w in this cycle that is incident to an edge not yet included, form another
cycle from w to w with only edges that have not already been used. Repeat until
all edges are included. We then have a set of edge-disjoint cycles whose union is an
Eulerian trail.
Example
This graph has degree sequence 4, 4, 4, 4, 2,
so it is Eulerian
Starting at u, we can form the obvious cycle uvyzxu. We can also find cycles vwzv
and xwyx. The union of these edge-disjoint cycles is an Eulerian trail uvwzvyzxwyxu.
Definition 1.14 A semi-Eulerian trail in a graph is an open trail which includes
every edge.
A semi-Eulerian graph is a non-Eulerian graph which has a semi-Eulerian trail.
Proposition 1.10 A connected graph is semi-Eulerian if and only if it has exactly
two vertices of odd degree.
23
Proof
Suppose there are just two vertices u, v of odd degree. Adding an edge uv produces a
graph in which all vertices have even degree, so it is Eulerian. An Eulerian trail from
u to u becomes a semi-Eulerian trail from u to v when we remove uv.
Conversely, suppose there is a semi-Eulerian trail v1 · · · vn but no Eulerian trail.
The edges in this trail have the form v1v2, v2v3, . . . , vn−2vn−1, vn−1vn. The vertices
v1, . . . , vn need not all be distinct but each appears an even number of times in the
list of edges, except for v1 and vn. As every edge is in the trail, all but two of the
vertices have even degree.
This shows that there is no trail that crosses each of the Ko¨nigsberg bridges once,
even if the starting and finishing point need not be the same, since there are more
than two odd-degree vertices.
In the route inspection problem, also known as the Chinese postman problem, a net-
work of roads is represented by a graph in which each edge is assigned a weight, i.e. a
number representing the distance along that edge, or the cost of travelling along it,
or some other relevant value. The problem is to find a closed walk, of minimum total
weight, including each edge at least once. In an Eulerian graph, the solution is an
Eulerian trail. In a semi-Eulerian graph, the solution is a semi-Eulerian trail together
with a minimum-weight path between the two odd-degree vertices.
Example
The weighted network shown has two odd-degree
vertices, A and E, so it is semi-Eulerian. A semi-
Eulerian trail between A and E has total weight
32. The minimum-weight path between A and E
is ABGE, of weight 4. Thus the smallest possible
total weight of a closed walk that includes each
edge is 36.
1.3.2 Hamiltonian graphs
Several well-known mathematical problems require a graph to be traversed in such a
way that each vertex is visited only once, starting and finishing at the same point -
for example the travelling salesman problem, in which a number of cities need to be
visited at minimal cost. The solution involves finding a cycle of the following type,
named after Sir William Hamilton.
24
Definition 1.15 A Hamiltonian cycle in a graph G is a closed path which passes
through each vertex of G exactly once.
A Hamiltonian graph is a graph which has a Hamiltonian cycle.
A non-Hamiltonian graph G is semi-Hamiltonian if there is a non-closed path in
G which includes every vertex.
The Knight’s Tour problem on a chessboard requires a knight to start on one square
and make legitimate moves that visit every square once, returning to the starting
point. This can be modelled by a graph with vertices representing the squares and
an edge joining any two squares that are connected by a knight’s move. The problem
is to find a Hamiltonian cycle. This can be generalised to m× n boards.
In a graph with only one vertex, the only possible Hamiltonian cycle is a single loop.
With just two vertices, a Hamiltonian cycle can only be a pair of parallel edges. If
there are three or more vertices then loops and parallel edges cannot form part of a
Hamiltonian cycle, so they can be ignored when looking for such a cycle. Furthermore,
a Hamiltonian graph cannot contain a cut vertex so it must be 2-connected.
Proposition 1.11
Let G be a simple graph with n vertices, where n ≥ 3. Each of the following is a
sufficient condition for G to be Hamiltonian:
(i) d(u) + d(v) ≥ n for every pair of non-adjacent vertices u and v (Ore’s theorem),
(ii) d(v) ≥ n
2
for each vertex v (Dirac’s theorem).
Proof
Suppose condition (i) holds and G is not Hamiltonian. Add extra edges to G, which
will certainly preserve the inequality, until a graph G′ is obtained which would be
made Hamiltonian by adding another edge. (This is possible since Kn is clearly
Hamiltonian.) Now in G′ there must be a path of the form v1 · · · vn, passing through
all the vertices, which would become a Hamiltonian cycle with the edge vnv1 added.
v1 and vn are not adjacent in G so d(v1) + d(vn) ≥ n by assumption, hence each of
v2, . . . , vn−1 must be adjacent to at least one of v1 and vn, and at least two must be
Suppose that whenever vi is adjacent to v1, vi−1 is not adjacent to vn. Let k be
the largest number for which vk is adjacent to v1. Then vk, vk−1, . . . , v2 are adjacent
to v1 but not to vn, and vk+1, . . . , vn−1 are adjacent to vn but not to v1. But then
d(v1) + d(vn) = n − 2 < n. Thus there is some vertex vi, adjacent to v1, such that
vi−1 is adjacent to vn in G (and in G′).
25
Then v1v2 · · · vi−1vnvn−1 · · · viv1 is a Hamiltonian cycle in G′, giving a contradiction.
Hence if (i) holds, G is Hamiltonian.
Clearly (ii) implies (i).
Note that the conditions in Proposition 1.11 are sufficient but not necessary. There
are plenty of Hamiltonian graphs that do not satisfy the conditions in Dirac’s or Ore’s
theorem, such as the cycle graphs Cn for n ≥ 5.
Examples
G1 has 8 vertices, each with degree 4, so G1 is Hamiltonian. G2 has 7 vertices, and
each of the non-adjacent pairs has degree sum 7 or more, so G2 is also Hamiltonian.
There is no simple necessary and sufficient condition for a graph to be Hamiltonian.
The following necessary condition is sometimes useful.
Proposition 1.12 If G is a Hamiltonian graph then for every non-empty proper
subset S of V (G), the number of components of G− S is less than or equal to |S|
Proof
Let C be a Hamiltonian cycle in G and let S be a non-empty proper subset of V (G).
Removing all the vertices in S from C separates C into at most |S| components, this
maximum occurring when no two vertices in S are adjacent in C.
C is a spanning subgraph of G, so C − S is a spanning subgraph of G − S. Thus
G− S cannot have more components than C − S. The result follows.
Example
Five people A,B,C,D,E are to be seated around a circular table. The following
pairs are acquainted: (A,C), (A,E), (B,C), (B,E), (C,D), (D,E). Is it possible to
arrange them so that everyone is sitting between two acquaintances?
Represent the people as vertices of a graph, with edges joining acquaintances. We see
that deleting the two vertices C and E, and their incident edges, would separate the
graph into three components (each an isolated vertex). As 3 > 2, Proposition 1.12
shows that no Hamiltonian cycle exists so the desired arrangement is not possible.
26
1.3.3 Exercises
1. Find conditions for the following to be Eulerian or semi-Eulerian:
Cn, Wn, Kn, Kr,s.
2. Show that the graph of the octahedron is Eulerian and find an Eulerian trail in
it. Which of the other Platonic graphs are Eulerian?
3. Prove that in any connected graph there is a closed walk which traverses each
edge exactly twice.
4. Show that the following graph G is semi-Eulerian. State how G can be made
Eulerian by adding an edge. Find a semi-Eulerian trail in G.
5.
The network represents eight towns and the roads
joining them, with distances given for each road
imaginary extra roads between two pairs of towns,
and that there are three ways of doing this. Hence
find the minimum distance that the courier must
cover.
6. A king in chess can move to a horizontally or vertically adjacent square. Show
that on a normal 8 × 8 board it is impossible for a king to make a sequence
of such moves which cross every line between squares exactly once. Find the
dimensions of all square or rectangular boards for which this is possible.
7. For n ≥ 3, determine which of the following are Hamiltonian: Cn, Wn, Kn.
8. Show that a bipartite graph with an odd number of vertices is not Hamiltonian.
9. Prove that if a bipartite graph G(U,W ) is Hamiltonian then U and W contain
the same number of vertices.
10. Classify each of the following as Eulerian, semi-Eulerian, Hamiltonian, semi-
Hamiltonian or none of these:
27
11. Consider an n× n board, with squares coloured alternately black and white as
usual. Given that a knight’s move always moves from a square of one colour to
a square of the other colour, show that a knight’s tour is impossible when n is
odd.
12. Six people A,B,C,D,E, F are to be seated around a circular table. Determine
whether it is possible to arrange them so that everyone is sitting between two
acquaintances, in the cases where the following pairs are acquainted:
(a) (A,B), (A,C), (B,D), (B,F ), (C,D), (C,E), (D,F ), (E,F ).
(b) (A,C), (A,D), (A,F ), (B,C), (B,D), (B,E), (C,E), (C,F ), (D,E), (D,F ).
(c) (A,C), (A,F ), (B,C), (B,E), (C,D), (C,E), (C,F ), (D,E).
13. Let G be a connected simple graph with n ≥ 3 vertices. Suppose that there is a
positive integer k ≤ n such that d(u) + d(v) ≥ k for every pair of non-adjacent
vertices u and v. Show that there is a path of length k in G.
14. G is a simple graph with n vertices.
(a) Let G′ = G − {u, v}, where u and v are any two non-adjacent vertices in
G. Show that |E(G′)| = |E(G)| − d(u)− d(v).
(b) Now suppose G has
(
n− 1
2
)
+ 2 edges. Use the fact that G′ is a subgraph
of Kn−2 to show that
(
n− 1
2
)
+ 2− d(u)− d(v) ≤
(
n− 2
2
)
.
(c) Hence show that d(u) + d(v) ≥ n and deduce that G is Hamiltonian.
(d) Give an example of a non-Hamiltonian graph with
(
n− 1
2
)
+ 1 edges.
28
1.4 Trees
1.4.1 Trees
Definition 1.16 A tree is a connected graph which is cycle-free, i.e. it contains no
closed paths.
A forest is a graph in which each component is a tree.
Here are some trees. Their union is a forest.
From the diagrams, it appears that any non-trivial tree with n vertices has n − 1
edges. Assuming this (which is proved below), in a tree with n > 1 vertices and m
edges we have
n∑
i=1
d(vi) = 2m = 2n − 2 < 2n, so there are at least two vertices of
degree 1.
Proposition 1.13 For a graph G with n ≥ 2 vertices and m edges, the following are
equivalent:
(i) G is a tree;
(ii) there is a unique path between any two vertices in G;
(iii) G is connected and every edge of G is a bridge;
(iv) G is connected and m = n− 1;
(v) G contains no cycles and m = n− 1;
(vi) G contains no cycles and, if any two vertices of G are joined by a new edge e,
then G ∪ {e} has exactly one cycle.
Proof
(i) ⇒ (ii): As G is connected, there is a path between any two vertices. If there
were two such paths, their union would contain a cycle, so the path is unique.
(ii)⇒ (iii): If (ii) holds then G must be connected. Any edge uv of G is the unique
path joining u and v so if it is removed then there is no path from u to v, making G
disconnected. Thus uv is a bridge.
29
(iii) ⇒ (iv): If n = 2 then there is one edge, so m = n − 1. Now let n > 2 and
ssume that the implication holds when the number of vertices is less than n. When
there are n vertices, deleting an edge produces two connected components G1, G2,
each satisfying (iii), with n1, n2 vertices where n1 < n, n2 < n. By the hypothesis, G1
and G2 have n1 − 1, n2 − 1 edges respectively, so G has n1 − 1 + n2 − 1 + 1 = n− 1
edges. The result follows by induction.
(iv) ⇒ (v): Suppose G is connected with m = n − 1 and has a cycle of length r.
This contains r vertices and r edges. Each of the n − r vertices not on this cycle is
incident with one edge on a shortest path from it to the cycle, so G has at least n
edges, i.e m ≥ n. This contradicts (iv), so G is cycle-free.
(v) ⇒ (vi): Suppose G is cycle-free with m = n − 1. If G has k components then
adding k − 1 edges would create a tree with n vertices, so m + (k − 1) = n − 1 and
thus k = 1, i.e. G is connected.
Hence G is a tree so by (ii) there is a unique path P between any two vertices u, v of
G. Joining u and v by a new edge e gives a unique cycle P ∪ {e} in G ∪ {e}.
(vi) ⇒ (i): If G is not connected then any two vertices in different components
can be joined without creating a cycle. Thus if (vi) holds then G is connected and
cycle-free, so G is a tree.
We can distinguish between labelled and unlabelled trees. Here we use numbers to
label the vertices.
The following are isomorphic, but distinct, labelled trees. We see that there are three
different labelled trees with 3 vertices.
1.4.2 Prufer sequences
Proposition 1.14 The number of distinct labelled trees with n vertices is nn−2.
Proof
The result is clear if n = 1 or n = 2. Now assume n ≥ 3.
Given a tree with its vertices labelled 1, . . . , n, we construct a sequence of n − 2
elements of {1, . . . , n} as follows:
Select the end-vertex with the smallest label; call this label b1. Let a1 be the vertex
adjacent to b1. Delete b1 and the edge a1b1, leaving a labelled tree with n−1 vertices.
30
Repeat the procedure: select the end-vertex of the new tree with the smallest label
b2 and let the adjacent vertex be a2. Delete b2 and the incident edge. Continue until
only two vertices remain, at which point we have a sequence a1, a2, . . . , an−2.
Conversely, given such a sequence a1, . . . , an−2, let b1 be the smallest label in {1, . . . , n}
that is not in the sequence. Join the points labelled b1 and a1. Let b2 be the smallest
label not in b1, a2, . . . , an−2 and join it to a2. Repeat until there are only two labels
not in b1, . . . , bn−2, and join the points with these labels to get a tree. This tree will,
by the process described earlier, generate the sequence that we started with.
Thus there is a one-to-one correspondence between labelled trees and sequences.
There are n possible values for each of n−2 terms, so the number of possible sequences
is nn−2.
Definition 1.17 The sequence obtained in the above proof is called a Pru¨fer se-
quence.
Each such sequence of n−2 positive integers uniquely determines a labelled tree with
n vertices, and vice-versa. The Pru¨fer sequence for a tree has 2 fewer terms than the
number of vertices in the tree.
To construct the Pru¨fer sequence from the tree:
Remove the end-vertex with the smallest label, and its incident edge, from the tree.
Put the label of the adjacent vertex (now an end-vertex) in the sequence. Repeat
with the remaining tree until only two vertices remain - do not put them into the
sequence.
Note that all the numbers in the sequence are labels of vertices that were not end-
vertices in the original tree.
Example
The smallest end-vertex label is 2. It is adjacent to 6. Delete 2 and start the sequence
with 6.
The smallest end-vertex label is now 3. It is adjacent to 1. Delete 3. The sequence
becomes 6, 1.
The smallest end-vertex label is now 4. It is adjacent to 1. Delete 4. The sequence
becomes 6, 1, 1.
31
The smallest end-vertex label is now 1. It is adjacent to 6. Delete 1. The sequence
becomes 6, 1, 1, 6.
Only two vertices (5, 6) remain so the Pru¨fer sequence is complete: it is 6, 1, 1, 6.
To construct the tree from the Pru¨fer sequence:
Start with a null graph Nn, where n is 2 more than the length of the sequence. Take
the smallest number in the list 1, . . . , n that is not in the sequence. Join this to the
first term in the sequence. Delete the numbers from the two lists and repeat with
the remaining lists until only two numbers remain in the first list. Join these and the
tree is complete.
Example
Construct a tree with the Pru¨fer sequence 2, 3, 2, 1, 5.
The tree will have seven vertices. 4, 6 and 7, which are not in the sequence, will be
end-vertices.
Comparing 1, 2, 3, 4, 5, 6, 7 with 2, 3, 2, 1, 5, the smallest number not in the Pru¨fer
sequence is 4. Join it to the first in the sequence, 2.
Comparing 1, 2, 3, 5, 6, 7 with 3, 2, 1, 5, the smallest number not in the Pru¨fer
sequence is 6. Join it to the first in the reduced sequence, 3.
Comparing 1, 2, 3, 5, 7 with 2, 1, 5, the smallest number not in the Pru¨fer sequence
is 3. Join it to 2.
Comparing 1, 2, 5, 7 with 1, 5, the smallest number not in the Pru¨fer sequence is 2.
Join it to 1.
Comparing 1, 5, 7 with 5, the smallest number not in the Pru¨fer sequence is 1. Join
it to 5.
Now only 5 and 7 remain. Join them to complete the tree:
32
1.4.3 Spanning trees and forests
Definition 1.18 A spanning tree for a graph G is a subgraph T , which is a tree,
such that V (T ) = V (G).
If G is disconnected, a spanning forest for G is a union of spanning trees for all
its components.
Example
The Petersen graph, with 10 vertices, and two spanning trees, each with 10 − 1 = 9
edges.
Proposition 1.15 A graph is connected if and only if it has a spanning tree.
Proof
Assume G has a spanning tree T . Then there is a path in T , and hence in G, between
any pair of vertices, so G is connected.
Conversely, suppose G is connected. If G is not a tree then it contains a cycle. Re-
moving one edge of the cycle will not disconnect G. If the remaining graph is not
a tree, repeat the process. Continue until a tree is obtained. No vertices of G have
been removed, so we have a spanning tree.
It follows from Proposition 1.14 that there are nn−2 different spanning trees of Kn.
From Proposition 1.15, every graph has a spanning forest. In a graph G with n
vertices and c components, a spanning forest has n− c edges. Thus if G has m edges
then m− n+ c edges must be removed from G to obtain a spanning forest.
Proposition 1.16 Let T be a spanning forest of a graph G. Then
(i) each cutset of G has an edge in common with T ,
(ii) each cycle of G has an edge in common with the complement of T .
33
Proof
(i) Let S be a cutset of G, so if the edges in S are removed then some component H
of G is split into disjoint subgraphs H1 and H2. As T is a spanning forest, it includes
a spanning tree for H and thus contains an edge joining a vertex of H1 to a vertex of
H2. This edge must be in S.
(ii) Let C be a cycle in G and suppose no edge of C is in T . Then C is a subgraph of
T , but T contains no cycles. We have a contradiction, so C has an edge in common
with T .
Definition 1.19 Let G be a graph with n vertices, m edges and c components.
The cutset rank of G is ξ(G) = n− c.
The cycle rank or nullity of G is γ(G) = m− n+ c.
In particular, for a connected graph, γ(G) = m− n+ 1 and ξ(G) = n− 1.
In some applications, a particular vertex of a tree is identified as a root and the graph
is called a rooted tree. The root is usually shown at the bottom of a drawing. Any
vertex can be a root; for example, the graph on the left can be drawn as the rooted
tree on the right.
Tree diagrams for probability problems are examples of rooted trees. In that case the
root is usually shown on the left.
34
1.4.4 Exercises
1. Draw all the labelled trees with four vertices. By considering the possible lengths
of longest paths, or otherwise, find all unlabelled trees with seven vertices.
2. Find the sum of the degrees of all the vertices in a tree with n vertices, where
n ≥ 2.
3. Suppose a tree has an even number of edges. Show that it has at least one
vertex of even degree.
4. Show that any tree T has at least ∆(T ) end vertices.
5. Show that every tree with more than one vertex is a bipartite graph.
6. Show that the complete graph Kr,s (where r, s ∈ N) is a tree if and only if at
least one of r and s is 1.
7. Show that a semi-Hamiltonian tree must be a path graph.
8. Find the Pru¨fer sequence for each of the following labelled trees.
9. Draw labelled trees with Pru¨fer sequences
(a) 1, 2, 3, 4, 5, 6, (b) 3, 2, 3, 4, 2, (c) 1, 2, 1, 2, 1, 2, (d) 7, 7, 7, 7, 7.
10. What can be said about trees with Pru¨fer sequences in which the terms are
(a) all the same, (b) all different?
11. Let pk be the number of occurrences of the number k in a Pru¨fer sequence for
a labelled tree T . Find the degree of vertex k in T .
12. T is a tree with n vertices in which every vertex has degree 1 or 3. Show that
n is even and find the number of vertices of each degree, in terms of n.
13. Find the number of spanning trees of (a) a labelled complete graph K5,
(b) the graph in Example 1.1.1.
35
14. Find the cycle rank and the cutset rank of each of the following: K5, K3,3, K3,3,
W5, N5, the Petersen graph, a tree with n vertices.
15. For any n ≥ 2, let G be the graph obtained from Kn by deleting any one edge.
Show that G has (n− 2)nn−3 spanning trees.
36
Chapter 2
Planar graphs, colouring, matching
and flows
2.1 Planar graphs and dual graphs
2.1.1 Planar graphs
Definition 2.1 A planar graph is a graph that can be drawn in a plane in such a
way that edges intersect only at vertices to which they are incident.
A plane graph is a planar graph drawn in such a way in a plane.
It may not be apparent whether a given graph is planar. The following method can
be applied to a Hamiltonian graph G. First find a Hamiltonian circuit C (which is
not necessarily unique), then try to divide the edges that are not in C into two sets
A and B, such that the edges in A and in B can be drawn, without crossing, inside
and outside C respectively. If this is possible, G is planar.
Example
In the graph below, there is a Hamiltonian cycle tuxwvyzt. Draw this as a heptagon.
If the edge zu is drawn inside the heptagon then zv and zw can also go inside without
crossing. Then tx, tw and wy will have to go outside the heptagon. They can be drawn
without crossing, as shown, so the graph is planar. We can check that the vertices
have the same degrees as in the original drawing. The number of edges drawn must
be half the sum of the degrees.
37
Definition 2.2 A face of a plane graph is a region bounded by edges. There is an
infinite face lying outside the graph.
The degree (or face degree) of a face F , denoted by d(F ), is the number of edges
that form the boundary of F . If an edge is incident to a vertex of degree 1 inside F ,
it contributes 2 to d(F ).
If all faces have the same degree r then the graph is face-regular of degree r.
Example
This plane graph has 9 vertices, 12 edges and
5 faces, labelled F1, . . . , F5. The face degrees
are: d(F1) = 2, d(F2) = 8, d(F3) = 1, d(F4) =
3, d(F5) = 10. (The edges with end-vertices in-
side F2 and F5 have each been counted twice.)
Note that the sum of the face degrees, 24, is twice the number of edges. The following
result, which corresponds to Proposition 1.1, shows why this is so.
Proposition 2.1 (i) Let G be a plane graph with m edges and f faces F1, . . . , Ff .
Then
f∑
i=1
d(Fi) = 2m.
(ii) The number of faces of odd degree in any plane graph is even.
Proof
(i) Each edge e has faces Fi and Fj (which may be the same) on either side of it. In
calculating the sum of the face degrees, e is counted in both d(Fi) and d(Fj). Thus
the sum of the face degrees is twice the number of edges.
(ii) Suppose there are p odd-degree faces and q even-degree faces. Then the sum of
the face degrees is the sum of p odd numbers and q even numbers. By (i) this sum is
even, so p must be even.
Proposition 2.2 (Euler’s formula) Let G be a connected plane graph with n ver-
tices, m edges and f faces. Then n−m+ f = 2.
38
Proof
If m = 1 then G has one edge, two vertices and one (infinite) face, so the result holds.
Assume it holds for all connected plane graphs with fewer than m edges. Now let G
have m edges. If G is a tree then m = n− 1 and f = 1, so n−m+ f = 2.
If G is not a tree then it contains a cycle. Let e be an edge in this cycle. Removing e
combines two faces into one, so G−e is a plane graph with n vertices, m−1 edges and
f−1 faces. By the hypothesis, n−(m−1)+(f−1) = 2 and thus again n−m+f = 2.
The result follows by induction on m.
Now consider a convex polyhedron with n vertices, m edges and f faces. By projecting
the figure onto a plane we obtain a plane graph with the same values of n,m and f ;
one face of the polyhedron becomes the infinite face of the graph. Thus the formula
n−m+ f = 2 holds for the polyhedron.
We can use this to establish that the five platonic solids are the only convex polyhedra
which are regular, in the sense that their faces all have the same number of edges,
and the same number of edges meet at each vertex. That is, each vertex has the same
degree d ≥ 3 and each face has the same degree r ≥ 3.
By Propositions 1.1 and 2.1, dn = rf = 2m. Also n−m+ f = 2.
Combining these equations gives
2m
d
− m + 2m
r
= 2, so
1
d
+
1
r
=
1
m
+
1
2
where
d, r,m ∈ N. This is impossible if d ≥ 4 and r ≥ 4, since then 1
d
+
1
r
≤ 1
2
, so at least
one of d and r is 3. Then the other one cannot be more than 5.
The possible pairs (d, r) are thus (3, 3), (3, 4), (3, 5), (4, 3), (5, 3). When d = r = 3 we
have 3n = 3f = 2m, so n = f = 4,m = 6, giving the tetrahedron. Similarly, the
other pairs give the other Platonic solids.
Proposition 2.3 Let G be a connected simple planar graph with n ≥ 3 vertices and
m edges. Then m ≤ 3n− 6. If G contains no triangles then m ≤ 2n− 4.
Proof
Consider a plane drawing of G. As G is simple and has at least 3 vertices, each face
is bounded by at least three edges. Thus if f is the number of faces then 2m ≥ 3f by
Proposition 2.1. Now n−m+f = 2, so 2m ≥ 3(2+m−n). Hence 2m ≥ 6+3m−3n,
so m ≤ 3n− 6.
If G has no triangles then each edge is bounded by at least four faces, so 2m ≥ 4f ,
giving m ≤ 2n− 4.
39
2.1.2 Kuratowski’s theorem
Proposition 2.4 K5 and K3,3 are non-planar graphs.
Proof
K5 and K3,3 are certainly connected simple graphs with more than two vertices.
K5 has n = 5 vertices and m = 10 edges, so m > 3n − 6, hence by Proposition 2.3
K5 is non-planar.
K3,3 is bipartite, so it contains no triangles. It has n = 6 vertices and m = 9 edges,
so m > 2n− 4, hence by Proposition 2.3 K3,3 is non-planar.
Proposition 2.5 Every simple planar graph G has at least one vertex whose degree
is not more than 5.
Proof
Clearly the result holds for G if and only if it holds for each component of G, so we
may assume that G is connected. If G has one or two vertices (indeed, up to six)
then the result is obvious, so we may assume Proposition 2.3.
Suppose each vertex has degree 6 or more. Then by Proposition 1.1, 2m =

v∈G
d(v) ≥
6n, so m ≥ 3n. But by Proposition 2.3 m ≤ 3n− 6, giving a contradiction. Hence G
has a vertex of degree ≤ 5.
Definition 2.3 Graphs G1 and G2 are homeomorphic if they can both be obtained
from a graph G by inserting new vertices of degree 2 on its edges. Each of G1 and G2
is then a subdivision of G.
Proposition 2.6 (Kuratowski’s Theorem) A graph is planar if and only if it has
no subgraph homeomorphic to K5 or to K3,3.
Note that if G1 is obtained from G by inserting vertices of degree 2 then G1 is
homeomorphic to G. Thus if we are given a graph G and can obtain K5 or K3,3 by
deleting some edges and replacing paths by single edges, then G is non-planar. In
particular, if G contains K5 or K3,3 then it is not planar.
Example
Consider the Petersen graph. It has no subgraph homeomorphic to K5 but it does
have a subgraph homeomorphic to K3,3 as shown, so it is not planar.
40
See the exercises for another way of showing that this graph is non-planar.
2.1.3 Geometric dual
Now let G be a plane graph with n vertices, m edges and f faces (including the
infinite face). Construct a new graph G∗ as follows. Place a vertex in each face of G,
including one in the infinite face. For each edge e in G, draw an edge which crosses
e (and no other edge of G), joining the vertices in the faces on either side of e.
Definition 2.4 The graph G∗ described above is called the geometric dual of G.
Example
The graph G on the left (with the thick edges) has four faces, including the infinite
face. One face is the interior of a loop; another lies between a pair of parallel edges.
The dual G∗ has vertices u1, u2, u3, u4, one in each face, as shown.
The thinner lines show a way of constructing the dual as a plane graph - one edge of
G∗ must cross each edge of G, and the edges must not cross except at vertices. The
dual can be tidied up slightly, as on the right.
Proposition 2.7 Let G be a plane connected graph with n vertices, m edges and f
faces. Then G∗ is a plane graph with f vertices, m edges and n faces.
41
Proof
G∗ is clearly a plane graph, by construction. It has f vertices, one in each of the f
faces of G. One edge of G∗ is drawn to cross each edge of G, so G and G∗ have the
same number of edges. It follows from Euler’s formula that G∗ has n faces.
By the method of construction of G∗, a vertex of degree k in G corresponds to a face
of degree k in G∗, and vice-versa.
Given a planar graph G we can start with a plane drawing of G, which is not unique
in general, and follow the given procedure to obtain a particular plane graph G∗.
Starting from that plane drawing of G∗ (not re-drawing it to get an isomorphic graph)
we can follow the procedure again to obtain (G∗)∗, which we write as G∗∗, the double
dual of G. The construction of G∗∗ from G∗ reverses the steps in the construction of
G∗ from G, so G∗∗ = G.
In Example 2.1.3, if we start with G∗, place a vertex in each face and join them
appropriately we get back to G. However, this will not necessarily work if we start
with a different drawing of G∗, e.g. with the loop at u1 not enclosing u4.
Thus isomorphic graphs do not in general have isomorphic duals. In the example
below, the graphs with the thicker edges are different plane drawings of the same
graphs. Their duals, drawn with the thinner edges, cannot be isomorphic because
their vertices have different degrees: 6, 3, 3 in the first case and 5, 4, 3 in the second.
Proposition 2.8 Let G be a plane graph with geometric dual G∗. A set of edges of
G forms a
{
cycle
cutset
}
in G if and only if the corresponding set of edges of G∗ forms
a
{
cutset
cycle
}
in G∗. A cycle of length k in either graph corresponds to a cutset with k
edges in the other.
Proof
We may consider each component of G separately, so assume G is a connected plane
graph containing a cycle C. In the region bounded by the edges in C there is at
42
least one face, in which a vertex of G∗ is located. Let S be the set of all vertices of
G∗ that lie inside C and let T be the set of all edges in G∗ that cross the edges in
C. Removing the edges in T disconnects the vertices of G∗ in S from the rest. No
proper subset of T can have this property, so T is a cutset in G∗. Clearly T con-
tains the same number of edges as the cycle C. The converse follows since G∗∗ = G.
In Example 2.1.3 there is a cycle C = v1v2v3v1 in G using either of the parallel edges.
Take the left-hand one in the drawing; then S = {u2, u3} is the set of vertices inside
C. Let T be the set consisting of u1u3 and the two parallel edges u1u2. This is a
cutset in G∗ as it disconnects u2 and u3 from u1 and u4, thus disconnecting G∗ into
two components, but removing any subset of T would not disconnect G∗.
Similarly, the cutset consisting of the edge v3v4 in G corresponds to the cycle that is
the loop at u1 in G
∗.
Results about plane graphs can be dualized using the correspondences established
above. By Proposition 2.3, if a connected simple plane graph has n ≥ 3 vertices and
m edges then m ≤ 3n−6. Now G being simple means that it has no loops of multiple
edges, i.e. no cycles of length 1 or 2. These correspond to cutsets with 1 or 2 edges
in G∗, so the dualized result is: if a connected, 3-edge-connected plane graph has m
edges and f faces then m ≤ 3f − 6.
Proposition 2.9 A connected plane graph G is bipartite if and only if G∗ is Eulerian.
Proof
G is bipartite ⇔ G has no cycle of odd length (by Proposition 1.4)
⇔ G∗ has no cutset with an odd number of edges (by Prop. 2.8)
⇔ G∗ has no vertices of odd degree (see Exercises 2.1, Q. 17)
⇔ G∗ is Eulerian (by Proposition 1.9).
43
2.1.4 Maximal planar graphs
Definition 2.5 A maximal planar graph is a simple planar graph which would be
Proposition 2.10 A simple planar graph G is maximal if and only if, in any plane
drawing of G, every face has degree 3. In a maximal planar graph with n vertices and
m edges, m = 3n− 6.
Proof
Let G be a simple planar graph drawn in a plane. As G is simple, no face has degree
1 or 2.
Suppose there is a face F with degree > 3, so there are vertices v1, . . . , vk inside or
on the boundary of F , where k ≥ 4. If a new vertex is placed inside F and joined it
to each of v1, . . . , vk, the resulting graph is still planar. If each pair of v1, . . . , vk were
adjacent there would be a subgraph isomorphic to K5, which is non-planar. Hence
some pair is non-adjacent in G. Joining them with an edge in G, the resulting graph
is still planar so G is not maximal planar.
Conversely, if every face (including the external face) has degree 3 then 3f = 2m,
hence m = 3n−6. Certainly G is simple with at least three vertices. If more edges are
added between non-adjacent vertices then the graph is still simple and m > 3n − 6,
so it becomes non-planar. Thus G is maximal planar.
Proposition 2.10 shows that this is a maximal planar graph. All faces, including the
infinite face, are bounded by three edges. n = 11 and m = 27 = 3n− 6.
44
2.1.5 Exercises
1. Make plane drawings of the following graphs:
For each of your plane graphs, state the number of faces, find the face degrees
and verify Propositions 2.1 and 2.2.
2. Verify Euler’s formula for each of the platonic graphs.
3. A plane connected simple graph has degree sequence 6, 5, 5, 4, 3, 3, 2. Find how
many faces it has.
4. G is a 3-regular connected plane graph with 24 vertices. Find the number of
faces in G.
5. If a connected graph with n vertices and m edges is face regular of degree r,
express m in terms of n and r.
6. Show that a simple connected planar graph with fewer than 12 vertices has at
least one vertex whose degree is not more than 4.
7. Let G be a plane graph with n vertices, m edges, f faces and c components.
Deduce from Euler’s formula that n−m+ f = c+ 1.
8. The girth of a graph G is the length of the shortest cycle in G. Use Euler’s
formula to show that if G is a connected planar graph of girth 5 then m ≤
5
3
(n− 2). Deduce from this that the Petersen graph is not planar.
9. G is a connected plane graph in which each vertex has degree at least 3, and
each face is bounded by either 5 or 6 edges. Show that at least 12 faces are
bounded by 5 edges.
10. Three houses are to be connected to three utility supplies: electricity, gas and
water. Can this be done in such a way that the supply lines do not cross?
11. Use Kuratowski’s theorem to show that the following graphs are not planar.
45
12. Construct the geometric dual of the following graph G:
List the face degrees and the vertex degrees of each of G and G∗.
13. Show that the following two graphs are isomorphic but that their geometric
duals are not isomorphic. (There is no need to draw the duals.)
14. Show that if a connected plane graph with n vertices and m edges is isomorphic
to its geometric dual, then m = 2(n− 1).
15. Consider the graph G in Example 1.1.1. Without drawing it, state the length
of the longest cycle in G∗ and the value of the edge connectivity λ(G∗).
16. Investigate the geometric duals of trees, cycle graphs and wheel graphs.
17. Suppose a graph G has a cutset consisting of an odd number of edges. Show
that G has a vertex of odd degree.
18. Determine which of the Platonic graphs are maximal planar graphs.
19. G is a maximal simple planar graph with n vertices and m edges. There are ki
vertices of degree i, for i = 1, . . . , n− 1. Show that
n−1∑
i=1
(6− i)ki = 12.
20. Show that in a maximal planar graph, every vertex has degree at least 3. Deduce
that such a graph has at least four vertices of degree ≤ 5. Hence show that
every simple planar graph has at least four vertices of degree ≤ 5.
46
2.2 Graph colourings
2.2.1 The chromatic number and the greedy algorithm
Definition 2.6 A colouring (sometimes called a proper colouring) of the ver-
tices/edges/faces of a graph is an assignment of colours such that no two distinct
adjacent vertices/edges/faces have the same colour. It is a k-colouring if at most k
colours are used. If a k-colouring of the vertices exists, the graph is k-colourable.
The chromatic number χ(G) is the smallest k ∈ N for which the graph G is k-
colourable. For this k, we say that G is k-chromatic.
Note that colouring always refers to vertices unless otherwise stated. Terms such as
k-edge colouring and k-face colourable can be used for clarity in other cases.
Clearly χ(G) cannot be more than the number of vertices of G. χ(Kn) = n, so if
G has a subgraph isomorphic to Kn then χ(G) ≥ n. Furthermore χ(G) = 1 if and
only if G is a null graph, and χ(G) = 2 if and only if G is bipartite. Graphs with
χ(G) = 3 include Cn and Wn for any odd integer n ≥ 3.
If G is k-colourable, then clearly so is any subgraph of G. Indeed, if H is a subgraph
of G then χ(H) ≤ χ(G).
There are various algorithms for colouring graphs. The following method, known as
the greedy algorithm, is a simple method for finding a vertex colouring. Label the
vertices v1, . . . , vn and the colours 1, 2, . . . For i = 1, . . . , n, assign to vi the lowest-
numbered colour that is not already assigned to an adjacent vertex. Certainly χ(G)
cannot be greater than the highest-numbered colour that is used, so this method
gives an upper bound for the chromatic number. Different orderings of the vertices
can require different numbers of colours.
Example
Consider the following graph (from Exercises 1.3 Question 4).
Colouring the vertices in the order v1, . . . , v9, the greedy algorithm assigns colours as
follows:
v1 : 1, v2 : 2, v3 : 1, v4 : 3, v5 : 4, v6 : 1, v7 : 2, v8 : 2, v9 : 3.
Colouring them in the reverse order v9, . . . , v1, we get:
47
v9 : 1, v8 : 2, v7 : 2, v6 : 3, v5 : 2, v4 : 1, v3 : 3, v2 : 4, v1 : 1.
We have two 4-colourings. The graph is 4-colourable. Clearly at least 4 colours are
needed since the graph contains K4, so the graph is 4-chromatic.
Recall that ∆(G) denotes the largest degree of any vertex in G.
Proposition 2.11 Let G be a simple graph. Then χ(G) ≤ ∆(G) + 1.
Proof
The result clearly holds for N1, a simple graph with one vertex, for which χ(G) = 1
and ∆(G) = 0.
Assume it holds for all graphs with fewer than n vertices. Now let G have n vertices,
so G−v has n−1 vertices. Clearly ∆(G−v) ≤ ∆(G), so by the hypothesis χ(G−v) ≤
∆(G− v) + 1 ≤ ∆(G) + 1.
Take a (∆(G) + 1)-colouring of G− v. At most ∆(G) colours are used on the vertices
adjacent to v in G, so we can give v a different colour from these to get a (∆(G) + 1)-
colouring of G. Thus χ(G) ≤ ∆(G) + 1. The result follows by induction.
2.2.2 The five and four colour theorems
Proposition 2.12 (The Five Colour theorem)
Every planar graph is 5-colourable.
Proof
As loops and multiple edges do not affect the adjacency of vertices, it is enough to
prove the result for simple graphs.
Let G be a simple planar graph with n vertices. The result is obvious for n ≤ 5 as
G is then n-colourable. Make the inductive hypothesis that the result holds for all
simple planar graphs with fewer then n vertices.
By Proposition 2.5, G has a vertex v of degree ≤ 5.
Suppose d(v) < 5. By the hypothesis there is a 5-colouring of G − v, in which the
vertices which are adjacent to v in G have at most four different colours. There is
then another colour available which can be assigned to v, giving a 5-colouring of G.
Now suppose d(v) = 5. Let u1, . . . , u5 be the vertices adjacent to v. If each pair out
of u1, . . . , u5 were adjacent then G would have K5 as a subgraph, so would not be
planar. Thus at least two of these vertices, say ui and uj, are not adjacent.
Contract the edges uiv and ujv, so that ui, uj and v are merged into a single vertex w
incident to all edges that were incident to ui, uj or v. Replace any resulting parallel
48
edges by single edges. The resulting graph is simple, planar and has fewer than n
vertices, so is 5-colourable by the hypothesis.
Reinstate v and the two edges that were removed. Assign the colour of w to ui and
uj, since they are not adjacent in G. The vertices adjacent to v now have at most
four colours, so v can be given a different colour from them to produce a 5-colouring
of G. The result follows by induction on n.
Proposition 2.13 (The Four Colour theorem)
Every planar graph is 4-colourable.
The original motivation for graph-colouring problems was the colouring of maps.
The question as to whether all maps are 4-colourable was posed by Francis Guthrie
to Augustus De Morgan in 1852. There were many flawed attempts at proofs. The
Four Colour theorem is generally regarded as having been proved in 1976 by Appel
and Haken. Refinements have followed since then. The method involves computer
analysis of a large number of cases, so it cannot easily be checked by hand.
In the kind of map that we wish to colour, each region (e.g. a country or county) is
represented by a single face of a connected planar graph, with one infinite face which
is also to be coloured. Vertices of degree 2 may be ignored, as they do not affect the
2.2.3 Maps
Definition 2.7 A map is a connected plane graph with no bridges.
Proposition 2.14 A map has a k-colouring of its faces if and only if its geometric
dual has a k-colouring of its vertices.
Proof
Suppose a map G has a k-colouring of its faces. The geometric dual G∗ is a loopless
plane graph. Each face of G contains one vertex of G∗. Faces are adjacent in G if
and only if the corresponding vertices are adjacent in G∗, so assigning the colours of
the faces of G to the vertices of G∗ gives a k-colouring of these vertices. Similarly, a
k-colouring of the vertices of G∗ yields a k-colouring of the faces of G.
It follows from Propositions 2.13 and 2.14 that every map is 4-colourable.
Proposition 2.15 A map is 2-face-colourable if and only if it is Eulerian.
49
Proof
By Proposition 2.14, a map has a 2-colouring of its faces if and only if its dual has a
2-colouring of its vertices, i.e. the dual is bipartite, which by Proposition 2.9 holds if
and only if the map is Eulerian.
Proposition 2.16 A cubic map is 3-face-colourable if and only if each face has even
degree.
Proof
Suppose a map is cubic, which means that each vertex has degree 3. Then its geo-
metric dual is a connected plane graph in which each face (including the infinite one)
has degree 3. Such a graph is called a plane triangulation, and is maximal planar by
Proposition 2.10. We shall prove that a plane triangulation is 3-colourable if and only
if every vertex has even degree. This is equivalent to the proposition, by duality.
Suppose G is a plane triangulation and has a vertex v of odd degree. Then v and the
adjacent vertices form a wheel Wr, where r is even. This is not 3-colourable, hence
nor is G.
Now suppose every vertex of a plane triangulation G has even degree. If G is a
triangle, it is clearly 3-colourable. Make the inductive hypothesis that the result
holds for all plane triangulations with fewer vertices than G, in which every vertex
has even degree.
By Proposition 2.5, G has a vertex v of degree ≤ 5. As each vertex has even degree,
d(v) = 2 or 4.
If d(v) = 2 then G−v has a pair of parallel edges. Deleting one of these edges leaves a
graph satisfying the inductive hypothesis, which can be 3-coloured. Give v a different
colour from each of its neighbours in this colouring, to get a 3-colouring of G.
If d(v) = 4, there are four vertices w, x, y, z adjacent to v. As G is planar it does not
contain K5 so there is a non-adjacent pair among these vertices, say w and y. If v
is at the the centre of a wheel W5, contract the edges vw and vy to get a graph G

satisfying the inductive hypothesis, which can be 3-coloured. In G′ there is a wheel
subgraph centred on v in which x and z are an even distance apart so they have the
same colour, which is different from that of v. Apply this colouring to G, then give
the colour of v to both w and y and the third colour to v. We now have a 3-colouring
of G. A similar argument applies if v is on the boundary of the infinite face. The
result follows by induction.
50
Proposition 2.17 If every cubic map is 4-face-colourable then every map is 4-face-
colourable.
Proof
Let G be a map. Assume it has no vertices of degree 2, as these do not affect colour-
ings of the faces. For each vertex v of degree ≥ 4, replace v by a cycle of length d(v)
with a vertex incident to each edge that is incident to v. Repeating this as often as
necessary, every vertex will eventually have degree 3 so we get a cubic map. Assuming
this to have a 4-colouring of its faces, we still have such a colouring when the cycles
are replaced by the original vertices.
Thus to prove the Four Colour theorem it is only (!) necessary to prove that all cubic
maps are 4-colourable. Later we shall see another equivalent condition, in terms of
edge colourings.
We now consider an application of vertex colourings.
2.2.4 Chromatic polynomials
Definition 2.8 Let G be a graph and let k ∈ N. The chromatic polynomial PG(k)
is the number of distinct k-colourings of the vertices of G.
We must justify calling PG(k) a polynomial:
Proposition 2.18 Let G be a simple graph with n vertices and m edges.
(i) For each edge e of G, PG(k) = PG−e(k)− PG\e(k).
(ii) PG(k) = k
n −mkn−1 +
n−2∑
r=1
ark
r for some a1, . . . , an−2 ∈ Z.
Proof
(i) Let e be an edge joining vertices v and w. In G and G − e, the numbers of
k-colourings in which v and w have different colours are equal.
In G − e and G \ e, the numbers of k-colourings in which v and w have the same
colour are equal (since they are the same vertex in G \ e).
The k-colourings of G − e which are not k-colourings of G are those in which v and
w have the same colour, each of which corresponds to a k-colouring of G \ e.
Hence PG−e(k) = PG(k) + PG\e(k), giving the required result.
(ii) Let G be a simple graph with n vertices. When G has no edges, i.e. G = Nn,
then PG(k) = k
n so the result holds.
51
Assume it holds for all simple graphs with fewer than m edges. Now let G have m
edges, so the hypothesis can be applied to G−e and G\e (with parallel edges replaced
by single edges), which both have < m edges and n, n− 1 vertices respectively.
Thus we can write PG−e(k) = kn − (m− 1)kn−1 + bk−2kn−2 + · · ·+ b1k
and PG/e(k) = k
n−1 + ck−2kn−2 + ck−3kn−3 + · · ·+ c1k.
By (i), PG(k) = PG−e(k)−PG\e(k) = kn−mkn−1+(bk−2−ck−2)kn−2+ · · ·+(b1−c1)k,
which is a polynomial of the same form. The result follows by induction on m.
Note that PG(k) has constant term 0, so PG(0) = 0 for every graph G. It can further
be shown that the terms in PG(k) alternate in sign.
χ(G) is the smallest k ∈ N for which PG(k) 6= 0.
To find the chromatic polynomial of a graph, we can follow the procedure described
in the proof of (i). In this situation, when an edge is contracted any resulting parallel
edges are replaced by a single edge.
There are some standard results:
1. When G = Nn, PG(k) = k
n.
2. When G = Kn, PG(k) = k(k − 1)(k − 2) · · · (k − n+ 1) = k!
(k − n)! .
3. When G is a tree with n vertices, PG(k) = k(k − 1)n−1.
4. When G = Cn (for n ≥ 3), PG(k) = (k − 1)n + (−1)n(k − 1).
Also, if G is disconnected then PG(k) is the product of the chromatic polynomials of
all the components.
The chromatic number and polynomial can be applied to scheduling problems. Sup-
pose we have a set of events, some of which cannot take place simultaneously. Rep-
resent the events by the vertices of a graph G, with edges joining those pairs which
must be kept apart. Use different colours for the different time slots. Then χ(G) is
the minimum number of separate sessions needed. PG(k) is the number of distinct
ways of scheduling the events using up to k sessions.
Example
Lectures are to be timetabled in Algebra, Calculus, Dynamics, Modelling and Statis-
tics. Calculus and Dynamics must be at different times, and neither can take place at
the same time as Algebra or Modelling. Also, Modelling and Statistics cannot take
place simultaneously.
52
The graph is clearly 3-chromatic, so at least three lecture periods are needed.
To find the chromatic polynomial, choose an edge e to remove and contract. Apply
PG(k) = PG−e(k)− PG\e(k) to this edge.
Taking e = CD we have PG−e(k) = PG1(k) as shown below and PG\e(k) = PP4(k).
Then taking e = MS in G1 we have PG1(k) = PG1−e(k)−PG1\e(k) where PG1−e(k) =
C4 ∪N1 and PG1\e(k) = C4.
Thus PG(k) = kPC4(k)− PC4(k)− PP4(k) = (k − 1)[(k − 1)4 + k − 1]− k(k − 1)3
= (k − 1)2((k − 1)3 + 1− k(k − 1)) = (k − 1)2(k3 − 4k2 + 4k) = k(k − 1)2(k − 2)2.
The number of ways of timetabling the lectures in three periods is PG(3) = 12. If
four periods are available, it can be done in PG(4) = 144 ways.
There are many other results on vertex colourings, such as:
Brooks’s theorem: If G is a simple, connected but not complete graph in which
∆(G) ≥ 3, then G is ∆(G)-colourable.
Gro¨tzsch’s theorem: If a planar graph G contains no triangles then χ(G) ≤ 3.
We next look at edge colourings.
53
2.2.5 Chromatic index and Vizing’s theorem
Definition 2.9 Given a graph G, the chromatic index χ′(G) is the smallest k ∈ N
for which G is k-edge-colourable.
Clearly χ′(G) ≤ |E(G)|. A much better upper bound is given by the following, which
shows that there are only two possible values for χ′(G) in any given simple graph.
Proposition 2.19 (Vizing’s theorem) Let G be a simple graph. Then χ′(G) is
either ∆(G) or ∆(G) + 1.
Proof
Clearly χ′(G) ≥ ∆(G), so we must show that χ′(G) ≤ ∆(G) + 1. This is clearly true
for a graph with one edge, where χ′(G) = ∆(G) = 1.
Suppose the result is true for all graphs with fewer edges than G. Let uv be any
edge of G. ∆(G − uv) ≤ ∆(G), so by the hypothesis there is an edge colouring of
G− uv using colours {1, 2, . . . ,∆(G) + 1}, in which no vertex is incident to edges of
all ∆(G) + 1 colours. Say a colour is missing at a vertex if it is not assigned to any
edge incident to that vertex.
Construct a sequence of edges uv0, uv1, . . . and a sequence of colours c0, c1, . . . as
follows: let v0 = v. For i = 0, 1, . . ., let ci be a colour that is missing at vi, and let
uvi+1 be an edge (if there is one) that is already assigned colour ci.
Stop with k = i when either ck is missing at u, or ck is already used on some edge
uvj where j < k.
If ck was missing at u, recolour uvi with ci for 0 ≤ i ≤ k to get a (∆(G) + 1)-edge-
colouring of G.
Otherwise, recolour uvi with ci for 0 ≤ i < j and uncolour uvj. Now ck is missing at
both vj and vk. Let c` be a colour that is missing at u.
If ck is missing at u, colour uvj with ck. If c` is missing at vj, colour uvj with c`.
If c` is missing at vk, colour uvi with ci for j ≤ i < k and colour uvk with c`. (None
of the uvi for j ≤ i < k has colour ck or c`.)
If none of the above hold, consider the subgraph consisting of all edges coloured ck or
c`. The components of this subgraph are paths or cycles. u, vi, vk are the end vertices
of paths so they do not all lie in the same component. Take a component that contains
exactly one of u, vi, vk and swap ck and c` on each edge in this component. One of
the conditions above will now hold, giving a (∆(G) + 1)-edge-colouring of G. The
result follows by induction.
54
Proposition 2.20 For all n > 1, χ′(Kn) = n if n is odd and n− 1 if n is even.
Proof
Each vertex of Kn has degree n− 1, so by Vizing’s theorem χ′(Kn) is n− 1 or n.
If n is odd, any
n+ 1
2
edges are incident to n + 1 vertices so at least two of these
edges are adjacent. Thus at most
n− 1
2
edges can have the same colour. Now Kn
has
n(n− 1)
2
edges, so at least n colours must be used. Thus χ′(Kn) = n.
If n is even, we colour the edges of Kn using n− 1 colours as follows. If n = 2 there
is one edge, which can be coloured with one colour. For n > 2, let v be any vertex.
Then Kn − v is a complete graph Kn−1. As n− 1 is odd, this has an edge-colouring
using n− 1 colours. There is such a colouring in which one colour is missing at each
vertex and these missing colours are all different, so we can assign them to the edges
joining v to the vertices in Kn−1 to give an (n− 1)-edge-colouring of Kn.
2.2.6 Ko¨nig’s theorem
Proposition 2.21 (Ko¨nig’s theorem) If G is bipartite (and not necessarily sim-
ple) then χ′(G) = ∆(G).
Proof
The result is clear when G has one edge, as then χ′(G) = ∆(G) = 1. Make the
inductive hypothesis that the result is true for all bipartite graphs with fewer edges
than G.
Delete an edge uv of G to give a bipartite graph G′. Clearly ∆(G′) ≤ ∆(G) so, by
hypothesis, there is an edge colouring of G′ using ∆(G) colours.
In G′, d(u) < ∆(G) so there is at least one of the ∆(G) colours missing at u, and
similarly at v. If the same colour is missing at both u and v, assign this colour to uv
to get a ∆(G)-edge colouring of G.
Otherwise, suppose colours i and j are missing at u and v respectively. Let Hij be
the subgraph of G consisting of v and all edges and vertices that can be reached from
v by a path consisting only of edges with colours i and j. These edges must alternate
between two sets, so u is not in Hij. Interchanging colours i and j on the edges of
Hij will not affect the rest of the colouring. Assigning colour i to uv now gives a
∆(G)-edge colouring of G. The result follows by induction.
55
Proposition 2.22 Every map is 4-face-colourable if and only if χ′(G) = 3 for every
cubic map G.
Proof
By Proposition 2.17, every map is 4-face-colourable if and only if every cubic map is
4-face-colourable. Suppose G is a cubic map whose faces can be coloured with four
colours α = (0, 0), β = (0, 1), γ = (1, 0), δ = (1, 1). Colour each edge e of G with
the sum (mod 2) of the colours of the faces either side of e, e.g. if e lies between
faces coloured β and δ then e will be coloured with (0, 1) + (1, 1) = (1, 0) = γ. Now
each edge is coloured with one of β, γ or δ, since no two distinct colours have sum
α. The three faces that meet at each vertex have different colours. The sums of
these pairs are different, so adjacent edges have different colours. Thus we have a
3-edge-colouring of G. Clearly two colours are not enough, so χ′(G) = 3.
Conversely, suppose G is a cubic map and we have a 3-edge-colouring using colours
α, β, γ. Edges of all three colours meet at each vertex. Consider the subgraph of G
consisting of those edges coloured α or β. This is 2-regular, hence each component
is Eulerian, so its faces can be coloured using two colours: call them 0 and 1. The
same can be done with the subgraph of G consisting of those edges coloured α or
γ. These colourings give, for each face, an ordered pair (x, y), where x, y ∈ {0, 1}.
For two adjacent faces, either the x values or the y values (or both) are different, so
(0, 0), (0, 1), (1, 0), (1, 1) give a 4-colouring of the faces of G.
56
2.2.7 Exercises
1. Consider the graph G in the first diagram in Example 2.2.4 (top of Page 53).
Apply the greedy algorithm to allocate colours 1, 2, 3, . . . to the vertices in the
orders
(i) A,C,D,M, S, (ii) A,C,D, S,M .
State the value of χ(G).
2. v is a vertex of a graph G, such that d(v) < k. Show that if G−v is k-colourable
then G is k-colourable.
3. G is an r-regular simple graph with n vertices. Prove that χ(G) ≥ n
n− r .
4. Let α(G) denote the number of vertices in the largest independent set of vertices
in a graph G with n vertices. Show that α(G)χ(G) ≥ n.
5. Find the minimum number of colours needed for a proper colouring of the faces
of each of the Platonic graphs.
6. Show that if G is a k-colourable simple graph with n vertices then G has a
vertex of degree less than or equal to

n
(
1− 1
k
)⌋
.
7. Show that if G is not a connected graph then the coefficient of k in PG(k) is
zero.
8. Using the standard result for the chromatic polynomial of Cn, find the chromatic
polynomial of the wheel graph Wn.
9. Find the chromatic polynomials of the six connected simple graphs with four
vertices. Hence find the number of ways of 4-colouring each of these graphs.
10. An examination schedule is to be drawn up for a set of five modules, A to E.
The table below shows the exams which may not be scheduled at the same time
(marked with a ∗). Find the minimum number of periods needed to schedule all
five exams, and the number of ways of scheduling them using this many periods.
A B C D E
A ∗ ∗ ∗ ∗
B ∗ ∗
C ∗ ∗ ∗
D ∗ ∗ ∗
E ∗ ∗
57
11. Use any of the results proved or stated in the notes to find the chromatic index
of
(i) Kr,s (where r ≤ s),
(ii) the graphs of the tetrahedron and cube (as on Page 2).
12. Show that every 3-regular Hamiltonian simple graph is 3-edge-colourable.
58
2.3 Matchings and flows
2.3.1 Menger’s theorem
Definition 2.10 Let A and B be subsets of the vertex set of a graph G. An A,B
path in G is either a path between a vertex in A and a vertex in B, or a single vertex
of A ∩B.
A set of paths in G is disjoint if no two of them have any vertices (and hence edges)
in common.
A set S of vertices is called an A,B separator if every A,B path includes a vertex
in S.
Proposition 2.23 (Menger’s theorem)
Let A and B be sets of vertices in a graph G. Then the maximum number of disjoint
A,B paths in G is equal to the minimum order of an A,B separator.
Proof
The result is clear if G has no edges, as both numbers are then equal to |A ∩ B|
(which equals 0 if A and B have no vertices in common). Now assume G has at least
one edge and make the inductive hypothesis that the result holds for all graphs with
fewer edges than G.
Let s be the minimum order of an A,B separator in G. Clearly there cannot be more
than s disjoint A,B paths. We must show that s such paths exist.
Let e = uv be any edge of G. Contract the edge e to get the graph G \ e in which u
and v become a single vertex w, which is regarded as being in A if u or v is in A and
in B if u or v is in B.
Let S be an A,B separator of minimal order in G \ e, so |S| ∈ {s, s− 1}. If |S| = s,
which is certainly the case if w /∈ S, then by the hypothesis there are s disjoint A,B
paths in G \ e and hence in G.
If |S| = s − 1 then w ∈ S. Any A,B path passing through u or v in G would pass
through w in G \ e. Thus the vertices in S other than w, together with u and v, form
an A,B separator X of order s in G.
Each A,X separator or X,B separator in G − e is an A,B separator in G, so has
order at least s. Thus by the inductive hypothesis G − e contains s disjoint A,X
paths which join vertices in A to the s vertices in X, and s disjoint X,B paths which
join the s vertices in X to vertices in B.
An A,X path and an X,B path in G can intersect only in X, as otherwise G would
contain an A,B path entirely outside X. Thus combining each of s A,X paths with
each of s X,B paths gives s disjoint A,B paths in G, as required.
59
The result follows by induction on the number of edges of G.
It follows from Menger’s theorem (see Exercises) that given any two non-adjacent
vertices u and v in a graph, the minimum number of vertices in a u, v-separating set
equals the maximum number of paths between u and v which have no vertices in
common except u and v.
Definition 2.11 Let G(U,W ) be a bipartite graph. A (complete) matching from U
to W is a one-to-one correspondence between V (U) and a subset of V (W ), such that
2.3.2 Hall’s theorem
Proposition 2.24 (Hall’s theorem) Let G(U,W ) be a bipartite graph. For each
subset S of U , let θ(S) be the set of all vertices of W that are adjacent to at least one
vertex in S.
Then there is a matching from U to W if and only if |θ(S)| ≥ |S| for every subset S
of U .
Proof
It is clear that if a matching exists then |θ(S)| ≥ |S| for all S ⊂ U .
For the converse, assume |θ(S)| ≥ |S| for each S ⊂ U and let X be a U,W separator
consisting of a subset S of U and a subset T of V . Then no vertex in U \ S is
adjacent to a vertex in V \ T , so θ(U \ S) ⊂ T . Thus |U \ S| ≤ |θ(U \ S)| ≤ |T |, so
|X| = |S|+ |T | ≥ |S|+ |U \ S| = |U |.
Hence by Menger’s theorem, there are at least |U | vertex-disjoint U,W paths in G.
Each of these is a single edge, giving the required matching.
Hall’s theorem is often called the marriage theorem: given sets of men and women,
each of the r women can marry a man she knows if and only if, for k = 1, . . . , r, every
set of k women collectively knows at least k men. This condition is clearly necessary;
the theorem shows that it is also sufficient.
Another interpretation of the theorem uses the following idea.
60
2.3.3 Transversals
Definition 2.12 Let E be a non-empty finite set and let F = (X1, . . . , Xr) be a family
of non-empty subsets of E (not necessarily distinct). A transversal (or system of
distinct representatives) of F is a set of r distinct elements of E consisting of one
element from each of X1, . . . , Xr.
Clearly a transversal exists if and only if there is a matching from F to E, so Hall’s
theorem can be restated as follows: F has a transversal if and only if, for each of
k = 1, . . . , r, the union of any k of X1, . . . , Xr has order ≥ k.
Example
Let E = {a, b, c, d, e, f},F = (X1, . . . , X5) whereX1 = {a, b, c, d}, X2 = {a, c, d, e}, X3 =
{a, f}, X4 = {a, f}, X5 = {a, c, e, f}. Then F has transversals. For example,
(d, c, a, f, e) is a transversal of F .
Example
Let E = {1, 2, 3, 4},F = (X1, X2, X3, X4) where X1 = {1, 2, 3, 4}, X2 = {3, 4},
X3 = {3}, X4 = {4}.
|X2 ∪X3 ∪X4| = 2 < 3 so F has no transversal.
2.3.4 Networks
Definition 2.13 A network is a directed graph in which a positive capacity c(e)
is assigned to each arc e. For any vertex v, the in-degree din(v) and out-degree
dout(v) are the total capacities of all arcs leading into v and out of v, respectively.
Example
In this network, din(s) = 0, dout(s) = 10, din(u) =
dout(u) = 6, din(v) = dout(v) = 5, din(t) =
10, dout(t) = 0.
Notice that the sum of the in-degrees, 21, equals
the sum of the out-degrees.
61
Definition 2.14 In a connected network, a source (or initial vertex) s has din(s) =
0, dout(s) > 0. A sink (or terminal vertex) t has din(t) > 0, dout(t) = 0.
A flow in a network is a function f from the set of arcs to the non-negative real
numbers such that f(e) ≤ c(e) for each arc e. At each vertex v, the in-flow fin(v) is
the sum of the flows in all arcs leading into v and the out-flow fout(v) is the sum
of the flows in all arcs leading out of v. The in-flow and out-flow must be equal at
each v /∈ {s, t}. The value of the flow is fout(s), or equivalently fin(t). An arc is
saturated if the flow in it is equal to its capacity.
A cut is a set of arcs whose removal leaves no path from s to t, such that no proper
subset has this property. The capacity of a cut is the sum of the capacities in all
those arcs which cross the cut from the side containing s to the side containing t.
There are several alternative forms of Menger’s theorem. One of these states that the
maximum number of arc-disjoint paths from a vertex u to a vertex v in a digraph
is equal to the minimum number of arcs in a u, v-disconnecting set, i.e. a set of arcs
whose removal leaves no path from u to v. We use this to prove:
Proposition 2.25 In a network with a source and sink, the maximum value of a
flow is equal to the minimum capacity of a cut.
Proof
Clearly the maximum flow is less than or equal to the minimum capacity of any cut.
Assume the capacities are integers. The network can be represented by a digraph D in
which the number of arcs from vi to vj equals the capacity of vivj. The maximum flow
is then equal to the number of arc-disjoint paths in D from the source s to the sink t.
By the version of Menger’s theorem stated above this equals the smallest number of
arcs in an s, t-disconnecting set in D, which in turn represents the minimum capacity
of any cut.
If the capacities are rational, they can be multiplied by a suitable integer to make
them all integers. This will not affect their comparative sizes, so the result for inte-
gers can be applied. Irrational flows (which seldom occur) may be approximated by
rationals to any required degree of accuracy.
There are algorithms for finding the maximum flow in a network. If we can find, by
inspection or otherwise, a flow and a cut that have the same value then they must
be respectively maximal and minimal. The flow consists of a value for each arc, less
than or equal to the capacity of the arc, such that the flows into and out of each
vertex are equal.
62
Example
The left-hand diagram shows a network with the capacities shown on the arcs. The
vertical line shows a cut of value 20.
The right-hand diagram shows a flow of 20. The circled values are on saturated edges.
This must be the maximum flow from s to t, as we have found a cut of equal value.
63
2.3.5 Exercises
1. u and w are vertices of a connected graph G. k is the order of the smallest set
S ⊂ V (G)\{u,w} such that there is no path from u to w in G−S. Use Menger’s
theorem to show that there are at most k paths from u to w in G which are
internally disjoint, i.e. they have no vertices except u and w in common.
2. u is a vertex of a connected, k-connected graph G. U is the set of all neighbours
of u and W is a set of at least k vertices of G, other than u.
Use Menger’s theorem to show that there are k paths from u to W which have
no vertices except u in common.
3. Let k ≥ 2. Use the previous question to show that every k-connected graph
with at least 2k vertices contains a cycle of length at least 2k.
4. Wilson (link on SurreyLearn) Exercises 25.1, 25.3, 26.1 (omit partial transver-
sals), 26.4, 29.1.
64
Chapter 3
Graphs and matrices
Definition 3.1 Let v1, . . . , vn be the vertices of a graph G.
The adjacency matrix of G, relative to the given labelling, is the n × n matrix A
with (i, j) entry equal to the number of edges joining vi to vj.
Clearly A is symmetric. For a simple graph, aij = 1 if vi and vj are adjacent, and 0
otherwise. If G has loops at vi then each loop contributes 1 to the (i, i) entry.
Labelling the vertices of G differently will permute the rows, and the columns cor-
respondingly, so that the resulting matrix A′ is similar to A, i.e. there is a matrix P
such that A′ = P−1AP. P is a permutation matrix, obtained from the n× n identity
matrix In by applying the same permutation to its columns. Any such matrix P is
an orthogonal matrix, i.e. P−1 = Pt.
The adjacency matrix can also be defined when G is a digraph. In that case the (i, j)
entry is the number of arcs from vi to vj and the matrix is not necessarily symmetric.
Example

1 1 1 0
1 0 1 1
1 1 0 2
0 1 2 0
 represents the following graph relative
to the vertex labelling (v1, v2, v3, v4).
65
v3 v4
v2v1
e1
e2
e3 e4 e5
e6
e7
If u1 = v2, u2 = v3, u3 = v4, u4 = v1 then relative to (u1, u2, u3, u4) the graph has

0 1 1 1
1 0 2 1
1 2 0 0
1 1 0 1
.
We have A′ = P−1AP where P =

0 0 0 1
1 0 0 0
0 1 0 0
0 0 1 0
, the identity matrix I4 with its
columns permuted in the order 2, 3, 4, 1.
Proposition 3.1 Let A be the adjacency matrix of a graph G with n vertices. For
any r ∈ N, the (i, j) entry of Ar is the number of walks in G of length r from vi to
vj.
Proof
The result is clear when r = 1, by the definition of A.
Assume the statement is true for r = k. Let cij be the (i, j) entry of A
k.
Ak+1 = AkA, so the (i, j) entry of Ak+1 is
n∑`
=1
ci`a`j.
By assumption ci` is the number of walks of length k from vi to v` and a`j is the
number of edges joining v` to vj, so the sum is the number of walks of length k + 1
from vi to vj. Thus the result holds when r = k + 1, so by induction it is true for all
r ∈ N.
Example
For the graph in Example 3.1, A2 =

3 2 2 3
2 3 3 2
2 3 6 1
3 2 1 5
.
Thus there are 3 walks of length 2 from v1 to v1. These are v1v2v1, v1v3v1, and round
the loop twice. As the graph is undirected, traversing the loop in different directions
does not give distinct walks.
66
There are two walks of length 2 from v1 to v2, namely v1v3v2 and v1v1v2, the latter
being the loop (in either direction) followed by the edge v1v2.
It is clear that a graph is disconnected, with c components, if and only if its vertices
can be ordered such that its adjacency matrix has the form
 A1 . . .
Ac
, all
entries outside the diagonal blocks being zero. This matrix is called the direct sum
or diagonal sum A1 ⊕ · · ·⊕ Ac.
From Year 1 Linear Algebra, every real symmetric matrix A is diagonalisable; indeed,
there is an orthogonal matrix P such that PtAP is a diagonal matrix. This implies
that the algebraic and geometric multiplicities of any eigenvalue are equal, i.e. the
number of times the eigenvalue occurs as a root of the characteristic equation equals
the dimension of the associated eigenspace. Thus we can just refer to the multiplicity
of an eigenvalue.
The set of all eigenvalues of a matrix is called its spectrum. We say the spectrum
is symmetric if whenever λ is an eigenvalue, −λ is also an eigenvalue with the same
multiplicity.
Proposition 3.2 A graph is bipartite if and only if the spectrum of its adjacency
matrix is symmetric.
Proof
A bipartite graph G(U,W ) can be labelled such that its adjacency matrix A has the
form
(
O B
Bt O
)
, where B is a p× q matrix, p = |U | and q = |W |.
Let x be an eigenvector of A, associated with the eigenvalue λ, so Ax = λx. We
can write x as
(
y
z
)
where y ∈ Rp, z ∈ Rq. Thus Bz = λy and Bty = λz, so
A
( −y
z
)
=
(
Bz
−Bty
)
=
(
λy
−λz
)
= −λ
( −y
z
)
.
Hence for every eigenvalue λ there is an eigenvalue −λ. The sum of the eigenvalues
is the trace of A, which equals 0 as a bipartite graph has no loops, so λ and −λ have
the same multiplicity. Thus the spectrum of A is symmetric.
Conversely, suppose the spectrum of A is symmetric. The eigenvalues of Ar are the
rth powers of those of A, so for any odd r ∈ N the trace of Ar is 0. As the entries are
non-negative, it follows that each diagonal entry of Ar is 0.
67
Thus by Proposition 3.1 there are no walks of odd length from any vertex to itself,
i.e. no closed walks of odd length in G. In particular there are no odd cycles, so G is
bipartite.
Let A be a symmetric n× n real matrix, x a column vector in Rn, and q(x) = xtAx.
Recall from Linear Algebra that q(x) is called a real quadratic form.
A has eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn, associated with mutually orthogonal eigenvec-
tors v1, . . . ,vn which we can assume have been normalised, i.e. they are unit vectors.
Letting P be the matrix with these vectors as its columns, we have P−1AP = D, the
diagonal matrix with λ1, . . . , λn on its main diagonal. P is orthogonal, so P
−1 = Pt.
{v1, . . . ,vn} is a basis for Rn, so any vector x ∈ Rn can be written as c1v1+· · ·+cnvn.
Let c = (c1 · · · cn)t, so x = Pc.
Then xtAx = (Pc)tAPc = ctPtAPc = ctDc = λ1c
2
1 + · · ·+ λnc2n.
Suppose x is a unit vector. As P is orthogonal, |Pc| = |c|, so |c| = |x| = 1, hence
c21 + · · ·+ c2n = 1.
Thus xtAx ≤ λ1c21 + · · ·+ λ1c2n = λ1 and xtAx ≥ λnc21 + · · ·+ λnc2n = λn.
Now xtAx = λ1 when x = v1 and x
tAx = λn when x = vn, giving the following
result which you may have met in Operations Research and Optimisation:
Proposition 3.3 Let A be a symmetric real matrix and let q(x) = xtAx.
The maximum value of q(x) subject to |x| = 1 is equal to the largest eigenvalue of A,
and occurs when x is a corresponding unit eigenvector.
The minimum value of q(x) subject to |x| = 1 is equal to the smallest eigenvalue of
A, and occurs when x is a corresponding unit eigenvector.
We now apply this to some results in Graph Theory.
68
Proposition 3.4 Let H be a subgraph of a simple graph G with vertices v1, . . . , vn.
Let λ1, µ1 be the largest eigenvalues of the adjacency matrices AG, AH of G and H
respectively. Then µ1 ≤ λ1.
Proof
If V (H) does not include all the vertices of G, replace H by its union with these
isolated vertices; this simply adds some zero rows and columns to AH and does not
affect its eigenvalues. Now AG and AH have the same dimensions. All their entries
are either 0 or 1.
Letting x = (x1 · · · xn)t be a unit eigenvector of AH associated with µ1, we have
µ1 = x
tAHx = 2
( ∑
vivj∈E(H)
xixj
)
≤ 2
( ∑
vivj∈E(G)
xixj
)
= xtAGx
By Proposition 3.3, xtAGx ≤ λ1, so µ1 ≤ λ1.
Proposition 3.5 Let λ1 be the largest eigenvalue of the adjacency matrix of a simple
graph G. Then δ(G) ≤ λ1 ≤ ∆(G) and χ(G) ≤ 1 + λ1.
Proof
Let u = (u1 · · · un)t be a unit eigenvector of A associated with λ1, so Au = λ1u and
|u| = 1. As u 6= 0, we can assume u has at least one positive entry.
Let uk be the largest positive entry of u. Then λ1uk = kth entry of Au
=
n∑
j=1
akjuj ≤
n∑
j=1
akjuk = d(vk)uk ≤ ∆(G)uk, so λ1 ≤ ∆(G).
Let 1 be the vector in Rn whose entries are all 1, so
1√
n
1 is a unit vector.
Then λ1 = max|x|=1
xtAx ≥ 1√
n
1tA
1√
n
1 =
1
n
1tA1
=
1
n
n∑
i=1
n∑
j=1
aij =
1
n

v∈V (G)
d(v) ≥ δ(G), so λ1 ≥ δ(G).
Now define subgraphs Gi as follows: G1 = G and for i = 1, . . . , n− 1, Gi+1 = Gi− vi
where vi is a vertex of smallest degree in Gi. Then Gn is a single vertex vn. χ(Gn) = 1
and λ1 ≥ 0, so Gn is (1 + λ1)-colourable.
Assume that Gi+1 is (1 + λ1)-colourable. The degree of vi in Gi is less than or equal
to the largest eigenvalue of A(Gi), which is less than or equal to λ1 by Proposition
3.4. Hence vi has at most λ1 neighbours in Gi. These are all in Gi+1, so there is at
least one of the 1 + λ1 colours available to colour vi differently from its neighbours.
Thus there is a vertex-colouring of Gi with these colours. The result for G follows by
induction.
69
3.2 Incidence matrix
Definition 3.2 Let G be a graph with vertices v1, . . . , vn and edges e1, . . . , em.
The (vertex-edge) incidence matrix of G is the n × m matrix B with (i, j) entry
equal to 1 if vi is incident to ej and 0 otherwise.
Clearly this matrix depends on the ordering of both the vertices and the edges.
Example
For the graph in Example 3.1, relative to (v1, . . . , v4) and (e1, . . . , e6), the incidence
matrix of G is B =

1 1 1 0 0 0 0
0 1 0 1 1 0 0
0 0 1 1 0 1 1
0 0 0 0 1 1 1
.
We see that a column corresponding to a loop contains a single 1, while any other
column has 1 in exactly two positions, in the rows corresponding to its two ends.
Different orderings of the vertices and edges will permute the rows and columns.
A vector x of length m can represent a set Ex of edges by letting the jth entry be
1 if ej is in the set and 0 otherwise. For example, if there are seven edges then
(1, 1, 0, 1, 0, 1, 0) represents {e1, e2, e4, e6}. Row i of the incidence matrix is a vector
which represents the set of edges that are incident to vi.
Writing x as a column vector, Bx is the column vector whose ith entry is the number
of edges in Ex that are incident to vertex vi.
With B as in the example above, taking x = (1 1 0 1 0 1 0)t, we find Bx =
(2 2 2 1)t. This shows that, from the set {e1, e2, e4, e6}, two edges are incident to
each of v1, v2, v3 and one edge is incident to v4.
BBt is the n×n matrix whose (i, j) entry is the number of edges that are incident to
both vi and vj.
Every entry of the incidence matrix B is 0 or 1, so we can regard B as a matrix over
the field F2 of integers modulo 2; that is, F2 = {0, 1} where 1+1 = 0. A vector which
represents a set of edges has entries 0 or 1, so can be regarded as a vector over F2.
Recall that the null space of B, Null(B), is the set of all vectors x such that Bx = 0.
The row space of B, Row(B) is the set of all linear combinations of the rows of B.
Null(B) and Row(B) are subspaces of F2m.
Proposition 3.6 Let B be the incidence matrix of a graph G with no loops. Regard
B as a matrix over F2.
70
A vector x ∈ F2m is in Null(B) if and only if it represents a union of one or more
edge-disjoint cycles in G.
A vector x ∈ F2m is in Row(B) if and only if it represents a union of one or more
disjoint cutsets in G.
Proof
The ith entry of Bx is the number (mod 2) of edges incident to vi in the set Ex
represented by x. This is 0 for each i if and only if every vertex of G is incident to an
even number (possibly 0) of edges in Ex. By Proposition 1.9, this holds if and only
if Ex can be partitioned into edge-disjoint cycles.
Let S = {vi1 , . . . , vir} be a set of r vertices of G. The sum (modulo 2) of rows i1, . . . , ir
of B is a vector with jth entry 1 if ej is incident to an odd number of the vertices in
S, and 0 otherwise. This vector represents the set of all edges that are incident to
exactly one vertex in S, so deleting these edges will disconnect the subgraph induced
by S from the rest of the graph. This is the case if and only if they represent a union
of one or more disjoint cutsets.
Definition 3.3 With G and B as above, Null(B) is the cycle space of G. Its di-
mension is the cycle rank or nullity, γ(G).
Row(B) is the cutset space of G. Its dimension is the cutset rank, ξ(G).
The cycle rank and cutset rank of G are respectively the nullity and rank of the
incidence matrix B. Recall that the nullity and rank of a matrix add up to the number
of columns.
Assuming G has no loops, the sum of the rows of B is 0. If G is connected and one
row is deleted, the remaining rows form a linearly independent set so ξ(G) = n − 1
and γ(G) = m− n+ 1.
If G has c components with n1, . . . , nc vertices then ni − 1 out of each set of ni rows
are linearly independent, so ξ(G) = n− c and γ(G) = m−n+ c. Thus the definitions
here are consistent with those in Definition 1.19.
Consider the graph in Example 3.1, excluding the loop e1. The incidence matrix is
now B =

1 1 0 0 0 0
1 0 1 1 0 0
0 1 1 0 1 1
0 0 0 1 1 1
. We have ξ(G) = 4−1 = 3 and γ(G) = 6−4+1 = 3.
Row(B) is spanned over F2 by any three rows of B, which form a basis for the cutset
space.
71
Null(B) is spanned over F2 by {(0, 1, 1, 1, 0, 0, 0), (0, 1, 1, 0, 1, 1, 0), (0, 1, 1, 0, 1, 0, 1)}.
These represent the cycles e2e3e4, e2e5e6e3, e2e5e7e3. These form a basis for the cycle
space, sometimes referred to as a fundamental set of cycles.
3.3 Degree and Laplacian matrices
Definition 3.4 Let G be a loopless graph with vertices v1, . . . , vn and adjacency ma-
trix A.
The degree matrix of G is the n × n diagonal matrix D with (i, i) entry d(vi) and
all other entries 0.
The Laplacian matrix of G is the n× n matrix L = D− A.
L is a real symmetric matrix, so its eigenvalues are real. It is clear from the definition
that the sum of the entries in each row or column of L is 0, so if 1 is the vector whose
entries are all 1 then L1 = 0. Hence 0 is an eigenvalue of L, which is singular.
Let C be the n×m signed incidence matrix of G, which is formed by changing a single
1 to −1 in each column. It does not matter which; we normally change the ‘lower’
entry to −1. The (i, j) entry of CCt is (row i of C) . (row j of C). This equals d(vi)
if i = j and −aij otherwise. Thus CCt = D − A = L.
Example
For the graphG shown here, relative to the ordering (v1, . . . , v5),
A =

0 1 0 1 0
1 0 1 1 0
0 1 0 0 1
1 1 0 0 1
0 0 1 1 0
, D =

2 0 0 0 0
0 3 0 0 0
0 0 2 0 0
0 0 0 3 0
0 0 0 0 2
 so L =

2 −1 0 −1 0
−1 3 −1 −1 0
0 −1 2 0 −1
−1 −1 0 3 −1
0 0 −1 −1 2
.
Let C =

1 0 1 0 0 0
−1 1 0 1 0 0
0 −1 0 0 1 0
0 0 −1 −1 0 1
0 0 0 0 −1 −1
. Then CCt =

2 −1 0 −1 0
−1 3 −1 −1 0
0 −1 2 0 −1
−1 −1 0 3 −1
0 0 −1 −1 2

= L.
72
Note that if x = (x1 · · · xn)t then Ctx has an entry xi − xj for each edge vivj of G,
so xtLx = xtCCtx = (Ctx)t(Ctx) =

vivj∈E(G)
(xi − xj)2 ≥ 0.
If Lx = λx then 0 ≤ xtLx = λ|x|2, so λ ≥ 0.
Proposition 3.7 Let G be a loopless graph. The number of components of G equals
the multiplicity of 0 as an eigenvalue of the Laplacian matrix of G.
Proof
Let G have c components G1, . . . , Gc. For j = 1, . . . , c, let uj be the column vector
with ith entry 1 if vi ∈ Gj and 0 otherwise. Then Luj = 0, and uj . uk = 0 for j 6= k.
Mutually orthogonal vectors form a linearly independent set, so there are at least c
distinct eigenvectors associated with the eigenvalue 0.
Let x = (x1, . . . , xn) be any eigenvector of L associated with 0. Lx = 0 so 0 = x
tLx =∑
vivj∈E(G)
(xi−xj)2. Thus xi = xj whenever vi and vj are in the same component of G,
so x is a linear combination of the c vectors uj defined above. Hence the dimension
of the eigenspace for 0 (i.e. the multiplicity of the eigenvalue 0) is exactly c.
It follows that if L has (not necessarily distinct) eigenvalues 0 = λ1 ≤ λ2 ≤ · · · then
G is disconnected if and only if λ2 = 0.
Recall that for each entry aij of an n×n matrix A, its minor Mij(A) is the determinant
of the (n− 1)× (n− 1) matrix obtained by deleting row i and column j of A.
3.4 Matrix tree theorem
Proposition 3.8 (The matrix tree theorem)
The number of distinct labelled spanning trees of a connected loopless graph G is equal
to the minor of any entry on the main diagonal of the Laplacian of G.
Proof
The result is true for a graph with one edge, for which the Laplacian is
(
1 −1
−1 1
)
and there is one spanning tree. Make the inductive hypothesis that it is true for any
connected loopless graph with fewer edges than G.
Let e = vivj be any edge of G. The spanning trees of G which do not include e are
the spanning trees of G− e. The spanning trees of G which do include e correspond
73
to spanning trees of G \ e. Thus the number t(G) of labelled spanning trees of G
satisfies t(G) = t(G− e) + t(G \ e).
L(G− e) is obtained from L(G) as follows: the (i, i) and (j, j) entries decrease by 1,
while the (i, j) and (j, i) entries increase by 1.
Expanding Mii(L(G−e)) by row j, all the terms are the same as in Mii(L(G)) except
for the first term, which decreases by the determinant of the matrix obtained by
deleting rows i and j and columns i and j of L(G). This is the minor of the ith
diagonal entry of L(G \ e), since the other rows and columns are not affected by
contracting e. Thus Mii(L(G)) = Mii(L(G− e)) +Mii(L(G \ e)).
G− e and G \ e have fewer edges than G so by the inductive hypothesis, t(G− e) =
Mii(L(G− e)) and t(G \ e) = Mkk(L(G \ e)). The result follows by induction.
To illustrate the proof, consider the following graph G and let e = v1v4.
L(G) =

2 0 −1 −1 0
0 1 −1 0 0
−1 −1 3 0 −1
−1 0 0 2 −1
0 0 −1 −1 2
, L(G − e) =

1 0 −1 0 0
0 1 −1 0 0
−1 −1 3 0 −1
0 0 0 1 −1
0 0 −1 −1 2
,
L(G \ e) =

2 0 −1 −1
0 1 −1 0
−1 −1 3 −1
−1 0 −1 2
.
M11(L(G)) =
∣∣∣∣∣∣∣∣
1 −1 0 0
−1 3 0 −1
0 0 2 −1
0 −1 −1 2
∣∣∣∣∣∣∣∣ and M11(L(G− e)) =
∣∣∣∣∣∣∣∣
1 −1 0 0
−1 3 0 −1
0 0 1 −1
0 −1 −1 2
∣∣∣∣∣∣∣∣. Ex-
panding these by the last row, the only difference is in the minor of the entry which
changes from 2 to 1. This minor equals
∣∣∣∣∣∣
1 −1 0
−1 3 −1
0 −1 2
∣∣∣∣∣∣, which equals M11(L(G\e)).
It can be shown more generally that the number of spanning trees equals the modulus
of the minor of any entry of the Laplacian.
74
Example
The graph in Example 3.1, ignoring the loop e1, has Laplacian matrix L =

2 −1 −1 0
−1 3 −1 −1
1 −1 4 −2
0 −1 −2 3
.
Find any 3× 3 minor of L, e.g. M44 =
∣∣∣∣∣∣
2 −1 −1
−1 3 −1
−1 −1 4
∣∣∣∣∣∣ = 2(11) + 1(−5)− 1(4) = 13,
or M32 =
∣∣∣∣∣∣
2 −1 0
−1 −1 −1
0 −2 3
∣∣∣∣∣∣ = 2(−5) + 1(−3) = −13.
Thus there are 13 labelled spanning trees of this graph.
If a graph is planar and has fewer faces than vertices, it can be easier to use the
following:
Proposition 3.9 A connected plane graph G and its geometric dual G∗ (excluding
any loops) have the same number of distinct labelled spanning trees.
Proof
Let G have n vertices, m edges and f faces. Let T be a spanning tree of G, so T has
n − 1 edges. Let H be the subgraph of G∗ consisting of all edges corresponding to
those not in T , except for any loops (which can never form part of a spanning tree).
A cycle in H is a cycle in G∗ formed from edges in H. This corresponds to a cutset
in G formed from edges not in T . But every cutset of G must include an edge of T .
Hence H contains no cycles.
Now G∗ has f vertices and the number of edges of H is m−(n−1) = f−2+1 = f−1.
Thus H is a spanning tree of G∗.
As G∗∗ = G, the same reasoning can be applied to obtain a spanning tree of G from
one of G∗. There is thus a one-to-one correspondence between the spanning trees of
G and those of G∗, so the numbers of them are the same.
Example
For the graph in Example 3.3, the geometric dual has Laplacian matrix
 3 −1 −2−1 4 −3
−2 −3 5
.
(Remember that the entries in each row and column must add up to 0.)
Any 2 × 2 minor of this matrix has modulus 11, so the dual, and hence also the
original graph, has 11 distinct labelled spanning trees.
75
Definition 3.5 Let e1, . . . , em be the edges of a graph G.
The edge-adjacency matrix of G is the m×m matrix in which the (i, j) entry, for
i 6= j, is equal to the number of vertices (0, 1 or 2) at which ei and ej meet. The (i, i)
entry is 1 if ei is a loop and 0 otherwise.
Example
The edge-adjacency matrix of this graph, relative to the
labelling (e1, . . . , e5), is
1 1 1 0 0
1 0 1 1 1
1 1 0 1 1
0 1 1 0 2
0 1 1 2 0
.
The edge-adjacency matrix of a graph can be used to construct another graph of which
it is the adjacency matrix. For simple graphs, this is easily described as follows:
Definition 3.6 Let G be a simple graph with edges e1, . . . , em. The line graph of
G, denoted by Λ(G), has vertices v1, . . . , vm, such that vi and vj are adjacent in Λ(G)
if and only if ei and ej are adjacent edges in G.
Example
The simple graph G below has edge-adjacency matrix

0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
. This is the
(vertex) adjacency matrix of its line graph Λ(G).
76
3.5 Exercises
1. Write down the adjacency matrices of the graphs in Example 1.1.1 and Exercises
2.1 Question 1 (a), relative to the given labellings of the vertices.
For the graph in Example 1.1.1, square its adjacency matrix and identify all the
walks of length 2 from v1 to v3.
2. A is the adjacency matrix of a graph G.
(a) State what the entries of A + A2 + · · · + Ar represent.
(b) Suppose G is simple. Show that the trace of A is 0 and the trace of A2 is
twice the number of edges of G. What does tr(A3) represent?
3. Let G be an r-regular simple graph with n vertices. Show that 1 (the vector
whose entries are all 1) is an eigenvector of the adjacency matrix of G and find
the associated eigenvalue. Show also that the adjacency and Laplacian matrices
of G have the same eigenvectors.
4. Let B be the incidence matrix of a tree. Regarding B as a matrix over F2,
identify the null space of B.
5. For the graph in Example 3.3, find bases for the cutset space and cycle space.
6. Write down the incidence matrix of the graph G in Example 1.1.1, relative to
the orderings (e1, . . . , e10) and (v1, v2, v3, v4).
For the same graph G, find the Laplacian matrix of G− e1. Also give a matrix
C such that CCt = L(G− e1).
7. Find the Laplacian matrices of the cycle graph C4 (with vertices labelled in
order around the cycle) and the path graph P2. Show that if
(
a
b
)
is an
eigenvector of L(P2) then

a
b
b
a
 is an eigenvector of L(C4).
8. Use the matrix tree theorem to find the number of labelled spanning trees of
(i) K3, (ii) the graph in Example 3.3.
9. A vector y of length n can represent a set Vy of vertices by letting the ith entry
be 1 if vi is in the set and 0 otherwise. For example, if there are four vertices
then (1, 1, 0, 1) represents {v1, v2, v4}.
77
(a) Give interpretations of: (i) column j of the incidence matrix, (ii) y1 . y2,
(iii) the ith entry of Bty, (iv) the (i, j) entry of BtB.
(b) If G is a loopless graph, how is the edge-adjacency matrix of G related to
BtB?
10. Find the edge-adjacency matrix of the graph G in Example 3.3, relative to the
labelling (e1, . . . , e6). Draw the line graph Λ(G). How many edges has it?
78  Email:51zuoyejun

@gmail.com