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

adjacent in G.

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

we already knew.

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

adjacent to both.

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

link. A courier needs to drive along each road at

least once and return to the starting point. Show

that the graph can be made Eulerian by adding

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

made non-planar by adding an extra edge between any two non-adjacent vertices.

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

adjacency of faces.

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

corresponding vertices are adjacent.

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

3.1 Adjacency matrix

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

The adjacency matrix A =

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

adjacency matrix A′ =

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