Special Mathematics Lecture

Graph theory
Nagoya University, Spring 2024

Lecturer: Serge Richard

Teaching assistant: Sota Kitano

Goals of these Lectures notes:

Provide the necessary background information for understanding the main ideas of graph
theory. These notes correspond to 14 lectures lasting 90 minutes each.

Figure 1: A finite graph

Website for this course:

[Link]
Comments or corrections are welcome:
richard@[Link]
Contents

1 The basics 2
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Walks and paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Weighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Representations and structures 11

2.1 Matrix representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Automorphisms and symmetries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Trees 23
3.1 Trees and forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Rooted trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Traversals in binary trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4.1 Arithmetic expression trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4.2 Binary search trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.3 Huffman trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.4 Priority trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Counting trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Spanning trees 41
4.1 Growing trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Depth-first and breadth-first search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Applications of DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Spanning tree with mimimum total edge-weight . . . . . . . . . . . . . . . . . . . . . . . . . 49

5 Connectivity 52
5.1 Vertex and edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2 Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 Blocks and block-cutpoint graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6 Optimal traversals 58
6.1 Eulerian trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

b
 6.2 Postman tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.3 Hamiltonian paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.4 The travelling salesman problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

7 Graph colorings 69
7.1 Vertex-colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Plane graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.3 Map-colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.4 The five color theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

8 Directed graphs 82
8.1 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
8.2 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.3 Project scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9 Flows 94
9.1 Capacity, flows and cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
9.2 Maximum flow problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
9.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
9.3.1 Flow and Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
9.3.2 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.3.3 Transversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.3.4 Hall’s marriage theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

10 Random graphs: the G(n, p) model 105

10.1 Basic results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.3 Clustering coefficient and path lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.4 Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

11 The configuration model 117

11.1 Construction, and basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
11.2 Additional properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
11.3 Community structure, or modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

12 Epidemics on graphs 126

12.1 Basic models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
12.1.1 The SI-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
12.1.2 The SIR-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.1.3 Other models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
12.2 Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
12.3 Epidemic on graphs and percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
12.4 Time dependent evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Bibliography 137

1
Chapter 1

The basics

1.1 Graphs
In this section we provide the main definitions about graphs.

Definition 1.1 (Graph). A graph G consists in a pair G = (V, E) of two sets together with a map i : E → V × V
assigning to every e ∈ E a pair (x, y) of elements of V 1 . Elements of V are called vertices, elements of E are
called edges. If i(e) = (x, y), the vertices x and y are also called the endpoints of e.

We say that the graph is undirected or unoriented if we identify

the pairs (x, y) and (y, x) in V × V, while the graph is directed
or oriented if we consider (x, y) distinct from (y, x) in V × V.
For undirected graphs, when i(e) = (x, y) we say that the edge e
links x to y or y to x, without any distinction, or that e is an edge
between x and y, or between y and x. For directed graphs, if
i(e) = (x, y) we often call x the initial vertex for e, or the origin
Figure 1.1: One edge, two vertices
of e, while y is called the terminal vertex or the target. In this
case, we also set o : E → V and t : E → V with o(e) = x and
t(e) = y such that i(e) = o(e), t(e) , the origin and the terminal maps, see Figure 1.2. Some authors also use


head and tail for the terminal vertex and the initial vertex, respectively. For directed or undirected graphs, we
also say that x and y are connected or adjacent whenever there exists an edge (directed or not) between them.

One observes that Definition 1.1 allows any graph to have loops, when i(e) = (x, x), and multiple edges
between the same vertices, namely when for some fixed x, y ∈ V there exist e1 , . . . , en with i(e j ) = (x, y) for
all j ∈ {1, . . . , n}, see Figures 1.3 and 1.4.

Note that directed graphs are also called digraphs, and that graphs with loops and / or multiple edges are
also called multigraphs. If a graph contains both directed edges (often represented by arrows) and undirected
edges (just represented by a segment), we call it a mixed graph. Clearly, an undirected graph can be obtained
from a directed graph by forgetting the information about the direction (one simply identifies (x, y) with (y, x)
in V × V), while a directed graph can be constructed from an undirected one by assigning a direction to each
edge (for example by fixing the origin of each edge).
1
According to this definition one should write G = (V, E, i) but shall keep the shorter and common notation G = (V, E).

2
 Figure 1.2: Oriented edge Figure 1.3: Loop Figure 1.4: Multiple edges

Remark 1.2 (Simple graph). When a graph has no loop and no multiple edge, we say that the graph is simple.
In such a case, the set E can be identified with a subset of V × V. Indeed, an edge can be simply written
e = (x, y) since there is no ambiguity about the indexation. In an undirected simple graph, the notations (x, y)
and (y, x) would represent the same edge, while for a directed simple graph they would not.

Definition 1.3 (Finite graph, order, and size). A graph G = (V, E) is finite if V and E contain only a finite
number of elements. A graph is infinite if either V or E (or both) contain(s) an infinite number of elements. In
the infinite case, it is assumed that the sets V and E are countable. For finite graph, the order of G, denoted
by |G|, corresponds to the cardinality of V, while the size of G, denoted by ∥G∥, corresponds to the cardinality
of E.

Let us provide a few definitions related to vertices.

Definition 1.4 (Degree and neighbourhood). Let x be a vertex of a graph G = (V, E).

(i) The degree of x, or valence of x, denoted by deg(x), corresponds to the number of edges connected at
x, with a loop giving a contribution of 2,

(ii) The set of neighbours of x, denoted by N(x), corresponds to the set of vertices connected to x by an
edge,

A vertex x with deg(x) = 1 is sometimes called a leaf, and

a vertex x with deg(x) = 0 is said to be isolated. However,
one has to be careful for graphs admitting loops. Is a vertex
having only one (or more) loop(s) and no other link isolated or
not ? The answer depends on the authors. In principle, we shall
consider that a vertex which has no link to any other vertex is
isolated, even if it possesses some loops.

Based on these notions, we define the minimum degree of a

graph as δ(G) := min{deg(x) | x ∈ V} and the maximum de-
gree of a graph as ∆(G) := max{deg(x) | x ∈ V}. Also, a graph
is k-regular if deg(x) = k for all x ∈ V, see Figure 1.5.
Figure 1.5: A 3-regular graph
Let us state an easy result based on the notion of degree.

Lemma 1.5 (Euler’s degree-sum theorem). The sum of the degrees of the vertices of a finite graph is twice the
number of edges.

Consider now a graph G = (V, E) and another graph G′ = (V ′ , E ′ ) with E ′ ⊂ E and V ′ ⊂ V, and with i′ = i|E ′
whenever it is defined. In this case G′ is called a subgraph of G, and one says that G contains G′ . This notion
is rather simple, but one can be more precise.

3
Definition 1.6 (Induced subgraph). A subgraph G′ ⊂ G is an induced subgraph if, for all x, y ∈ V ′ and all
e ∈ E with i(e) = (x, y) one has e ⊂ E ′ . We also say that V ′ induces or spans G′ in G, and write G′ = G[V ′ ].
From this definition, one can define the suppression of vertices.
If G = (V, E) is a graph and if U ⊂ V, then we write G − U
for G[V \ U]. In other words, G − U corresponds to the graph
containing all vertices of V \ U and all edges of G which do not
have an endpoint in U. For edges, if F ⊂ E, one write G − F
for the graph (V, E \ F).
Remark 1.7 (Union of graphs). The notion of union of two
graphs needs to be defined with great care. Indeed, let us con-
Figure 1.6: An induced graph in pink
sider G1 = (V1 , E1 ) and G2 = (V2 , E2 ). If we consider a disjoint
union (denoted by ⊔), then G := G1 ⊔G2 with G := (V, E) and V = V1 ⊔V2 , E = E1 ⊔ E2 , with no identification
between some elements of the sets V j , or of the sets E j , for j ∈ {1, 2}. If we want to identify some elements,
then one has to do it very precisely.
One more important definition related to the division of a graph into two parts:
Definition 1.8 (Bipartite graph). An undirected graph G = (V, E) is bipartite if the set of its vertices can be
divided into two subsets V1 and V2 such that any e ∈ E has one endpoint in V1 and the other endpoint in V2 .
The sets V1 and V2 are called the bipartition subsets.
It is rather clear that a bipartite graph can not have any loop. On the other
hand, multiple edges do not prevent a graph to be bipartite. There exists
also a kind of duality between some graphs, as provided in the following
definition.
Definition 1.9 (Line graph). The line graph of an undirected graph G =
(V, E) (without loop) consists in a new graph L(G) := (V ′ , E ′ ) with V ′ = E
and two vertices in V ′ are adjacent if and only if they had a common vertex
in G.
Figure 1.7: Bipartite graph The representation of a line graph is provided in Figure 1.8. Note that the
definition of a line graph for an undirected graph with loop does not seem
to be completely clear and standard.

(a) Original graph G (b) Line graph L(G)

Figure 1.8: Graph and its line graph

Note that there exists a lot of classical graphs which are presented in any book, as for example in Section 1.2
of [GYA]. We shall not present these examples except when necessary.

4
1.2 Walks and paths
As in the previous section, the following definitions depend slightly on the authors. We always choose the
definitions which look quite general and flexible.
Definition 1.10 (Walk). A walk W of length N on a graph G = (V, E) is an alternating sequence

W = (x0 , e1 , x1 , e2 , . . . , xN−1 , eN , xN )

with the requirement that i(e j ) = (x j−1 , x j ) for j ∈ {1, . . . , N},

An illustration of a walk is given in Figure 1.9.

Figure 1.9: One walk with one loop included

Let us observe that this definition is quite flexible. Indeed, there is no restriction about intersection of a walk
with itself. Also this definition is valid for directed and undirected graphs: for the former, it means that a walk
is always going in the direction of the arrows. Note also that this definition of walk is compatible with loops
and multiple edges, and take them into account. We say that the above walk starts at x0 and ends at xN , or is
from x0 to xN . We also say that the walk is closed if x0 = xN .
Remark 1.11. For simple graphs, a walk is uniquely defined by the sequence (x j )Nj=0 since multiple edges or
loops are not allowed. The list of edges is therefore not necessary.
For k ∈ {1, 2}, consider two walks Wk with start at x0k and ends at xkNk . We say that these walks are composable
if x1N1 = x02 , and in this case we define their composition. This operation consists in defining the new walk
W = W1 W2 with
W = (x01 , e11 , x11 , e12 , . . . , x1N1 −1 , e1N1 , x1N1 , e21 , x12 , e22 , . . . , e2N2 , x2N2 ).

This new walk is of length N1 + N2 .

One walk can also be concatenated: Consider W = (x0 , e1 , x1 , e2 , . . . , xN−1 , eN , xN ) and suppose that x j = xk
for some 0 ≤ j < k ≤ N. Then one concatenated walk consists in removing x j+1 , . . . , xk and e j+1 , . . . , ek to
the alternating sequences defining the walk W. One thus get a new walk starting at x0 and ending at xN which
is “shorter” than the initial walk. Note that several concatenations might be possible on a given walk, and do
not always lead to the same resulting walk, see Figure 1.10
The notion of walks is convenient because the addition of two composable walks is again a walk. However,
walks have some drawbacks because “the walker is allowed to do some detours”. Let’s be more efficient !

5
 (a) Before concatenation (b) After concatenation

Figure 1.10: One concatenation of a walk

Figure 1.11: d(x, y) = 1 but d(y, x) = ∞

Definition 1.12 (Trail and path). A trail is a walk with no repeated edges. A path is a trail with no repeated
vertices, except possibly the endpoints x0 and xN . The length of a trail or of a path corresponds to the length
of the corresponding walk.
Note that for multiple edges, one has to be careful when defining a trail, since edges linking the same two
vertices can still appear in a trail, if each of them does not appear more than once. On the other hand, in a path
this is not possible since two vertices would appear at least twice.
The following notions could have been defined in terms of walks, but they are always realized by a path. For
that reason, it is more natural to express them in terms of paths.
Definition 1.13 (Distance in a graph). Given two vertices x, y in a graph G, the distance d(x, y) between x
and y corresponds to the length of the shortest path between x and y. If there is no path from x to y, one sets
d(x, y) = ∞.
It is clear that for undirected graphs, one has d(x, y) = d(y, x). For directed graphs, d(x, y) can be different
from d(y, x), see Figure 1.11.
Definition 1.14 (Eccentricity). The eccentricity ecc(·) : V → [0, ∞] in a graph G = (V, E) is defined as the
distance between a given vertex x to the vertex farthest to x, namely

ecc(x) := max d(x, y).

y∈V

6
Two additional notions for a graph can be defined in terms of the eccentricity:
Definition 1.15 (Diameter and radius).
(i) The diameter diam(G) of a graph G = (V, E) is defined by the maximal eccentricity on the graph, namely

diam(G) := max ecc(x) = max d(x, y).

x∈V x,y∈V

(ii) The radius rad(G) of a graph G = (V, E) is the minimum of the eccentricities, namely

rad(G) := min ecc(x).

x∈V

In a very vague sense, one can think about these two notions respectively as the diameter of a ball containing
the entire graph, and as the maximum radius of a ball contained in the graph and centered at the best place
(the “center” of the graph, as defined below).
Let us emphasize that these two concepts can take the
value ∞. It should also be noted that these notions can be
different for a directed graph and for the subjacent undi-
rected graph, once the direction on the edges have been
removed. Related to the notion of radius of a graph, one
can also look for the “center” of a graph.
Definition 1.16 (Central vertex). A central vertex of a
graph G is a vertex with minimum eccentricity, which
means x is a central vertex if ecc(x) = rad(G).
This definition does not imply that there is only one central Figure 1.12: diam(G) = 4, rad(G) = 2
vertex. In fact, one can even construct graphs for which all
vertices are the central vertex. Even if uniqueness does not
hold in general, existence always holds: there always exists at least one central vertex (with the exception of
the trivial graph with no vertex).
Paths can also be used for defining the notion of connected graphs.
Definition 1.17 (Connected). An undirected graph G = (V, E) is connected if for any x, y ∈ V there exists a
path between x and y. A directed graph is connected if the underlying undirected graph is connected.

Figure 1.13: One connected graph, one not connected graph

We observe that this definition fits with our definition of an isolated vertex (when it has no link to any vertex
different from itself). Indeed, any such point is isolated, and any graph having such a vertex would not be
connected. Note also that with Definition 1.17, the direction is suppressed. For directed graphs, some authors

7
say that they are weakly connected when they are connected with the notion defined above. This is in contrast
with the following definition, which is more useful for directed graphs:
Definition 1.18 (Strongly connected). An directed graph G = (V, E) is strongly connected if for any x, y ∈ V
there exists one path from x to y.
Observe that for strongly connected graphs, the distances d(x, y) and d(y, x)
are never equal to ∞, for any pair of vertices (x, y). However, these two
quantities can still be different, see Figure 1.14.

1.3 Cycles
The notion of closed walks has already been introduced, and since paths
are special instance of walks, closed paths are also already defined. A
name is given to non-trivial closed paths (here non-trivial means a path not
Figure 1.14: Strongly connected reduced to a single vertex).
graph Definition 1.19 (Cycle). A cycle is a (non-trivial) closed path.
Observe that for simple graphs, a cycle has always a length of at least 3.
On the other hand, for graphs with loops or multiple edges, a cycle can
be of length 1 (for a loop) or of length 2 (between 2 vertices linked by
multiple edges). If a graph has no cycle, it is called acyclic, and we shall come back to them subsequently.
For graphs with cycles, we can wonder what is the length of the shortest cycle ?
Definition 1.20 (Girth). The girth of a graph G is the length of the shortest cycle in G, and it is denoted by
girth(G). If G is acyclic, then its girth is ∞.
In the next statement, a characterization of bipartite graphs in terms of cycles is provided. A proof is available
in [GYA, Thm. 1.5.4].
Theorem 1.21. An undirected graph is bipartite if and only if it has no cycle of odd length.
The following extension of this result has been proposed by Duc Truyen Dam, and the proof has been provided
by Chang Sun (both former G30 students).
Theorem 1.22 (Strongly connected bipartite graphs). A strongly connected oriented graph G is bipartite if
and only if it has no cycle of odd length.
Let us now introduce a cycles with an additional property:
Definition 1.23 (Hamiltonian cycle and graph). A cycle that includes ev-
ery vertex of a graph is called a Hamiltonian cycle. A graph having a
Hamiltonian cycle is called a Hamiltonian graph.
Let us also stress that a Hamiltonian cycle has to go through every vertices,
but it will not use all edges of a graph in general (and is not allowed to
use twice any vertex). These cycles are important because their existence
Figure 1.15: A Hamiltonian means that there exists a closed path visiting all vertices once. Hamiltonian
graph cycles are also related to the famous travelling salesman problem. What
is the analogue definition for edges instead of vertices ? The answer is

8
provided below. Note that we consider trails instead of paths, which means that a vertex can be visited more
than once, but any edge can be used only once.
Definition 1.24 (Eulerian trail and graph).
(i) An Eulerian trail is a trail that contains every edge of a graph.
(ii) An Eulerian tour is a closed Eulerian trail.
(ii) An Eulerian graph is a connected graph which possesses an Eulerian tour.
Let us remark that there are natural questions related to the above two
notions. Given a connected graph G = (V, E), does it posses a Hamiltonian
cycle, or is it an Eulerian graph ? One answer for simple graphs is provided
in [Die, Thm. 1.8.1] while the proof for more general graphs is given in
[GYA, Thm. 4.5.11].
Theorem 1.25. A connected, undirected and finite graph is Eulerian if and
only if every vertex has even degree.
Let us finally gather in the next statement a few results which link some of
the notions introduced so far. We also recall that δ(G) and ∆(G) denote the
minimal and the maximal degree of a graph.
Theorem 1.26. Let G be a simple undirected finite graph:
(i) G contains a path of length δ(G) and a cycle of length at least δ(G)+ Figure 1.16: Eulerian graph
1 (provided δ(G) ≥ 2).
(ii) If G contains a cycle, then girth(G) ≤ 2 diam(G) + 1.
(iii) If rad(G) = k and ∆(G) = d ≥ 3, then G contains at most d
d−2 (d − 1)
k

vertices.

1.4 Weighted graphs

Additional information can be encoded in a graph. In particular, a weight can be added to each vertex and / or
to each edge.
Definition 1.27 (Weighted graph). A weighted graph G = (V, E, ω) is a graph (V, E) together with two maps
ωV : V → R and ωE : E → R. The notation ω refers to the pair (ωV , ωE ).
Note that quite often, one considers these maps with value in (0, ∞) instead of R, and that the index V or E
is often drop. We then have ω : V → R and ω : E → R, and this does not lead to any confusion. Weighted
graphs are very natural and useful in applications. In this framework one has the following definition:
Definition 1.28 (Weighted length). The weighted length of a walk in a weighted graph is given by the sum of
the weight on the corresponding edges.
Clearly, this definition is also valid for trails, paths or cycles, since they are special instances of walks. For
a graph without weights, it corresponds to the original notion of length of a walk if one endows the graph
with the constant weight 1 on every edge (and on every vertex). Note that in a weighted graph, the shortest
path (disregarding weights) between two vertices might not be the one with the smallest weighted length. In

9
applications, one has therefore to specify which quantity has to be minimized: the unweighted length, or the
weighted length ? Of course, it depends on the purpose.

10
Chapter 2

Representations and structures

In this chapter, we first introduce a few ways to encode the information contained in a graph. Then, we develop
the notion of isomorphisms, and list some invariant structures of a graph.

2.1 Matrix representations

Since linear algebra contains a large set of powerful tools, it is rather natural to use this theory for analysing
graphs. There exist several ways to represent a graph with matrices. The figures about adjacency matrices are
borrowed from [3]. Note that in these figures, vertices are denoted by v j while in the text they are written x j .
Definition 2.1 (Adjacency matrix). Let G = (V, E) be a finite graph, and set V = {x1 , . . . , xN }. The adjacency
matrix AG of G is a N × N matrix with entries
a jk = #{e ∈ E | i(e) = (x j , xk )}
with the convention that (x j , xk ) = (xk , x j ) if the G is undirected, and that a loop satisfying i(e) = (x j , x j ) is
counted twice for an undirected graph, but only once for a directed graph.

Figure 2.1: Adjacency matrix of an undirected graph

It easily follows from this definition that the adjacency matrix of an undirected graph is a symmetric matrix,
since a jk = ak j , see Figure 2.1. In addition, the relation
X X
deg(x j ) = a jk = ak j
k k

11
 Figure 2.2: Non symmetric adjacency matrix

holds for any undirected graph and any x j ∈ V. Note that these properties are not true in general for a directed
graph. However, let us define the indegree and the outdegree of a vertex of a directed graph:

degin (x) = #{e ∈ E | i(e) = (y, x) with y arbitrary} (2.1.1)

and
degout (x) = #{e ∈ E | i(e) = (x, y) with y arbitrary}. (2.1.2)
Clearly, one has degin (x) + degout (x) = deg(x). Then, if G is a directed graph, the following relations hold, see
Figure 2.2 : X X
a jk = degout (x j ) and a jk = degin (xk ).
k j

Note also that the convention of counting twice a loop for undirected graph is coherent with the degree 2
attached to a loop in Definition 1.4, see Figure 2.3. However, this choice has also some drawbacks, and the
convention is not universal. For example, this convention leads to wrong result in the next statement about
the powers of the adjacency matrix. Note that in this statement and in the sequel, we take the convention that
N := {1, 2, 3, . . . }.

Figure 2.3: Adjacency matrices in the presence of loops

Proposition 2.2. Let G be a graph and let AG be the adjacency matrix (with the convention that a loop
r
of the
provides a contribution 1 on the diagonal also for undirected graphs). For any r ∈ N the entry AG jk
rth power of AG is equal to the number of walks of length r from x j to xk .

12
Proof. Let AG be a N × N adjacency matrix. When r = 1, AG r
is the number of walks of length 1 from x
jk j
to xk by the definition of the adjacency matrix. Then, let r ∈ N be given and suppose AG r
is the number of
jk
walks of length r from x j to xk . Consider AGr+1
, and let us compute this entry by using the summation of
jk
multiplication of entries of two matrices.
N
X
r+1

= r 1

lk .


AG jk AG jl AG (2.1.3)
l=1

By the assumption and definitions mentioned above, AG r
is the number of walks of length r from x to x ,
jl j l
and AG 1
is the number of walks of length 1 from x to x . Hence, Ar
A1
is the number of walks of
lk l k G jl G lk
length r + 1 consisting of two walks, one is the walk of length r from x j to xl and another one is the walk of
jl AG lk indicates the number of all walks of length r + 1 from
P r

length 1 from xl to xk . It follows that l AG 1

x j to xk . Thus, we can regard the l.h.s. of (2.1.3) as the number of walks of length r + 1 from x j to xk . One
finishes the proof by an induction argument. □

Let us also mention that adjacency matrices can also be used for checking if two graphs are isomorphic, see
the following sections. Indeed, if AG and AG′ correspond to the adjacency matrices of two finite graphs with
the same order, then a reordering of the vertices on one graph should lead to two identical adjacency matrices
if the graphs are isomorphic. However, this approach is very time and energy consuming, and therefore very
inefficient.
We now provide another tool involving matrices. Unfortunately, the definition is not exactly the same for
directed or undirected graphs. Also, these definitions depend slightly on the authors, especially for the value
associated with a loop.
Definition 2.3 (Incidence matrix of an undirected graph). Let G = (V, E) be a finite undirected graph with
V = {x1 , . . . , xN } and E = {e1 , . . . , e M }. The incidence matrix IG of G consists in the N × M matrix with entries




 0 if x j is not an endpoint of eℓ ,
i jℓ = 


 1 if x j is an endpoint of eℓ ,


2 if eℓ is a loop at x j .


Figure 2.4: Incidence matrix of an undirected graph, see Fig. 2.6.4 of [GYA]

The following properties can be easily inferred from this definition:

Lemma 2.4. For the incidence matrix of a finite undirected graph the following relations hold:
M
X N
X
i jℓ = deg(x j ) and i jℓ = 2.
ℓ=1 j=1

13
For a directed graph, the incidence matrix is defined as follows:

Definition 2.5 (Incidence matrix of a directed graph). Let G = (V, E) be a finite directed graph with V =
{x1 , . . . , xN } and E = {e1 , . . . , e M }. The incidence matrix IG of G consists in the N × M matrix with entries




 0 if x j is not an endpoint of eℓ ,

1 if x j is the target of eℓ ,


i jℓ = 





 −1 if x j is the origin of eℓ ,

2 if eℓ is a loop at x j .


Figure 2.5: Incidence matrix of an undirected graph, see Fig. 2.6.5 of [GYA]

Note that one of the undesirable features of these matrices is that they contain many zeros. One can be more
economical by keeping only the non-zero information but one loses the power of matrices. The incidence
tables corresponds to new representations.

Definition 2.6 (Incidence table of an undirected graph). Let G = (V, E) be a finite undirected graph with
V = {x1 , . . . , xN } and E = {e1 , . . . , e M }. The incidence table IV:E (G) lists, for each vertex x j , all edges eℓ
having x j as one endpoint.

Figure 2.6: Incidence table of an undirected graph, see Ex. 2.6.6 of [GYA]
For directed graphs, the tables have to be duplicated.

Definition 2.7 (Incidence tables of a directed graph). Let G = (V, E) be a finite directed graph with V =
{x1 , . . . , xN } and E = {e1 , . . . , e M }. The incoming incidence table inV:E (G) lists, for each vertex x j , all edges
eℓ having x j as a final point (target), while the outgoing incidence table outV:E (G) lists, for each vertex x j , all
edges eℓ having x j as an initial point (origin).

14
 Figure 2.7: Incidence tables for the graph of Figure 2.5, see Ex. 2.6.7 of [GYA]

2.2 Isomorphisms
Our general aim is to provide some efficient tools for deciding when two graphs contain the same information,
even if they are represented quite differently. What characterizes a graph is its pattern of connections, and the
direction on edges for directed graphs, but the way they are represented does not matter. For example, the two
graphs of Figure 2.8 correspond to the same graph, even if they do not look similar.

Figure 2.8: Two representations of the same graph, see. Fig. 2.1.1 of [GYA]

We say that these two pictures represent the same graph because any vertex has the same adjacent vertices on
both representations. Clearly, if the graph has loop(s) or multiple edges, or if the graph is directed, we would
like to have these properties similarly represented in the two pictures. The correct notion encoding all the
necessary information is provided in the next definition.

Definition 2.8 (Isomorphism of graph). Let G = (V, E) and G′ = (V ′ , E ′ ) be two graphs, with internal map
denoted respectively by i and by i′ . A map f : G → G′ is an isomorphism of graphs if f = ( fV , fE ) with
fV : V → V ′ and fE : E → E ′ satisfy

(i) fV and fE are bijections,

(ii) For any e ∈ E with i(e) = (x, y) in V × V, one has i′ fE (e) = fV (x), fV (y) in V ′ × V ′ .

Whenever such an isomorphism exists, we say that G and G′ are isomorphic, and write G  G′ .

Note that this definition holds for the general definition of a graph provided in Definition 1.1, see Figures 2.9
and 2.10. Once again, if the graph is undirected, the pairs (x, y) and (y, x) are identified in V × V, and the same
for the pairs fV (x), fV (y) and fV (y), fV (x) in V ′ × V ′ , but this property does not hold for directed graphs. In



the special case of simple graphs, as presented in Remark 1.2, the above definition can be slightly simplified
since an edge is uniquely defined by its endpoints, see Figure 2.11. Observe finally that another way to present

15
 Figure 2.9: Isomorphism of a graph with loops and multiple edges

the second condition of Definition 2.8 is to say the following diagram is commutative:

i
E V ×V
fE fV × fV
i′
E′ V′ × V′ .

Figure 2.10: a) and d) are isomorphic, b) and c) are isomorphic

Figure 2.11: Isomorphism of a simple graph

Remark 2.9. One observes that the notion of isomorphisms is an equivalence relation. Indeed, G  G
(reflexive property) by considering the identify map for the graph isomorphism; if G  G′ , then G′  G
(symmetric property) because f −1 also defines an isomorphism of graph; if G  G′ (through a map f ) and
G′  G′′ (through a map f ′ ), then G  G′′ (transitive property) because the composition of maps f ′ ◦ f also
defines an isomorphism of graph, as it can be easily checked.

16
Deciding when two graphs are isomorphic is a hard and famous problem, the so-called graph-isomorphism
problem. Except for very small graphs, it is very time consuming. However, by looking at specific quantities,
one can often easily show that two graphs are not isomorphic. Such quantities are presented in the next
definition.
Definition 2.10 (Graph invariant). A graph invariant is a property of a graph which is preserved by isomor-
phisms.
In other terms, such a quantity is the same in any representation of a graph. Thus, if this quantity is not the
same in two graphs, one can directly say that these two graphs are not isomorphic. Let us list a few quantities
which are clearly graph invariants, additional examples will appear in this chapter. We recall that the notation
N(x) for the set of neighbours of x has been introduced in Definition 1.4.
Proposition 2.11 (Graph invariants 1). Let G = (V, E) be a graph. The following quantities are graph invari-
ants:
(i) The order and the size (see Definition 1.3), with the convention that these quantities can take the value
∞,
(ii) The set of degrees (see Definition 1.4), namely {deg(x) | x ∈ V},
(iii) The set of degrees of neighbours, namely

{deg(y) | y ∈ N(x)} for any x ∈ V ,



(iv) The set of lengths of walks, of trails, or of paths in G, see Definitions 1.10 and 1.12,
(v) The diameter, the radius and the girth (see Definitions 1.15 and 1.20).
Let us observe that for directed graphs, a refined version of (ii) and (iii) exists. We recall that the notion
of indegree and outdegree have been introduced in (2.1.1) and (2.1.2), respectively. Then, the following
quantities are directed graphs invariants:
(ii’) The set if indegrees and outdegrees, namely {degin (x) | x ∈ V}, and {degout (x) | x ∈ V},
(iii’) The indegrees and outdegrees of neighbours, namely

{degin (y) | y ∈ N(x)} for any x ∈ V ,



and
{degout (y) | y ∈ N(x)} for any x ∈ V .


Note that these invariants could be even further refined by considering separately the set of neighbours of x
which are connected by an edge e satisfying either o(e) = x or t(e) = x. We leave the definition of these
invariants to the interested reader.

2.3 Automorphisms and symmetries

Identifying the symmetries of a graph is often useful, even if it is not an easy task. Clearly, symmetries should
not depend on the representation but should again be an intrinsic property. The following definition contains
the necessary notion for dealing with symmetries of a graph.

17
Definition 2.12 (Automorphism). Let G be a graph. An isomorpism from G to G is called an automorphism.
Clearly, any graph possesses an automorphism, the identity map. In addition, by the properties of the equiv-
alence relation mentioned in Remark 2.9, one observes that the set of automorphisms of a graph is in fact
a group: the composition of automorphisms is associative, and every automorphism has an inverse (it corre-
sponds to the map f −1 mentioned in Remark 2.9). One speaks about the automorphisms group of a graph. The
main idea now is to look at the size of this group. If this group is big, then the graph has several symmetries,
while if the group contains only the identity element, then the graph has no symmetry at all. Observe that for
simple undirected graphs, automorphisms can be completely described by permutations of the set of vertices.
Figure 2.12 contains three representations of the same simple graph, called the Petersen graph. At first glance,
it is not easy to see that these three graphs are isomorphic, but this can be checked by looking at the edges
connected at any vertex. Then, what about automorphisms ? It is clear on the picture (a) that any rotation
by 2πk/5 with k ∈ {0, 1, 2, 3, 4} defines an automorphism. A reflection symmetry by a vertical axis is also
clear on figure (a). On figures (b) and (c) a reflection symmetry by a vertical axis is also clear, but these three
reflection symmetries do not correspond to the same automorphisms of G.

Figure 2.12: Three representations of the Petersen graph, see. Fig. 2.2.3 of [GYA]

Let us try to describe these automorphisms by using a convenient notation. More information on the permuta-
tion group can be found in the Appendix A.4 of [GYA] or in Wikipedia [2]. One way to describe the rotation
by 2π/5 of figure (a) is to write
(0 1 2 3 4)(5 6 7 8 9)
describing the action of the automorphism: 0 → 1, 1 → 2, 2 → 3, 3 → 4, 4 → 0 and 5 → 6, 6 → 7,
7 → 8, 8 → 9, 9 → 5. In a similar way, the three mentioned reflection symmetries can be described by
(1 4)(2 3)(6 9)(7 8)(0)(5), (0 5)(1 8)(2 3)(4 7)(6)(9) and (0 2)(3 4)(5 7)(8 9)(1)(6).
Whenever a group acts on an object, a useful concept is the one of orbit. Here, we keep in mind the action
of the automorphism group acting on a graph, but the definition is more general. Note that since G is already
used for a graph, we use the notation H for the group in the next definition.
Definition 2.13 (Orbit). Let H be a group acting on a set X, with an action denoted by h(x) ∈ X for x ∈ X
and h ∈ H. For any x ∈ X the orbit of x is the set {h(x) | h ∈ H} and is denoted by Orb(x).
In other words, Orb(x) corresponds to all points taken by x when a group H acts on this point. It is easily
observed that for any x, y ∈ X one has either Orb(x) = Orb(y) or Orb(x)∩Orb(y) = Ø, and no other alternative.
Let us consider the graph given in Figure 2.13. This graph has again several automorphisms obtained by
reflection symmetries by a vertical axis, a horizontal axis, but also the one obtained by the combination of
these two automorphisms. If we list them with the notation introduced above one gets

(1)(2)(3)(4)(5)(6)(7)(8)

18
 Figure 2.13: A graph with several symmetries

(1 8)(2 7)(3)(4)(5)(6)
(1)(2)(3 5)(4 6)(7)(8)
(1 8)(2 7)(3 5)(4 6).

Let us now describe the orbits of the vertices and of the edges under the group generated by these four
automorphisms. For this example, the vertex orbits are

Orb(1) = Orb(8) = {1, 8}, Orb(2) = Orb(7) = {2, 7},

Orb(4) = Orb(6) = {4, 6}, Orb(3) = Orb(5) = {3, 5},

while the edge orbits are

Orb(a) = Orb(b) = {a, b}, Orb(c) = Orb(d) = {c, d},

Orb(e) = Orb( f ) = Orb(g) = Orb(h) = {e, f, g, h}, Orb(i) = {i}.

Observe that these notions apply to directed graphs as well, but the orien-
tation is one more ingredient to take into account. For example, the graph
represented in Figure 2.14 has a group of automorphism reduced to the
identity only.
Let us still state some easy properties of elements on orbits. These proper-
ties can be deduced from Proposition 2.11.
Lemma 2.14.
(i) All vertices in one orbit have the same degree (and the same indegree
and outdegree for directed graphs),
(ii) All edges in one orbit have the same pair of degrees at their end-
Figure 2.14: No symmetry
points (and the same indegrees and outdegrees for directed graphs).

19
Let us check what are the vertex orbits and the edge orbit of Figure 2.12 ? Quite surprisingly, this graph has
only one vertex orbit (containing all vertices) and one edge orbit (containing all edges). It means that given
two vertices x and y, there exists one automorphism sending x on y, and a similar observation holds for any
pair of edges. In such a case, we speak about a vertex transitive graph and a edge transitive graph.

2.4 Subgraphs
Some properties of a graph can be determined by the existence of some subgraphs inside it.
One example is Theorem 1.21 about undirected bipartite graphs and the
existence of cycles of odd length. In this section we gather several notions
related to subgraphs, not all these notions are related to each others.
Definition 2.15 (Clique). Let G = (V, E) be an undirected graph and con-
sider a subset S ⊂ V. This set S is called a clique if for any x, y ∈ S with
x , y there exists e ∈ E with i(e) = (x, y).
Note that the first part of the definition means that every two distinct ver-
tices in S are adjacent. One speaks about a a maximal clique S if there
is no clique S ′ with S ⊂ S ′ ⊂ V, see Figure 2.15. Observe also that this
requirement is a maximality condition, and that some authors include this
requirement in the definition of a clique. The notion of clique is interesting
for the next definition.
Definition 2.16 (Clique number). The clique number w(G) of a graph G
corresponds to the number of vertices of a largest clique in G. Figure 2.15: 1 clique, 1 maximal
Note that there might be several cliques containing w(G) vertices. Thus, clique
there is no uniqueness for the “largest” clique, but the clique number is uniquely defined. In a vague sense, this
clique number gives the maximal number of vertices which are tightly connected to each others, see Figure
2.16. Two concepts complementary to the notions of clique and clique number are:
Definition 2.17 (Independent set and independence number). Let G = (V, E) be an undirected graph and
consider a subset S ⊂ V. This set S is called independent if no pair of vertices in S is connected by any
edge in G. The independence number α(G) of a graph G corresponds to the number of vertices of a largest
independent set in G.
As before, there is no uniqueness for the largest independent set in G, but
the independence number is uniquely defined, see Figure 2.17 for example.
Note that these last notions extend directly to directed graphs. However,
for the notion of a clique, it is not so clear what would be the most useful
extension ? Should we use the notion of a clique in the underlying undi-
rected graphs (when orientation is suppressed), or should we look for pair
of edges connected by directed edges in both directions ? The choice of
the most suitable notion would certainly depend on the applications.
A somewhat related (but more global) notion is provided in the next defi-
nition.
Definition 2.18 (Component). A component of a graph G is a maximal
connected subgraph of G.
Figure 2.16: w(G) = 4
20
 Figure 2.17: Independence number: α(G) = 5

Figure 2.18: A graph with 4 components

In other words, a connected subgraph G′ is a component of G if G′ is not a proper subgraph of any connected
subgraph of G. Here, proper simply means different. It thus follows that any graph is made of the disjoint
union of its components. The number of components of G will be denoted by c(G), see Figure 2.18.

Since orientation does not play any role in the definition of connected graphs, it also does not play any role in
the definition of a component. Note that an alternative definition could be provided in terms of paths: For any
pair of vertices in one component there exists a path (with the direction on the edges suppressed) having these
vertices as endpoints, and the edges for all these possible paths belong to same component of the graph.

Recall that the suppression of a vertex or an edge from a graph has been introduced in Section1.1. Together
with the notion of component, we can now select some vertices or edges which are more important than others.
More precisely, the following definitions identify the most vulnerable parts of a graph, see also Figures 2.19
and 2.20.

Definition 2.19 (Vertex-cut and cut-vertex). Let G = (V, E) be a graph.

(i) A vertex-cut is a set of vertices U ⊂ V such that G − U has at least one more component than G.

(ii) A vertex x ∈ V is called a cut-vertex or a cutpoint if {x} is a vertex-cut.

Definition 2.20 (Edge-cut and cut-edge). Let G = (V, E) be a graph.

(i) An edge-cut is a set of edges F ⊂ E such that G − F has at least one more component than G.

(ii) An edge e ∈ E is called a cut-edge or a bridge if {e} is an edge-cut.

These notions will be used again when graph’s connectivity will be discussed. For the time being, let us
simply complement the content of Proposition 2.11 with a few more graph invariants.

21
 Figure 2.19: Graph with two cut-vertices Figure 2.20: Graph with three cut-edges

Proposition 2.21 (Graph invariants 2). Let G = (V, E) be a graph. The following quantities are graph invari-
ants:
(i) For undirected graphs, the clique number and the independence number, namely w(G) and α(G),
(ii) The number of components, namely c(G),
(iii) The number of distinct cutpoints or bridges.

22
Chapter 3

Trees

Trees play a central role in graph theory, and are at the root of many algorithms. We first present the theoretical
part, and subsequently describe several applications.

3.1 Trees and forests

We first provide the definition of a tree in the general setting that we have introduced so far. Usually, trees and
directed trees are treated separately.
Definition 3.1 (Tree). A tree is a connected graph whose underlying undirected graph has no cycle.
Note first that the acyclicity condition prevents any tree to have a loop or any multiple edges. For that reason,
trees are always simple graphs, as defined in Remark 1.2.
For undirected graphs the above definition reduces to a connected
and acyclic graph. For directed graphs, this definition does not see
the orientation on the edges, and is probably not the most interest-
ing definition. Indeed, the notion of connected graph is based on the
underlying graph, and the acyclicity property is also imposed on the
underlying undirected graph. For directed graphs, a more interesting
notion is the one of acyclic digraph, see Figure 3.1. These oriented
graphs have no cycle, but the underlying unoriented graph can have
cycles. Acyclic digraphs have also several applications, see [4]. For
simplicity, we shall simply say that a directed graph has no undi-
rected cycle whenever the underlying undirected graph has no cycle.
Directed graphs which are trees are also called oriented trees, poly-
trees, or singly connected network. In the sequel, whenever we want
to emphasize that the tree considered is also an oriented graph, we
shall call it an oriented tree, and accordingly an unoriented tree will
be a tree without orientation, see Figure 3.2.
Figure 3.1: An acyclic digraph
Recall that a leaf is a vertex of degree 1. It is not difficult to observe
(and prove) that any finite tree containing at least one edge has also
,
at least two leaves. In other words, a non-trivial tree must have at least two leaves . Also, if a tree is made

23
 Figure 3.2: Three trees: two unoriented, one oriented

of n vertices, it contains exactly n − 1 edges. Note that a graph with no undirected cycle is called a forest, see
Figure 3.3, and that such a forest is made of the disjoint union of trees, each of them defining a component of
the graph, see Definition 2.18. Some authors use the terms polyforest or oriented forest for the disjoint union
of oriented trees.
We now provide some equivalent definitions of a tree. The proof is
provided in [GYA, Thm. 3.1.8] for undirected graphs.
Proposition 3.2. Let G be a graph with n vertices. The following
statements are equivalent:
(i) G is a tree,
(ii) G contains no undirected cycle and has n − 1 edges,
(iii) G is connected and has n − 1 edges,
(iv) G is connected and every edge is a cut-edge, see Definition
2.20,
(v) Any two vertices of G are connected by exactly one unoriented
path (when the orientation on the edges is disregarded),
Figure 3.3: One forest
(vi) G contains no undirected cycle, and the addition of any new
edge e on the graph generates a graph with exactly one undirected cycle.
Recall that the notion of a central vertex has been introduced in Definition 1.16. Such a vertex has the property
of being at a minimum distance to all other vertices, and therefore is located at a “strategic position”. This
position is usually not unique, and examples with several central vertices are easy to construct. For trees, the
situation is completely different. In fact, the following statement has already been proved in 1869, but note
that it applies only to unoriented graphs.
Theorem 3.3. For any finite unoriented tree, there exists only one or two central vertices.
The proof is not difficult but relies on several lemmas, see pages 125 and 126 of [GYA]. Let us just emphasize
the main idea: If x is a central vertex in an unoriented tree, then x is still a central vertex in the induced tree
obtained by removing all leaves. By the process of removing leaves iteratively, one finally ends up with a tree
consisting either of one single vertex, or of two vertices connected by an edge. This unique vertex or the two
vertices correspond to the central vertices of the initial unoriented tree.

24
 Figure 3.4: Irreducible trees with less than 12 vertices, see [5]

Note that this almost unicity of the central vertex of a tree can be used for the definition of the root of a tree.
Before introducing rooted trees, and for fun, let us introduce one more notion:
Definition 3.4 (Irreducible tree). An irreducible tree, or series-reduced tree is an unoriented tree in which
there is no vertex of degree 2.
Note that there exists a classification of such trees, modulo isomorphisms. The table of the ones with less that
12 is provided in Figure 3.4.

3.2 Rooted trees

In a tree, it is sometimes important to single out one vertex. This idea is contained in the next definition.
Definition 3.5 (Rooted tree). A rooted tree is tree with a designated vertex called the root.
On drawings, the root of a rooted tree is often put at a special
place (top, bottom, left or right of the picture), see figure 3.5.
Note that in this definition, the choice of the root is arbitrary.
However, in applications there often exists a natural choice for
the root, based on some specific properties of this vertex. For
oriented trees, two specific oritentations of the edges are of spe-
cial importance, as mentioned in the following definition.

Figure 3.5: Two trees with root r

25
Definition 3.6 (Arborescence and anti-arborescence). An arborescence or out-tree is a rooted oriented tree
with all edges pointing away from the root, and an anti-arborescence or in-tree is a rooted oriented tree with
all edges pointing towards the root.
Let us illustrate these definitions: In Figure 3.6, the first tree is a rooted unoriented tree without any special
property, the second tree corresponds to a tree with its root coinciding with the unique central vertex, while
the third tree is an arborescence. Note that underlying graphs for the first and the second tree are the same,
only the choice of a specific vertex as a root makes them look different. As a consequence, these two trees are
isomorphic as graphs, but not as rooted trees (for which the two roots should be in correspondence).

Figure 3.6: Three trees

Let us now introduce some names related to vertices.

Definition 3.7. Let G be an unoriented rooted tree, or an arborescence, with root denoted by r.
(i) The height, or the depth, or the level of a vertex x corresponds to the distance d(r, x),
(ii) The height of the tree is the greatest level, or equivalently the length of the longest path with one
endpoint at r,
(iii) The ancestors or ascendants of a vertex x is the set of all vertices contained in the path from r to x, while
the descendants of x is the set of all y having x as an ancestor. One speaks about proper ancestors of x
and proper descendants of x when x is not included in these sets,
(iv) The parent of a vertex x is the ancestor y satisfying d(r, y) = d(r, x) − 1, and a child of x is a descendant
y satisfying d(r, y) = d(r, x) + 1, with the convention that the root has no parent, and a leaf has no child,
(v) Two vertices having the same parent are called siblings,
(vi) An internal vertex of a tree is a vertex which possesses at least one child.
It is easily observed that a vertex x has only one parent but is allowed to have several children. Let us also
mention that these notions can also be applied to anti-arborescence, if the distance d(r, x) is replaced by d(x, r),
and the directions of paths are reversed. In the sequel we shall usually not mention anti-arborescences, but
keep in mind that any information on arborescences can be adapted to anti-arborescences. On the other hand,
one observes that the notions introduced above do not really fit with arbitrary oriented rooted trees, since given
an arbitrary vertex x, the distances d(r, x) and d(x, r) could be infinite.
Let us now discuss the regularity of trees.

26
Definition 3.8 (p-ary tree, complete p-ary tree). Let p be a natural number.
(i) A p-ary tree is an unoriented rooted tree or an arborescence, in which every vertex has at most p
children, and at least one of them possesses p children,
(ii) A complete p-ary tree is an unoriented rooted tree or an arborescence in which every internal vertex
has p children, and each leave of the tree has the same depth.

Figure 3.7: A 3-ary tree and a complete 2-ary tree

Another useful notion can be defined for the rooted trees considered so far. Note however that it is an additional
structure which is added repeatedly to the children of each vertex.
Definition 3.9 (ordered tree). An ordered tree is an unoriented rooted tree or an arborescence in which the
children of each vertex are assigned with a fixed ordering.
On drawing, the ordering is often represented by the respective position of the children of any given vertex.
The primary example of an ordered tree is the binary tree, a 2-ary tree with possibly a left child and a right
child for each vertex. Another example is the ternary tree, a 3-ary tree with children distinguished into left
child, mid child and right child.

Figure 3.8: One binary tree and one ternary tree

Let us now list a few applications of rooted trees, more will be presented in the following sections. The
forthcoming pictures are all borrowed from [GYA, Sec. 3.2].
Example 3.10 (Decision tree). A decision tree is a decision support tool that uses a tree-like model of deci-
sions and their possible consequences, including chance event outcomes, resource costs, and utility. It often
lists all possible sequences, and provides a final weight (for example probability or cost) to each path in the
tree, see Figure 3.9 and [6].

27
 Figure 3.9: The first three moves of tic-tac-toe

Example 3.11 (Tree data structure). Trees are widely used whenever data contains a hierarchical structure,
see Figure 3.10. The notion of parent and children can then be used efficiently.

Figure 3.10: Classification in libraries is often based on a tree data structure

Example 3.12 (Sentence parsing). Rooted trees can be used to parse a sentence in any language, see Figure
3.11. For such an application, a predefined structure of the tree is applied to a sentence.
Let us finally mention another application of trees which will appear again the future: the shortest path tree.
Given a connected unoriented graph and choosing one vertex x, it is always possible to realize one tree T with
root x such that the path from the root x to any other vertex y in T realizes the shortest path from x to y in G.
Note that this tree is usually not unique, but allows us to get a good representation of the distance between x
and any other vertex of the graph.

3.3 Traversals in binary trees

In this section we introduce a basic tool for encoding or decoding some information stored in binary trees,
see the left picture in Figure 3.8. Most of the constructions apply to more general ordered p-ary trees as well.
Note that this section and the following ones are very much oriented towards computer science.
Definition 3.13 (Graph traversal). A graph traversal or a graph search is the process of visiting systematically
each vertex in a graph.
Here “visiting” means either collect the data, or compare or perform the data, or update the data stored at a
vertex. Since each vertex are visited successively, a graph traversal also corresponds to endowing the vertices
of a graph with a global ordering. For a general graph, a traversal can be almost arbitrary, but for trees (and in

28
 Figure 3.11: Parsing a sentence

particular for binary trees) some traversals are rather natural. Note that we consider planar trees in the sense
that the order on the tree is indexed by left and right. As a consequence, given a vertex x of the graph, its left
subtree L(x) and its right subtree R(x) are clearly defined, see Figure 3.12.
The general recursive pattern for traversing a binary tree is this: Go down
one level to the vertex x. If x exists (is non-empty) execute the following
three operations in a certain order: (L) Recursively traverse x’s left subtree,
(R) Recursively traverse x’s right subtree, (N) Process the current node x
itself. Return by going up one level and arrive at the parent of x. The
following examples are the most used traversals:
Definition 3.14 (Traversal of binary trees). Let G be a binary tree, with
the root represented at the top.
(i) The level-order traversal consists in enumerating the vertices in the
top-to-bottom, left-to-right order,
(ii) The pre-order traversal or NLR is defined recursively by 1) process
the root, 2) perform the pre-order traversal of the left subtree, 3) per-
form the pre-order traversal of the right subtree,
(iii) The in-order traversal or LNR is defined recursively by 1) perform
the in-order traversal of the left subtree, 2) process the root, 3) per-
form the in-order traversal of the right subtree,
Figure 3.12: Left subtree L(x)
(iv) The post-order traversal or LRN is defined recursively by 1) perform and right subtree R(x)
the post-order traversal of the left subtree, 2) perform the post-order
traversal of the right subtree, 3) process the root .
Let us illustrate these traversals with Figure 3.13 from [7].

29
 Figure 3.13: Traversals of a binary tree

(i) Level-order traversal:

F, B, G, A, D, I, C, E, H,

(ii) Pre-order traversal (NLR) in red:

F, B, A, D, C, E, G, I, H,

(iii) In-order traversal (LNR) in yellow:

A, B, C, D, E, F, G, H, I,

(iv) Post-order traversal (LRN) in green:

A, C, E, D, B, H, I, G, F.

In the next section we gather several applications of binary trees. Traversals will also play a role for reading a
tree.

3.4 Applications
In applications, the letter T is often used for trees instead of the letter G which was more natural for general
graph. In this section, we follow this general trend and use the letter T instead of G.

3.4.1 Arithmetic expression trees

Let us first look at an application of the in-order traversal for arithmetic expressions. A similar application
holds for boolean expressions.

Definition 3.15 (Arithmetic expression tree). An arithmetic expression tree is a binary tree, with arithmetic
expressions (operators) at each internal vertex, and constants or variables at each leaf.

30
Clearly, such a tree can be read by the different traversals introduced in Definition 3.14. In this setting, the
most natural traversal is the in-order traversal. However, when printing the expression contained in such a
tree, opening and closing parentheses must be added at the beginning and ending of each expression. The
interest of these trees is precisely that they take care of the ordering of the operations. As every subtree
represents a sub-expression, an opening parenthesis is printed at its start and the closing parenthesis is printed
after processing all of its children. For example, the arithmetic expression tree represented in Figure 3.14
corresponds to the expression (5 + z)/ − 8 ∗ (42 ), see also [8]. Note that following the in-order traversal,


one should write 8− and not −8. However, the sign − is in fact slightly misleading since it represents here
the operation “take the opposite”. When applied to the number 8, the outcome is indeed −8. The operation
“take the opposite” or “take the inverse” are called unary operators because they require only one child, and
not two children as most of the other operations.

Figure 3.14: An arithmetic expression tree

3.4.2 Binary search trees

We now introduce an application of binary trees for the efficient search of data. In the next definition, we
consider a totally ordered set (S , ≤), which means a set S with a binary operation ≤ satisfying the following
three conditions for any a, b, c ∈ S :

(i) Antisymmetry: If a ≤ b and b ≤ a, then a = b,

(ii) Transitivity: If a ≤ b and b ≤ c, then a ≤ c,

(iii) Connexity: Either a ≤ b or b ≤ a.

Clearly, N, Z or R are totally ordered sets, but introducing this notion gives us more flexibility. When a ≤ b
we say that a is smaller than or equal to b.

Definition 3.16 (Binary search trees (BST)). Binary search trees (BST), also called ordered or sorted binary
trees is a binary tree T = (V, E) together with a (weight) function ω : V → S , with (S , ≤) a totally ordered set,
such that for any x ∈ V:

• ω(y) ≤ ω(x) for any y ∈ L(x),

• ω(x) ≤ ω(y) for any y ∈ R(x),

31
where L(x) and R(x) are the left and and the right subtree defined below x. The values at the vertices, namely
{ω(x) ∈ S | x ∈ V}, are called the keys.
Two examples of binary search trees are presented in Figure 3.15. Let us emphasize that binary search trees do
not consist only in the values of the keys: the structure of the tree and accordingly the position of each vertex
is important. For example, even though the two binary search trees of Figure 3.15 contain the same keys,
they are very different and exhibit different responses to a research algorithm. It takes only four comparisons
to determine that the number 20 is not one of the key stored in the left tree of Figure 3.15, while the same
conclusion is obtained only after nine comparisons in the right tree.

Figure 3.15: Two binary search trees, see Figure 3.4.1 of [GYA]

In practice, BST have a better behaviour if the two subtrees at each vertex contain roughly the same number
of vertices. In such a case, we say that the binary tree is balanced.
It is easily observed that the smallest key in a BST is always stored in the most left vertex. This can be found
starting from the root and proceeding always to the left until one reaches a vertex with no left-child. Similarly,
the largest value is always attached to the most right vertex. This vertex can be found starting from the root
and proceeding always to the right until a vertex with no right-child is reached.
More generally, the vertex corresponding to a certain key can be found by a simple iteration process, excluding
always either a left subtree or a right subtree from the rest of the search. For a balanced tree containing n
vertices, such a search requires an average of O ln(n) operations2 . Indeed, for a balanced tree, the relation


between the height h of the tree and the number n is of the form 2h  n, which means that a leaf can be reached
in about log2 (n) steps.
Two other primary operations can be performed on BST, namely the insert operation and the delete operation.
The first one consists in adding a vertex corresponding to a prescribed new key by first looking at the right
position for this new vertex. The second operation consists in eliminating a vertex but keeping the structure
of a BST. These operations can be studied as an exercise.

3.4.3 Huffman trees

In this section we discuss the use of binary trees for creating efficient binary codes.
2
For a strictly positive function ζ, the notation f ∈ O ζ(n) means that f (n)
≤ c for some c < ∞ and all n, while f ∈ o ζ(n) means



ζ(n)
limn→∞ f (n)
ζ(n)
= 0. These notations give us an indication about the growth property of the function f without looking at the details.

32
Definition 3.17 (Binary code). A binary code is a bijective map between a finite set of symbols (or alphabet)
and a set of finite sequences made of 0 and 1. Each sequence is called a bit string or codeword.
In this definition, the set of symbols can be arbitrary, like a set of letters, a set of words, a set of mathematical
symbols, and so on. Also, the finite sequences of 0 and 1 can either be all of the same length, or have a variable
length. In the latter case, it is important that a given sequence does not correspond to the first part of another
sequence. In that respect, the following definition is useful:
Definition 3.18 (Prefix code). A prefix code is a binary code with the property that no bit string is the intial
part of any other bit string.
It is quite clear that an ordered tree can be associated with any binary code. For this, it is sufficient to associate
the value 0 to the edge linking a father to the left child (if any), and a value 1 to the edge linking a father to the
right child (if any). In such a construction, the difference between a binary code and a prefix code is clearly
visible: in the former case a symbol can be associated to any vertex, while in the latter case a symbol is only
associated to leaves, see Figure 3.16.

Figure 3.16: Trees of a binary code and of a prefix code

The code ASCII is a binary code in which each bit string has a fixed length. On the other hand, the example
presented in Figure 3.17 corresponds to a prefix code together with the associated binary tree.

Figure 3.17: A prefix code and the corresponding tree, see Figure 3.5.1 of [GYA]

For some applications it would be be quite natural to use short codewords for symbols which appear frequently.

33
For example, in a prefix code for an English text, one would like to associate a short bit string to the letter e
which appears quite often, and accept a longer bit string for a letter which is much more rare. One efficient way
to realize such a prefix code is to use the Huffman code. It is based on one additional information associated
with any symbol: its frequency or its weight. The following definition is based on the notion of weighted
length for weighted graphs already introduced in Definition 1.28. We shall also use the information about the
height or depth of a vertex, as introduced in Definition 3.7. Recall that the depth corresponds to the length
d(r, x) of the path between the root r and a vertex x. In the present setting, this length is also equal to the
number of elements of the codeword associated to a vertex.
Definition 3.19 (Weighted depth). Let T be a tree with leaves {x1 , x2 , . . . , xn }, and let {ωi }ni=1 ⊂ [0, ∞) be
weights associated with the leaves. Then the weighted depth ω(T ) of the tree is defined by
n
X
ω(T ) := ωi d(r, xi ).
i=1

Figure 3.18: Huffman algorithm, from Algorithm 3.5.1 of [GYA]

Note that if the weight ωi associated to a leaf xi is related to the frequency of the letter si corresponding to that
leaf, and if i ωi = 1, then the weighted depth provides an information about the length of the transcription
P
of the text with this prefix code: the weighted depth corresponds to the average length of the bit strings used
for the transcription.
Now, given a list of symbols S := {s1 , s2 , . . . , sl } and a list of weights {ω1 , ω2 , . . . , ωl }, the Huffman algorithm
corresponds to constructing a tree T which minimizes the weighted depth ω(T ). Note however that the solution
is not unique, and the lack of unicity appears rather clearly in the algorithm presented in Figure 3.18. The
resulting tree is called a Huffman tree and the resulting prefix code is called a Huffman code. Clearly, these
outcomes depend on the given weights. An example of such a construction is provided in Figure 3.19. Let us
finally mention the result which motivates the construction presented above:
Theorem 3.20 (Huffman’s theorem). Given a list of weights {ω1 , ω2 , . . . , ωl }, the Huffman algorithm pre-
sented in Figure 3.18 generates an binary tree T which minimizes the weighted depth ω(T ) among all binary
trees.

34
 Figure 3.19: Application of Huffman algorithm, from Example 3.5.3 of [GYA]

3.4.4 Priority trees

Let us present one more application of binary trees. First of all, we introduce some ideas more related to
computer science.
Definition 3.21 (Abstract data type). An abstract data type is a set of objects together with some operations
acting on these objects.
Two such objects are quite common: 1) A queue, which is a set of objects that are maintained in a sequence
which can be modified by the addition of new objects (enqueue) at one end of the sequence and the removal of
objects (dequeue) from the other end of the sequence. A queue is also called FIFO (First In, First Out), and a

35
representation of a queue is provided in Figure 3.20a. 2) A stack, which is a set of objects that are maintained
in a sequence which can be modified by the addition of new object on the top of the sequence (push operation)
or removed also on the top of the sequence (pop operation). A stack is also called LIFO (Last In, First out),
and a representation of a stack is provided in Figure 3.20b.

(a) A queue (b) A stack

Figure 3.20: Two standard abstract data types

We now generalize these two examples.

Definition 3.22 (Priority queue). A priority queue is a set of objects, each of which is assigned a priority,
namely an element of a totally ordered set. The operation of addition (enqueue) consists simply in adding one
more object together with its priority to the set, while the operation of removal (dequeue) consists always in
removing the object with the largest priority. If two objects share the largest priority, an additional selection
rule has to be prescribed.
Note that the queue and the stack already mentioned as special instances of priority queues. In the former
one, the lowest priority is always given to the newest object, while in the latter the largest priority is always
given to the newest object. One can always represent a priority queue in a linked list, with the links sorted
by decreasing priorities. Note that a linked list is also an abstract data type consisting in a set of objects,
where each object points to the next in the set, see Figure 3.21. However, a better suited and more efficient
implementation of a priority queue can be obtained with priority trees, as introduced below. A priority tree
corresponds in fact to the most natural representation of a priority queue.

Figure 3.21: A linked list, with a terminal object (terminator) represented by a box

For priority trees, recall first that complete p-ary trees were introduced in Definition 3.8. We now weaken a
little bit the completeness requirement.
Definition 3.23 (Left-completeness). A binary tree of height h is called left-complete if the following condi-
tions are satisfied:
(i) Every vertex of depth h − 2 or less has two children,
(ii) There is at most one vertex at depth h − 1 that has only one child (a left-one)
(iii) No vertex at depth h − 1 has fewer children than another vertex at depth h − 1 to its right.

36
An example of a left-complete binary tree of height 3 is pre-
sented in Figure 3.22. In the sequel we shall endow the ver-
tices of such a tree with one additional information. However,
in order to keep the greatest generality, let us first introduce a
notion slightly weaker than the totally ordered set already men-
tioned. A partially ordered set S consists in a set S with a
binary operation ≤ satisfying the following three conditions for
any a, b, c ∈ S :
(i) Reflexivity: a ≤ a, Figure 3.22: A left-complete binay tree
(ii) Antisymmetry: If a ≤ b and b ≤ a, then a = b,
(iii) Transitivity: If a ≤ b and b ≤ c, then a ≤ c.
Clearly, a totally ordered set is also a partially ordered set, but the converse is not true. The main difference
with a totally ordered set is that some elements a and b, the relations a ≤ b and b ≤ a could both be wrong. In
such a case, we say that a and b are not comparable. An example of partially ordered set is provided by the
set of all subsets of R with A ≤ B if A ⊂ B, for any subsets A and B of R. For example, with intervals one has
(1, 2) ≤ (0, 4), but (0, 4) and (1, 5) are not comparable.
We can now introduce a general definition of priority trees:
Definition 3.24 (Priority tree). A priority tree is a left-complete binary tree T = (V, E) together with a map
ω : V → S , with (S , ≤) a partially ordered set, such that for any x ∈ V and any child y of x one has
ω(y) ≤ ω(x). The value of S are called the priorities.
Binary search trees (BST), also called ordered or sorted binary trees is a binary tree T = (V, E) together with
a (weight) function ω : V → S , with (S , ≤) a totally ordered set, such that for any x ∈ V:
• ω(y) ≤ ω(x) for any y ∈ L(x),
• ω(x) ≤ ω(y) for any y ∈ R(x),

(a) The alphabetical total ordering (b) The inclusion partial ordering

Figure 3.23: Two examples of priority trees

Two examples of priority trees are presented in Figure 3.23. Note that Figure 3.23a is based on a totally
ordered set, while Figure 3.23b is based on a partially ordered set. Note also that even though a vertex can
not have a larger priority than its parent, it can have a larger priority than a sibling of its parent. From the
definition, the piorities of a parent and of a child are always comparable, but the priorities of two siblings, or
of elements which are further away, do not need to be comparable.

37
By comparing the definition of priority queue and of priority trees, it is quite clear that a priority queue can be
represented in a priority tree. In fact, only special intances of priority trees are used for representing priority
queues: the ones for which the priorities are chosen in a totally ordered sets3 .
When a priority queue is represented by a priority tree, the dequeue operation consists simply in extracting
the root of the tree, but how can one obtain again a priority tree ? In fact, the removal and the addition of
any element in a priority tree can be implemented by the following algorithms. The insertion of an arbitrary
element in a priority tree can be implemented by the algorithm Priority tree insert presented in Figure 3.24.
An example is provided in Figure 3.25.

Figure 3.24: Priority tree insert, from algorithm 3.6.1 of [GYA]

Figure 3.25: The insertion of 13 in the priority tree, see Figure 3.6.3 of [GYA]
The removal of an arbitrary element of a priority tree (as for example the root) can be implemented by the
algorithm Priority tree delete presented in Figure 3.26. An example is provided in Figure 3.27.

3.5 Counting trees

Let us conclude this chapter with a question related to combinatorics: how many binary trees of n vertices can
one construct ? For this question one has to remember that binary trees are ordered 2-ary trees (which implies
that they are rooted). Clearly, if n = 1, there is only one such tree. If n = 2, two solutions exist: a root with
a left child, or a root with a right child. The solutions for n = 3 are presented in Figure 3.28, but what about
bigger n ?
3
A more general notion of priority queue with a partially ordered set is possible, but the corresponding operations are not well
defined, or not really natural.

38
 Figure 3.26: Priority tree delete, from algorithm 3.6.2 of [GYA]

Figure 3.27: The deletion of 21 in the priority tree, see Figure 3.6.4 of [GYA]

One approach is by recursion. Let Cn denote the

number of such binary trees of n vertices. As shown
above, C1 = 1, C2 = 2 and C3 = 5. Now, given
the root of a tree containing n vertices, this root has
a left subtree and a right subtree. If the left subtree
contains j vertices (with 0 ≤ j ≤ n − 1) then the
right subtree contains n − j − 1 vertices. In such a Figure 3.28: Rooted ordered trees with 3 vertices
case, there exists C j possible binary subtrees for the
left subtree, and Cn− j−1 subtrees for the right subtree,
making a total of C jCn− j−1 possible and different trees. Note that this formula holds if we fix by convention
that C0 = 1. Since j can vary between 0 and n − 1 and since the solutions obtained for different j are all
different, one obtains the recurrence relation

Cn = C0Cn−1 + C1Cn−2 + C2Cn−3 + . . . Cn−2C1 + Cn−1C0 .

This relation can also be written more concisely:

n−1
X
Cn = C jCn− j−1
j=0

39
and is called the Catalan recursion. Then numbers Cn are known as the Catalan numbers, and appear in
various counting problems, see [10]. A closed formula exists for the computation of these numbers, In fact
one has !
1 2n
Cn = ,
n+1 n
!
2n
where denote a binomial coefficient. Several proofs of this result are presented in [10].
n
Another formula which will appear later on is the so-called Cayley’s formula. This formula counts the number
of non-isomorphic trees with n labeled vertices. These labels can be identified with a different weight assigned
to each vertex, see Section 1.4 for the definition of weighted graphs. For weighted graphs, any isomorphism
has to respect the weights, which means that the functions ( fV , fE ), from the weighted graph G = (V, E, ω) to
the weighted graph G′ = (V ′ , E ′ , ω′ ), introduced in Definition 2.8 have to satisfy for any x ∈ V and e ∈ E

ω′ fV (x) = ω(x) ω′ fE (e) = ω(e).

and

Obviously, if only the vertices (or the edges) are endowed with weights, only one of these conditions has to
be satisfied.

Figure 3.29: Trees with 2, 3 and 4 labeled vertices, see [11]

In Figure 3.29 labels on vertices are indicated by colors, and only trees are considered. All non isomorphic
trees of 2, 3 and 4 labeled vertices are presented. Calyley’s formula states that for n labeled vertices, the
number of non-isomorphic trees is nn−2 . Several proofs are indicated on [11], and one is fully presented in
[GYA, Sec. 3.7].

40
Chapter 4

Spanning trees

In this chapter we study spanning trees and their construction. These trees have many applications, and nice
mathematical properties .,

4.1 Growing trees

Before stating the main definition of this section, let us recall that an arborescence is a directed rooted tree
with all edges pointing away from the root. As a consequence, there exists a unique (oriented) path from the
root to any vertex of the arborescence.

Definition 4.1 (Spanning tree). Let G be a connected graph. A spanning tree T of G is a subgraph of G which
is either an unoriented tree or an arborescence which includes every vertex of G.

A spanning tree T is a subgraph which induces or spans G, as introduced in Definition 1.6. For undirected
graphs, a spanning tree can also be defined as a maximal set of edges of G that contains no cycle, or as a
minimal set of edges that connect all vertices. Note that usually one fixes a root for the tree, but it is not
strictly necessary. It is rather clear that for undirected connected graphs, a spanning tree always exists (and
often it is non unique). On the other hand, for directed graphs, the requirement that the spanning tree is also
an arborescence makes its existence less likely, but it is only with this additional property that spanning trees
are useful for directed graphs, see Figure 4.1.

(a) An unoriented tree (b) An arborescence

Figure 4.1: Two spanning trees with root r

41
Our next aim is to construct such spanning trees. There exists several algorithms, but they all rely on a few
definitions which are introduced now.
Definition 4.2 (Tree edge, vertex edge, frontier edge). Let G be a connected graph, and T be a subgraph of
G which is a tree.
(i) A tree edge or a tree vertex is an edge or a vertex of G which belongs to T . A non-tree edge or a non-tree
vertex is an edge or a vertex of G which does not belong to T .
(ii) A frontier edge is an non-tree edge with one endpoint in T (called tree endpoint) and the other not in T
(called non-tree endpoint). If G is directed, the non-tree endpoint has to correspond the target. The set
of all frontier edges if denoted by Front(G, T ).
The frontier edges Front(G, T ) of an undirected graph is represented in Figure 4.2. For directed graph, a
frontier edge is also called a frontier arc and the requirement is that the edge points outside of the tree. The
general role of frontier edges is to be added to the existing tree (or arborescence in case of directed graphs)
and to make these structures grow, as easily shown with the following lemma.

Figure 4.2: A graph, a tree, and the frontier edges as dashed lines

Lemma 4.3. Let G be a connected graph, and T be a subgraph of G which is an unoriented tree or an
arborescence. The addition of a frontier edge eto T generates a new subgraph of G which is an unoriented
tree or an arborescence. This new tree is denoted by T ⊔ {e}.
Given an oriented tree or an arborescence in G, one natural question is about the choice of a frontier edge.
Indeed, there often exist several edges which are frontier edges, how can one choose a particular one and
based on which criteria ? Each criterion (selection rule) corresponds in fact to a different algorithm. Note that
choosing one element inside the set of all frontier edges can be either a deterministic operation or a random
operation. Note also that once a frontier edge has been chosen, this set has to be updated. Indeed, at least
this frontier edge has to be removed from the list, but possibly other frontier edges have to be removed, and
new frontier edges might become available. Thus, growing an unoriented tree or an arborescence inside a
connected graph G always consists in a series of several operations:
Algorithm 4.4 (Grow a tree).
(i) Fix an initial vertex x0 of G, set T 0 := {x0 } and fix i := 0,

42
 (ii) Choose one element ei+1 of Front(G, T i ), set T i+1 = T i ⊔ {ei+1 }, and set i := i + 1,
(iii) Repeat (ii) until Front(G, T i ) = Ø.
Let us make a few observations about this algorithm. The trivial initial tree
in indeed just defined by a vertex, while at each subsequent step only the
additional edge is mentioned. These information uniquely determine the
tree. As mentioned before the choice of ei+1 ∈ Front(G, T i ) will be deter-
mined by a prescribed procedure, and we shall see several subsequently.
For an undirected finite graph, the algorithm will stop once a spanning tree
has been obtained. For an arbitrary directed graph, this is much less clear,
and the process might stop much before a spanning tree is obtained. The
success of obtaining a spanning tree in this case will highly depend on
the choice of the initial vertex (the root) and of the structure of the directed
graph G. For example, in Figure 4.3 it is possible to create an arborescence
starting from the vertex a but not from the vertex b. On the other hand, if
a graph (directed or undirected) contains an infinite number of vertices,
the algorithm might never end. Note finally that even if Front(G, T i+1 ) is Figure 4.3: A digraph
different from Front(G, T i ), it might not be necessary to compute this set
from scratch but some information can be inferred from Front(G, T i ).
Remark 4.5 (Discovery number). In the point (ii) of the above algorithm, we have written “Choose one
element ei+1 of Front(G, T i ), set T i+1 = T i ⊔ {ei+1 }” and not simply “Choose one element e of Front(G, T i ), set
T i+1 = T i ⊔ {e}” which would have been sufficient. The interest in the first notation is that it keeps an ordering
in the growth of the tree. In fact, this ordering is called the discovery number and can be associated uniquely
to each edge or to each vertex of the tree. For the edge, the discovery number of ei is simply i, while for the
vertices, we set xi for the non-tree endpoint of the edge ei (before this endpoint becomes also part of the tree).
The function associating its discovery number to any vertex of the tree is often called the dfnumber-function.
The discovery number also endows the tree with the structure of an ordered tree, see Figures 4.4a and 4.4b.
With this notation, one can write precisely T i = (Vi , Ei ) with Vi = {x0 , x1 , . . . , xi } and Ei = {e1 , e2 , . . . , ei }.

(a) A graph with a spanning tree (b) The corresponding ordered tree

Figure 4.4: A graph, a spanning tree, and the resulting ordered tree

Let us now suppose that the process of growing a tree has ended up in a spanning tree. Except if the graph G
itself was a tree, otherwise some edges of G do not belong to the tree, they are non-tree edges. These edges

43
can be divided into two sets: the skip-edges and the cross-edges. Skip-edges link two vertices which are in
the same “family”, one being an ancestor of the other one, while cross-edges link two vertices which are not
in the same “family”, none being an ancestor of the other one. Note that for skip-edges in directed graphs,
one speaks about back-edge or back-arc if the target of the edge is the ancestor while it is a forward-edge or
forward-arc if the tail of the edge is the ancestor. Cross-edges of directed graphs can also be separated into
two subclasses, those linking a vertex with a discovery number to a vertex with a larger one, and those linking
a vertex with a discovery number to a vertex with a smaller one. Note that loops have not been considered in
this classification and should be considered as a family in itself.
As final note, let us observe that only connected graphs have been considered in this section. Clearly, the
process of growing a free will not be able to visit more than one component of a graphs made of several
components. However, it is not difficult to extend the construction and develop the growth of a forest. The
missing necessary step is to allow the start of a new tree in a component different from the initial one. By
iterating this procedure, one ends up with a forest and can define a spanning forest.

4.2 Depth-first and breadth-first search

We present here two classical solutions for choosing the element of Front(G, T i ) in the part (ii) of Algorithm
4.4.
The main idea of Depth-first search (DFS) is to start at the root node and explores as far as possible along
each branch before backtracking. For that purpose, the frontier edge ei+1 ∈ Front(G, T i ) is chosen with a tree
endpoint at x j with the largest number j (starting from i and then backward). Whenever more than one edge
satisfy this condition (one speaks about ties) a priority rule has to be imposed. This priority can be either
random, or based on some a priori information. For example, if indices had been attributed to edges or to
vertices, they can be used to implementing an additional selection rule. Such a rule is called a default priority.
One tree constructed with the depth-first search will naturally be called a depth-first search tree. Usually,
such a tree is not unique, and it is surely not unique if two edges in Front(G, T i ) had their tree endpoint at xi .
However, one easy property of depth-first search trees is provided in the next statement. Its proof can either
be found in [GYA, Prop. 4.2.1] or by a minute of thought.
Lemma 4.6. For an undirected graph, any depth-first search tree has no cross-edges.
Let us add two remarks which link the depth-first
search to two already introduced concepts. Firstly,
by using a slightly extended version of the pre-order
traversal as introduced in Definition 3.14 on a depth-
first search tree one reproduces the discovery order
of the edges in the original graph, see Figure 4.5.
Note that the mentioned extension corresponds to
an extension of the pre-order traversal to general or-
dered trees, and not only to binary trees. Secondly,
when the growth of a tree is implemented, the natural Figure 4.5: A DFS tree
way to store the frontier edges is to to use a priority
queue, see Definition 3.22. However, for depth-first search tree the structure of a stack is sufficient. Indeed,
the newest frontier edges are given the highest priority by being pushed onto the stack (in increasing default
priority order, if there is more than one new frontier edge). The recursive aspect of depth-first search also
suggests the feasibility of implementation as a stack, see Figure 3.20b and Figure 4.6.

44
 Figure 4.6: A growing DFS tree with Front(G, T i ) in dashed lines

Let us now move to Breadth-first search (BFS). This time, the main idea is to start at the tree root and explores
all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level. For that
purpose, the frontier edge ei+1 ∈ Front(G, T i ) is chosen with a tree endpoint at x j with the minimal number j
(starting from j = 0 and then upward). Again, whenever more than one edge satisfy this condition a default
priority is used.
One tree constructed with the breadth-first search
will naturally be called a breadth-first search tree.
Usually, such a tree is not unique, and it is surely
not unique if two edges in Front(G, T i ) shared the
same tree endpoint. This time, by using a slightly
extended version of the level-order traversal as in-
troduced in Definition 3.14 on a breadth-first search
tree one reproduces the discovery order of the edges Figure 4.7: A BSF tree
in the original graph, see Figure 4.7. Note that the
mentioned extension corresponds to an extension of the level-order traversal to general ordered trees, and not
only to binary trees. Additional properties of breadth-first search trees are provided in the next statement. The
proof can either be found in [GYA, Sec. 4.2] or by a minute of thought. We recall that the level of a vertex in a
tree has been introduced in Definition 3.7 and that the dfnumber-function has been introduced in Remark 4.5.
Lemma 4.7.
(i) Let x, y be two vertices in a breadth-first search tree, then the property level(y) > level(x) implies
dfnumber(y) > dfnumber(x),
(ii) Any breadth-first search tree provides the shortest path tree (a spanning tree) of an unoriented graph
with a given root, see the definition at the end of Section 3.2.
The appropriate data structure to store the frontier edges in a breadth-first search is a queue, since the frontier
edges that are oldest have the highest priority, see Figure 4.8.
A comparison between a DFS tree and a BFS tree is provided in Figure 4.9. Starting from the vertex v, it
represents the trees obtained after eleven iterations of the Algorithm 4.4.

4.3 Applications of DFS

In this section we present some applications of depth-first search to connected and finite graphs. Extensions
to non-connected ones can be done by considering the components separately.

45
 Figure 4.8: A growing BFS tree with Front(G, T i ) in dashed lines

Figure 4.9: A DFS tree and a BFS tree after 11 iterations, see also Figure 4.2.2 of [GYA]

Let us recall that in Algorithm 4.4 the central idea of depth-first search is to look for an edge ei+1 ∈ Front(G, T i )
with a tree endpoint at x j with the largest number j (at most i). The following definition is related to this quest.
Definition 4.8 (Finished vertex). In a depth-first search, a discovered vertex is finished when all its neighbours
have been discovered and those with higher discovery number are all finished.
An example of a depth-first search is provided in Figure 4.10. Since the graph is simple, the name of each
edge is indicated by the name of its two endpoints (xy means the edge between the vertices x and y). The
column “nextEdge” corresponds of the edge which has been chosen among the frontier edges.
As mentioned in the previous section, a natural generalization of the pre-order traversal applied to a DFS tree
provides the discovery order of the edges inside the original graph. Similarly, a slightly extended version
of the post-order traversal, also introduced in Definition 3.14, applied to a DFS tree provide the list of the
finished vertices, in the order they appear during the search. This property can be illustrated for example with
Figure 4.5.
Usually, a depth-first search generates a walk since one has to backtrack several times in the construction of a
spanning tree. In that respect, the following definition is natural.
Definition 4.9 (DFS-path). A DFS-path is a path produced by executing a depth-first search and by stopping
the iteration right before one backtracks for the first time.
Let us consider G undirected, and let x denote the endpoint of a DFS-path. Clearly, this path is also a tree, and

46
 Figure 4.10: 4 iterations of a depth-first search, see also Example 4.4.1 of [GYA]

the vertex x is finished. One easily observes that all neighbours of x belong to the path, since otherwise the
path could be extended. The following statement can then be easily deduced from this simple observation.
Lemma 4.10. Let G be an undirected graph, and let x denote the endpoint of a DFS-path. Then either
deg(x) = 1, or x and all its neighbours belong to a cycle of G.

Proof. The case deg(x) = 1 is clear. Suppose now that deg(x) ≥ 2, and let y be a neighbour of x with the
smallest value dfnumber among all neighbours of x. By the previous observation all neighbours of x are
contained on the path between y and x. Since y is also a neighbour of x it means that there is a non-tree edge,
see Definition 4.2, which links x to y. Thus, all neighbours of x are on a cycle, as claimed. □

Quite pleasantly, this result directly provides a proof to the statement (i) of Theorem 1.26. Namely, if G is a
simple and undirected finite graph with minimum degree δ(G) ≥ 2, it contains a cycle of length at least equal
to δ(G) + 1. Clearly, if δ(G) ≤ 1, then the statement is not true but nevertheless the graph contains a path of
length δ(G), as claimed in the statement of the theorem.
Let us now use the depth-first search for finding cut-edge (bridge) as introduced in Definition 2.20. Observe
firstly that in an undirected and connected graph, an edge is a bridge if and only if it does not belong to any
cycle in a graph, see also [GYA, Corol. 2.4.2]. Whenever a graph has some bridge(s), the following definition
is natural.
Definition 4.11 (Bridge component). Let G be a connected graph, and let B be the set of all its bridges. A
bridge component of G is a component of the graph G − B.
It clearly follows from this definition and from the previous observation that the edges and the vertices of
any cycle in a connected graph belong to the same bridge component. Let us go one step further in the
construction.

47
Definition 4.12 (Contraction). Let H = (VH , E H ) be a connected subgraph of a graph G = (V, E). The
contraction of H to a vertex is the replacement of VH by a single vertex k. Any edge between a vertex of VH
and a vertex of V \ VH is replaced by an edge between k and the same element of V \ VH , while all edges of
E H do not appear in the contraction.

Figure 4.11 provides an illustration of a contraction of three vertices.

Figure 4.11: Contraction of VH = {a, b, c} into the vertex k

As a result of these definitions and observations, one easily deduces the following important result:

Proposition 4.13. Let G be a connected and undirected graph. The graph that results from contracting each
bridge component of G to a vertex is a tree.

Figure 4.12 corresponds to the content of this proposition.

Figure 4.12: Before and after contracting each bridge component of G

Before stating the algorithm which allows us to identify the bridges of a graph, let us still observe that if x is
a vertex of a connected graph G with deg(x) = 1, then the bridge components of G is made of the component
consisting on x only, and on the bridge components of G − {x}. The algorithm for determining cut-edges is
presented below. Note that it has been developed for undirected graphs, and this assumption should be added
at the beginning of the statement.

Let us emphasize that the bridges are important because they correspond to the “weaknesses” of a graph. By
removing them, a connected graph becomes disconnected. Note that a similar procedure exists for cut-vertices,
as introduced in Definition 2.19. The construction is of the same type and can be studied independently. We
refer to [GYA, p. 196–200] for more information.

48
 Figure 4.13: How to find bridges, from algorithm 4.4.1 of [GYA]

4.4 Spanning tree with mimimum total edge-weight

In this section we refine the algorithm presented in Section 4.1 when a weighted connected graph is considered,
see Definition 1.27. Note that weights will be attached only to edges and not to vertices, which means that we
consider only edge-weights and accordingly edges-weighted graphs. Our aim is to construct a spanning tree
with the minimum total edge-weight, the so-called minimum spanning tree problem. Since for a graph with n
vertices, there could exist up to nn−2 trees, see Section 3.5, one is forced to look for an efficient algorithm.

The main idea for growing a tree with minimum total edge-weight is
to use Algorithm 4.4 and to choose at each step (ii) the edge ei+1 ∈
Front(G, T i ) with the smallest edge-weight. If there is more than one edge
in Front(G, T i ) with the smallest edge-weight, then the default priority can
choose one of them. Note that this procedure is referred to as Prim’s al-
gorithm, since it has been proposed by R.C. Prim in 1957. It remains then
to show that this procedure leads for undirected graphs to a spanning tree
with minimum total edge-weight. This can be done by an inductive proof
as presented for example in [GYA, Prop. 4.3.1]. Figure 4.14 provides the
example of an edges-weighted graph with a minimum spanning tree.

Let us mention that a generalization of the this problem consists in pre- Figure 4.14: A minimum span-
scribing only a subset of vertices. More precisely, let G = (V, E, ω) be a ning tree
connected edge-weighted graph, and let U ⊂ V. The Steiner-tree problem
consists in finding a minimum total weight tree in G containing all vertices of U. Clearly, the special case
U = V corresponds to the minimum spanning tree problem. The Steiner-tree problem has been extensively
studied, see [12]. A special instance of this problem consists in considering only two prescribed vertices in
the graph (the set U contains only two elements). We now develop this situation.

For solving this problem, recall that the weighted length of a walk has been introduced in Definition 1.28. It
corresponds to the sum of the weight on the corresponding edges, and if W denotes a walk in the graph, we
write ω(W) for its weighted length. Accordingly, if x, y are vertices of a weighted graph, it would be natural

49
to define
dω (x, y) = min ω(W) | W is a walk from x to y .


However, this notion suffers from two weaknesses. The first one has already been observed: there might be
no walk between x and y, in which case we set dω (x, y) = ∞. The second problem is more serious: if the
graph contains cycles with negative length, then most of the distances would be equal to −∞. In order to avoid
this situation, the minimal requirement is to impose that the graph has no such cycle of negative length. One
stronger requirement is to impose that all weights belong to [0, ∞). Note that if we further impose ω(e) > 0
for any edge e and if the graph is undirected, then the distance dω defined above endows the weighted graph
G = (V, E, ω) with a metric4 . If the graph is directed and/or if the weight is not strictly positive, dω does
not correspond to a metric in general. Note finally that in the general setting, this “distance” might represent
various quantities.
From now on, let us assume for simplicity that ω(e) ≥ 0, but mention that an extension with the only require-
ment of the absence of cycles of negative length exists (Floyd–Warshall algorithm). As an easy consequence,
one always has dω (x, x) = 0 for any x ∈ G. In the sequel we construct more than just the weighted path from a
prescribed x0 to a prescribed y with the minimum weight, we construct such a path from x0 to any vertex y in
the graph. In fact, we construct a tree with root x0 , and the minimum weighted path from x0 to any y is then
uniquely defined by the tree. This tree is called a Dijkstra tree, since it has been proposed by E. Dijkstra in
1959. The construction is again based on Algorithm 4.4 with a clever choice of ei+1 ∈ Front(G, T i ). However,
since an additional information has to be kept during the process, we provide below the updated version of
the algorithm.
Before this, let us adapt an already old concept. Since the edges in Front(G, T i ) have a tree endpoint and
a non-tree endpoint, it is rather natural to use the origin map o : E → V and the target map t : E → V
already introduced in Section 1.1. With this notation o(e) will denote the tree endpoint, while t(e) corresponds
to the non-tree endpoint. Note that in the present framework this notation is natural both for oriented and
non-oriented edges.
Algorithm 4.14 (Dijkstra’s tree algorithm).
(i) Fix an initial vertex x0 of G, set T 0 := {x0 } and fix i := 0,
(ii) Choose the element ei+1 ∈ Front(G, T i ) which satisfies
 
dω x0 , t(ei+1 ) := dω x0 , o(e) + ω(e) .



min (4.4.1)
e∈Front(G,T i )

Set T i+1 = T i ⊔ {ei+1 }, and set i := i + 1,

(iii) Repeat (ii) until Front(G, T i ) = Ø.
Note that if more than one edge satisfies condition (4.4.1), then the default priority is applied. Note also that
this algorithm is well defined, since dω x0 , o(e) always corresponds to dω (x0 , x j ) for some j ∈ {0, 1, . . . , i}.


This comes from the fact that for any e ∈ Front(G, T i ) one has o(e) = x j for some j ∈ {0, 1, . . . , i}. It is clear
that the implementation of this algorithm requires that the value dω (x0 , xi+1 ) has to be kept in memory each
time the new edge ei+1 is chosen. There exists several practical implementations of this algorithm, but we do
not develop this any further. The correctedness of this algorithm can be proved by induction over the trees.
One version is provided in [GYA, Thm. 4.3.3]. Alternatively, there are plenty of well documented websites
on Dijkstra’s tree algorithm over the internet, see also [13]. Note finally that Dijkstra’s algorithm has been
4
Recall that a metric is a map d : V × V → [0, ∞) satisfying the three conditions: 1. d(x, y) = 0 ⇔ x = y, 2. d(x, y) = d(y, x), and
3. d(x, y) ≤ d(x, z) + d(z, y) for any x, y, z ∈ V.

50
developed in several directions. For example, one could compute simultaneously the minimum weighted paths
from any x to any y, and not only from a fixed x to any y.
An example of the Dijkstra’s algorithm is presented in Figure 4.15. The edge-weights are indicated above
the edges, while the yellow disks contain an information about the distance from the root (upper-left vertex)
to the corresponding vertex: Once the vertex is visited, it corresponds to dω (x0 , xi ) and before it is visited it
corresponds to a preliminary result when a comparison of the type (4.4.1) is computed (preliminary distance).
This preliminary distance can only decrease, or stay constant if no path with a smaller weighted length is
discovered inside the graph. For that reason, these preliminary distances are often set to ∞ before the start
of the algorithm. At each step in the algorithm, one updates some of these values only if a smaller weighted
length is found.

Figure 4.15: Application of Dijkstra’s algorithm, from [14]

51
Chapter 5

Connectivity

Connectivity is an important concept in graph theory. Graphs with a dense connectivity or with a very weak
connectivity do not present the same vulnerability towards the removal of some vertices or edges. Beside the
notions of vertex-cut or edge-cut, and cut-vertex (=cutpoint) or cut-edge (=bridge) provided in Definitions
2.19 and 2.20, more refined concepts have to be introduced. Also, since loops do not play any role for the
connectivity of a graph, the graphs considered in this chapter will be loopless.

5.1 Vertex and edge connectivity

Let us start by providing a concept measuring the density of connectivity in a graph. For clarity, recall that
an operation disconnects a connected graph if after this operation the graph is no more connected. Let us
however acknowledge that the notion of connectivity does not fit well with the notion of orientation. In
fact, for digraphs more refined concepts are necessary, and will be introduced in subsequent chapters. As a
consequence, the main statement of this section, namely Theorem 5.4, is applicable to unoriented graphs only.
Its statement would be wrong for oriented graphs.
Definition 5.1 (vertex or edge connectivity). Let G be a connected graph.
(i) The vertex connectivity κV (G) of G is the minimum number of vertices whose removal can either dis-
connect G or reduce it to a 1-vertex graph.
(ii) The edge connectivity κE (G) of G is the minimum number of edges whose removal can disconnect G.
Note that the minimum degree δ(G) already introduced in Section 1.1 must satisfy κE (G) ≤ δ(G) (otherwise,
one easily gets a contradiction). In fact, the two connectivities are not independent, one has

κV (G) ≤ κE (G) ≤ δ(G). (5.1.1)

The proof is left as an exercise. Now, in relation with these definitions one also sets:
Definition 5.2 (k-connectedness). Let G be a connected graph, and let k ∈ N.
(i) The graph G is k-vertex connected (or simply k-connected) if κV (G) ≥ k,
(ii) The graph G is k-edge connected if κE (G) ≥ k,

52
These notions are useful for discussing any network survivabil-
ity, which is the capacity of a network to stay connected after
some edges or vertices are removed. For example, if the ver-
tices of the graph are divided into two subsets V1 and V2 , then
the number of edges between V1 and V2 is always greater or
equal to κE (G). An example of vertex connectivity and edge
connectivity is provided in Figure 5.1.

Recall that internal vertices of a tree have been introduced in

Definition 3.7. For a path which is not a cycle, the internal ver-
Figure 5.1: κV (G) = 2 and κE (G) = 3
tices correspond to all vertices of the path except its two end-
points. In order to discuss the vulnerability of a network, the
following definition is useful:

Definition 5.3 (Internally disjoint paths). Let x, y be distinct vertices in a graph G. A family of paths from x
to y is said to be internally disjoint if no two paths in the family have an internal vertex in common.

A representation of two such path is provided in Figure 5.2.

Already in 1932, H. Whitney provided a characterization of 2-
connected graphs in terms of internally disjoint paths, namely:
Any connected and unoriented graph with at least 3 vertices is
2-connected if and only if each pair of vertices in G admit two
internally disjoint paths between them. There are several proofs
of this Whitney’s 2-connected characterization available on In-
ternet. In fact, a more general characterization of 2-connected Figure 5.2: 2 internally disjoint paths
graphs can obtained, see also Figure 5.3. Its proof can be done
as an exercise.

Theorem 5.4. Let G be a connected, unoriented and finite graph with at least 3 vertices. The following
statements are equivalent:

(i) G is 2-connected,

(ii) For any two vertices, there exists a cycle containing both,

(iii) For any vertex and any edge, there is a cycle containing both,

(iv) For any two edges, there is a cycle containing both,

(v) For any two vertices and one edge, there is a path from one vertex to the other one that contains the
edge,

(vi) For any three distinct vertices, there is a path from the first to the third and containing the second,

(vii) For any three distinct vertices, there is a path containing any two of them and not the third one.

Let us emphasize that 2-connected unoriented graphs can be seen as stable structures with respect to the
deletion of an arbitrary vertex. Indeed, by the above statement (vii) it means that 2 vertices can always be
joined by a path, even if another arbitrary vertex of the graph as been removed. Let us add that a similar
description of 3-connected, unoriented and finite graphs also exists and is provided for example in [Die,
Sec. 3.2].

53
 Figure 5.3: A 2-connected graph on which the above statement can be observed

5.2 Menger’s theorem

The aim of this section is to present Menger’s theorem, one important result in graph theory. In order to state
a rather general version of this theorem, we first extend some of the definitions already introduced.
Definition 5.5 (A-B-path). Let G = (V, E) be a graph, and let A ⊂ V and B ⊂ V. An A-B path is a path in G
with its starting vertex in A, its end vertex in B, and no internal vertex in A or in B.
Examples of A-B paths are presented in Figure 5.4a. With this first notion at hand, we naturally extend
Definition 5.3.
Definition 5.6 (Internally disjoint A-B paths). Let G = (V, E) be a graph, and let A ⊂ V and B ⊂ V. A family
of A-B paths is said to be internally disjoint if no two paths in the family have an internal vertex in common.

(a) A-B paths (b) Internally disjoint A-B paths

Figure 5.4: Subsets of vertices, and paths between them

Internally disjoint A-B paths are presented in Figure 5.4b. Clearly, if A = {x} and B = {y} for two vertices
x, y of G, one comes back to Definition 5.3. Note that the interest of this definition is that the endpoints of the
different paths can be different elements of A and B.

54
In the rest of this section, we shall consider two subsets A ⊂ V and B ⊂ V with A ∩ B = Ø. More general
situations can be considered, but one has to be more careful....
Definition 5.7 (A-B separator). Let G = (V, E) be a connected graph, and let A ⊂ V and B ⊂ V with A∩B = Ø.
A set S ⊂ V is an A-B separator if any A-B path possess an internal vertex in S .
An A-B separator is presented in Figure 5.5. Observe that this
definition is related to Definition 2.19 about vertex-cut, but is
more flexible, since it does not imply that G −S is disconnected.
Indeed, looking carefully at this definition, the notion of orien-
tation is taken into account. More precisely, the definition of A-
B path holds for directed graphs, and Definition 5.7 also takes
care of orientation. An illustration of this concept is provided
in Figure 5.6.
Figure 5.5: A-B separator (in green)

Figure 5.6: A-B paths with orientation (in red)

Now, given a graph G = (V, E) and for two sets A, B ⊂ V with A ∩ B = Ø, two related problems can easily be
formulated:
Minimization problem: Determine the minimum number κ(A, B) of vertices contained in any A-B separator.
Maximization problem: Determine the maximum number ℓ(A, B) of internally disjoint A-B paths.
A rather general version of Menger’s theorem can now be stated. Note that quite often it is stated for A = {x}
and B = {y}, and only for unoriented graph. On the other hand, it is quite clear that only simple graphs can be
considered: loops do not play any role, but multiple edges would clearly lead to wrong statements (one could
add edges and paths without changing the number of vertices).
Theorem 5.8 (Menger’s theorem). Let G be a connected, simple and finite graph, and let A ⊂ V and B ⊂ V
with A ∩ B = Ø. Assume also that there with no edge with one endpoint in A and one endpoint in B. Then
the equality κ(A, B) = ℓ(A, B) holds, or in other terms the minimum number vertices contained in any A-B
separator is equal to the maximum number of internally disjoint A-B paths.
Note that one inequality is easy to prove, namely ℓ(A, B) ≤ κ(A, B). Indeed, let S denote an A-B separator
set containing κ(A, B) elements. Since S is A-B separating, each A-B path must contain at least one vertex of
S . If we impose that the paths are internally disjoint, it implies that there exists at most κ(A, B) such paths.
This directly leads to the stated inequality. Unfortunately the equality is more difficult to prove, but several
proofs exist. Let us also mention that the precise statement of the theorem depends on various conventions
and might differ between different references. It also seems that various proofs available in the litterature are

55
 /
not correct . In [Die, Sec. 3.3] three proofs are provided for undirected graphs; in [GYA, Sec. 5.3 & 10.3]
one version for undirected and one version for directed graphs are provided, but only in the case A = {x} and
B = {y}. In [15] two versions of the proof are also provided. Note finally that an extension for infinite graphs
also exists, but one has to be more cautious about equalities of the form ∞ = ∞.
Let us present two consequences of the previous result. Since it is related to the notion of connectivity, it will
hold for undirected graphs only. Indeed, for such graphs A-B paths are equal to B-A paths, which is not true
in general for directed graphs.
Proposition 5.9. Let G be a connected, simple, unoriented and finite graph containing at least one pair of
non-adjacent vertices. Then the vertex connectivity κV (G) satisfies

κV (G) = min κ {x}, {y} | x, y non-adjacent vertices of G .



The proof of this statement is provided in [GYA, Lem. 5.3.5], while the proof of the following theorem is
available in [GYA, Thm. 5.3.6]. Note that the following statement is a generalization of the characterization
of 2-connected graphs in terms of internally disjoint paths provided in Theorem 5.4.(ii).
Theorem 5.10 (Whitney’s k-connected characterization). Let G be a connected, simple, unoriented and finite
graph, and let k ∈ N. Then G is k-connected if and only if for any pair x, y of vertices of G there exist at least
k internally disjoint paths between x and y.
Let us still mention in this section that there exist analogues of Menger’s theorem and its consequences in
terms of edges instead of vertices. More precisely, the notion of edges disjoint paths can be introduced, and
separator can be expressed in terms of edges instead of vertices. Then, an edge form of Menger’s theorem can
be formulated, and a statement about edge connectivity holds as well.

5.3 Blocks and block-cutpoint graphs

The decomposition of a graph into blocks reveals its coarse structure, its skeleton. After this decomposi-
tion, a bipartite tree can then be constructed, which encodes the main structure of the graph. Note that this
decompositions holds for undirected graphs. We also recall that all graphs in this chapter are considered as
loopless.
Recall that the notion of cut-vertex has been introduced in Definition 2.19.
Definition 5.11. A block of an undirected graph G is a maximal connected subgraph which does not contain
any cut-vertex (any cut-vertex of the subgraph, but it can contain a cut-vertex of the graph G).
Recall that the notion of maximal means that there is not a larger
structure with the same properties. As a consequence of this defini-
tion, a block is either a maximal 2-connected subgraph containing
at least three vertices, or a dipole, or an isolated vertex. A dipole
consists in two vertices connected by one or several edges. Some
properties of blocks can be easily deduced, and we refer to [Die,
Sec. 3.2] or to [GYA, Sec. 5.4] for the proofs.

Figure 5.7: 1 graph, 5 blocks

56
Lemma 5.12. Let G be an undirected and loopless graph.
(i) Two blocks of G can overlap in at most one vertex, which is
then a cut-vertex of G,
(ii) Every edge of G lies in a unique block,
(iii) Cycles of G are confined in blocks.
Based on the above property, a bipartite tree can be constructed. It reflects the structure of the initial graph.
The construction is called the block-cutpoint graph BC(G) of G and goes as follows: Let G = (V, E) be the
initial graph, and let BC(G) = (W, F) be the block-cutpoint graph. The bipartition W1 , W2 of W is defined
by: each vertex of W1 corresponds to a block of G, each vertex of W2 corresponds to a cut-vertex of G. An
element of W2 is connected to an element of W1 if the corresponding cut-vertex belongs to the corresponding
block. It is then easy to check that the resulting bipartite graph is also a tree, see Figure 5.8.

Figure 5.8: A connected graph and its block-cutpoint graph

57
Chapter 6

Optimal traversals

In Definition 3.13 a graph traversal was introduced as the process of visiting systematically each vertex in a
graph. This definition can naturally be extended to the process of visiting systematically all edges of a graph.
In this chapter, we discuss some problems which often reduce to finding an optimal traversal, under some
constraints. Having more tools available, we also revisit or extend some results mentioned earlier.

6.1 Eulerian trails

Eulerian trails have been introduced in Definition 1.24 and correspond to a trail containing all edges of a
graph, but once and only once. On the other hand, vertices can be visited more than once. If the trail is closed
one speaks about an Eulerian tour.
Eulerian tours are intimately linked to the Seven Bridges of Königsberg’s problem, see [16]. The negative
resolution of this problem by Leonhard Euler in 1736 laid the foundations of graph theory. With the notation
introduced so far, the problem consists in establishing if the graph on the right of Figure 6.1 is an Eulerian
graph (a graph with an Eulerian tour).

Figure 6.1: A map of Königsberg and the corresponding graph, see [16]

As already mentioned, the answer is negative, since a characterization of Eulerian graphs require that all its
vertices have an even degree, see Theorem 1.25. On the other hand, for an unoriented finite graph whose
vertices all have an even number of edges, a rather simple algorithm exists for finding one Eulerian tour. This
algorithm is provided in Figure 6.2. By one minute of thought, one easily concludes that this algorithm is
correct if and only if every vertex has a even degree.
Let us still mention a few extensions of the above result. First of all, Eulerian trails which are not closed can

58
 Figure 6.2: Eulerian tour algorithm, from Algorithm 6.1.1 of [GYA]

also be useful. Indeed, such trails would correspond to trail visiting all edges of the graph, but with an initial
point and a final point which could be different. With this weaker requirement the following result can rather
easily be obtained, see also [GYA, Thm. 6.1.1].
Theorem 6.1. A connected, undirected and finite graph admits an open Eulerian trail if and only if it has
exactly two vertices of odd degree. Furthermore, the initial and the final vertices of any Eulerian trail must be
the two vertices of odd degree.
Two additional results exist explicitly for directed graphs. For completeness, we state them, and leave the
proofs as an exercise. Recall that the notions of indegree and outdegree of a vertex in a directed graph have
been introduced in (2.1.1) and (2.1.2).
Theorem 6.2. (i) A connected, directed and finite graph G = (V, E) is Eulerian if and only if degin (x) =
degout (x) for any x ∈ V.
(ii) A connected, directed and finite graph G = (V, E) admits an open Eulerian trail if and only if there exist
x, y ∈ G with degin (x) + 1 = degout (x), degin (y) = degout (y) + 1, and otherwise degin (z) = degout (z) for
all z ∈ V \ {x, y}.
Note finally that extensions of these results to infinite graphs are not so trivial. Indeed there exist infinite
graphs with vertices of even degree everywhere but which do not admit the natural extension of an Eulerian
tour. Additional information and some references on this infinite problem can be found on [16].

6.2 Postman tour

In the previous section, it was possible to visit all edges of a connected, undirected and finite graph once and
only once if and only if all vertices had an even degree. What about a graph with vertices having arbitrary
degrees ? It might not be possible to visit all edges without visiting some twice, or more, but it is certainly
possible to visit all of them at least once. In that respect the following definition is natural.
Definition 6.3 (Postman tour). A postman tour5 on a connected and finite graph is a closed walk that uses
each edge of the graph at least once. If the graph is endowed with edges weight, an optimal postman tour is a
5
Also called Chinese postman tour, in honor of the Chinese mathematician Mei-ko Kwan (also translated Meigu Guan) who
introduced the problem in 1962.

59
postman tour with the minimum total edge-weight.

Note that if the graph is not endowed with specific weight, one can always consider that a weight 1 is associ-
ated with each edge, and in this case the optimal postman tour corresponds to a shortest postman tour. Two
examples of optimal postman tour are presented in Figure 6.3. Let us also remind that a somewhat related
question has already been investigated in Section 4.4, when the minimum spanning tree problem was consid-
ered. However, the aim is different since the postman has to visit all edges. On the other hand, if the graph
is an Eulerian graph, one easily observes that the solution of the optimal postman tour is simply given by the
sum of the weights on the edges. Indeed, any Eulerian tour would visit all edges once, each of them giving its
contribution to the total weight.

(a) Unweighted graph (b) Weighted graph

Figure 6.3: Two optimal postman tours, from [17]

There exists an algorithm for solving the optimal postman problem, which is presented in Algorithm 6.5 for
undirected graph. The directed version is slightly more complicated. The idea behind the algorithm is to
artificially add some weighted edges between vertices with odd degrees, and choose the edges such that these
additional weights are kept to a minimum value. At the end of the construction, any Euler tour can be chosen
and it has the minimum weight. In order to understand the construction a few more definitions are necessary.

Definition 6.4 (Matching, perfect matching). A matching in a graph G = (V, E) is a set F ⊂ E such that no
two edges in F have a common endpoint. A perfect matching in a graph G is a matching F in which every
vertex of G is one endpoint of an element of F.

A matching and a perfect matching are represented in Figure 6.4. In the con-
struction below, the notion of perfect matching will appear in a complete graph.
More precisely, a complete graph is an undirected graph in which every pair
of distinct vertices is connected by a unique edge. The complete graph with n
vertices is often denoted by Kn and possess n(n − 1)/2 edges. For such a graph,
perfect matching are easily represented, see Figure 6.5 for K6 . The number of
different perfect matching for Kn can be computed and corresponds to (n − 1)!!.
Here, the notation n!! denotes the double factorial or semifactorial function. The
expression of this function is slightly different for n odd or n even, namely for n
even one has
n
2
Y
n!! = (2k) = n(n − 2)(n − 4) · · · 4 · 2 Figure 6.4: A matching, a
k=1
perfect matching
60
while for n odd one has
n+1
2
Y
n!! = (2k − 1) = n(n − 2)(n − 4) · · · 3 · 1.
k=1

Figure 6.5: Perfect matching for K6 , from [18]

Note that in the following algorithm, we assume that the graph is not Eulerian, since otherwise any Eulerian
tour is an optimal postman tour, and there is no need for any algorithm.
Algorithm 6.5 (Optimal postman tour). Let G be a connected, finite, undirected and non Eulerian graph.
(i) Determine the set S = {x1 , x2 , . . . , xn } of all vertices with odd degree (n is always even),
(ii) Construct the complete graph Kn on the vertices S , which means the graph with all edges e jk with
i(e jk ) = (x j , xk ) for x j , xk ∈ S and x j , xk ,
(iii) For x j , xk ∈ S , find in G the path P jk between x j and xk with a minimal weight ω jk , and assign this
weight ω jk to the edge e jk ,
(iv) Determine a perfect matching Fperfect in Kn (containing n/2 edges) with the requirement that the total
edge-weight of Fperfect is a minimum among all perfect matching,
(v) On the graph G add all weighted paths P jk corresponding to edges e jk in Fperfect . This augmented
graph, denoted by G∗ , is an Eulerian graph,
(vi) Choose any Eulerian tour in G∗ ; it is an optimal postman tour.
Note that in the above algorithm, the method for choosing the perfect matching has not been discussed yet.
We also mention that there exist several extensions of this problem. For example, different weights can be
considered on an edge whenever this edge is visited several times. The directed version of the postman tour
exists, and also the windy version. We refer to [GYA, Sec. 6.2] for other extensions, and to internet for
numerous related problems.

6.3 Hamiltonian paths and cycles

Recall that Hamiltonian cycles and Hamiltonian graphs have already been introduced in Definition 1.23. More
generally, one sets:

61
Definition 6.6 (Hamiltonian path). A Hamiltonian path is a path in a graph that contains all vertices of
the graph. If the path is closed, one speaks about a Hamiltonian cycle, and whenever a graph admits a
Hamiltonian cycle, one calls it a Hamiltonian graph.
Note that for a cycle, all vertices can be visited only once, ex-
cept the initial endpoint and the final endpoint which have to
coincide. Let us also mention an easy observation: loops or
undirected multiple edges do not change the property of a graph
of being a Hamiltonian graph or not. For directed graph, adding
multiple edges can change the situation if one adds edges with
the reserved orientation. Quite surprisingly, looking for Hamil-
tonian cycles turns out to be much more complicated than look-
ing for Eulerian tours. There is no simple characterization of
Hamiltonian graphs and there is no fast algorithm for determin-
ing Hamiltonian paths. However, there exit sufficient condi-
tions for a graph to be Hamiltonian that apply to a large class Figure 6.6: A Hamiltonian graph
of graphs. There also exist conditions which show that a graph
can not be a Hamiltonian graph.
Let us start by mentioning some easy rules which can be used for showing that a graph is not Hamiltonian. It
is based on the observation that only two edges adjacent to a vertex can be used in a Hamiltonian cycle. These
rules are:
(i) If a vertex x has degree 2, both incident edges must be used in any Hamiltonian cycle,
(ii) During the construction of a Hamiltonian cycle, no cycle can be formed until all vertices are visited,
(iii) If two edges of a given vertex have to be used for a Hamiltonian cycles, then all the other adjacent edges
can be disregarded.
The justification of the rules (i) and (iii) are quite clear. For (ii), it is enough to observe that whenever a cycle is
created, its initial point and its final point have to be the same, which means that this vertex is visited twice. If
this cycle is not the Hamiltonian cycle, then visiting twice a vertex is not allowed. This prevents the existence
of any cycle before the final Hamiltonian cycle. Based on these rules, the following exercise can be done.
Exercise 6.7. Show that the following two graphs are not Hamiltonian graphs.

Figure 6.7: Two non-Hamiltonian graphs, from [GYA, Sec. 6.3]

Another interesting exercise shows that Hamiltonian cycles and Hamiltonian paths are indeed different.
Exercise 6.8. Prove that the Petersen graph presented in Figure 2.12 admits a Hamiltonian path but no
Hamiltonian cycle. Some information for this proof can be obtained from [19].

62
As mentioned above, there also exist some sufficient conditions for a graph to be a Hamiltonian graph. We
provide such a result both for undirected and for directed graphs. Note however that these results are not really
efficient for graphs with a large number of vertices: they also require a large number of edges.

Theorem 6.9 (Ore, 1960). Let G be a simple undirected graph with n vertices and n ≥ 3. If deg(x)+deg(y) ≥ n
for each pair of non-adjacent vertices x and y, then G is a Hamiltonian graph. In particular, if deg(x) ≥ n2 for
any x, then G is a Hamiltonian graph.

The proof of the above theorem can be found in [GYA, Thm. 6.3.1]. It is not a completely trivial proof, and
it is based on a contradiction argument. Let us emphasize an easy and useful consequence of this result: For
n ≥ 3 any complete undirected graph Kn is a Hamiltonian graph. In fact, the number of different Hamiltonian
cycles in Kn is (n − 1)!/2. For this computation, cycles that are the same apart from their starting point are not
counted separately.

Theorem 6.10 (Woodall 1972). Let G be a simple directed graph with n vertices. If for any vertices x and y
with no edge from x to y one has degout (x) + degin (y) ≥ n, then G is a Hamiltonian graph. In particular, if
degout (x) ≥ n2 and degin (x) ≥ n2 for any x, then G is a Hamiltonian graph.

6.4 The travelling salesman problem

Hamiltonian cycles are related to the famous travelling salesman problem (TSP). This problem consists in
determining the shortest Hamiltonian cycle in a given weighted graph. Note that we assume in this section
that all weights are non-negative. If the graph is undirected one speaks about the symmetric TSP (sTSP)
while if the graph is directed, one speaks about the asymmetric TSP (aTSP). Also, let me remind that shortest
Hamiltonian cycle means a Hamiltonian cycle with the minimum total weight (it might not be unique). Such
a problem appears when a salesman wants to visit n cities once before returning home. The weight on the
edges can represent the distance between the cities, or the cost of the transportation. Note that loops do not
play any role for this problem, and multiple edges going in the same direction can be avoided by considering
always the one with the minimum weight. On the other hand, in directed graphs, two edges going in opposite
directions can not be simplified.

As we have seen in the previous section, not all graphs admit a Hamiltonian cycle. There are several ways
for avoiding this situations. For example, one can allow some back-and-forths which are not too costly, or
complete the graph with artificial edges of arbitrarily large weights. Once a complete graph is obtained, it is
sure that Hamiltonian cycles exist.

A rather famous solution to the aTSP is provided by the Bellman-Held-Karp algorithm, and this algorithm can
,
be studied for a report . However, if n denotes the number of vertices of the graph, the complexity of this
algorithm is of order O(n2 × 2n ). For large n, using this approach would require too much time, and therefore
this algorithm can not be applied. In such a situation, one should not look for the shortest solution, but to a
solution close to the best one. This approach is often based on the following concept:

Definition 6.11 (Heuristic). A heuristic or heuristic function is a guideline that helps in choosing from several
possible alternatives for a decision step. A heuristic algorithm is an algorithm whose steps are guided by
heuristics. This is usually achieved by trading optimality, completeness, accuracy, or precision for speed.

According to [20] the trade-off criteria for deciding whether to use a heuristic for solving a given problem
include the following:

63
 1. Optimality: When several solutions exist for a given problem, does the heuristic guarantee that the best
solution will be found ? Is it actually necessary to find the best solution ?
2. Completeness: When several solutions exist for a given problem, can the heuristic find them all ? Do
we actually need all solutions ? Many heuristics are only meant to find one solution.
3. Accuracy or precision: Can the heuristic provide a confidence interval for the purported solution ? Is
the error bar on the solution unreasonably large ?
4. Execution time: Is this the best known heuristic for solving this type of problem ? Some heuristics
converge faster than others. Some heuristics are only marginally quicker than classic methods.
The simplest sTSP heuristic is based on the nearest neighbour, as shown in Fig-
ure 6.9. The leading idea of this algorithm is to always choose the cheapest way
to go somewhere. The framework is a complete graph, which can always be re-
alized, as mentioned above. The implementation of this algorithm is very easy,
but its performance can be pretty bad, as illustrated in the example of Figure 6.8.
Indeed, by applying this algorithm on this graph, one gets a Hamiltonian cycle
of total weight of 1, 000, 003, while a clever choice would lead to a Hamiltonian
cycle of total weight 6. The weakest point of this algorithm is that it does not
look for a global minimum weight, but looks for the minimum weight only at
every step. Figure 6.8: A weighted
graph

Figure 6.9: Nearest neighbour algorithm, from Algorithm 6.4.1 of [GYA]

Another heuristic algorithm for sTSP is based on the minimum spanning tree introduced in Section 4.4. The
framework is again a complete graph. It also uses the characterization of Eulerian graphs, namely that any
graph with an even degree at every vertex admits an Eulerian tour. The main idea is to follow paths in the
minimum spanning tree, as long as possible, and jump to another part of the spanning tree once an already
visited vertex is reached. The precise form of this algorithm is provided in Figure 6.10. If we summarize it
very briefly, it consists in three steps: 1) Find the minimum spanning tree T ∗ of the initial weighted graph,
2) Duplicate every edge of T ∗ , 3) Return a Hamiltonian cycle obtained by taking some shortcuts on the
duplicate tree. An illustration of this procedure is provided in Figure 6.11.
So far, we have not discussed the performance of these algorithms. Indeed, as mentioned above, there is
always a trade-off between rapidity but also accuracy. In order to discuss the accuracy, more assumptions on

64
 Figure 6.10: Double tree algorithm, from Algorithm 6.4.2 of [GYA]

Figure 6.11: The three main steps of the double tree algorithm (observe that the first picture contains a mistake,
the last 2 vertices on the left should be labelled H and I).

the edge-weights have to be imposed. The following assumption is rather natural.

Definition 6.12. Let G = (V, E, ω) be a weighted graph, and let e xy , e xz and ezy be any elements of E satisfying
i(e xy ) = (x, y), i(e xz ) = (x, z) and i(ez y) = (z, y) for some vertices x, y, z ∈ V. Then G is said to satisfy the
triangle inequality if the following inequality holds:

ω(e xy ) ≤ ω(e xz ) + ω(ezy ).

Note that this condition is so natural that it is implicitly assumed in most works about TSP. If the edge-
weights represent a distance or the cost of a transportation, this condition is satisfied. Now, if we assume
that the weighted graph we consider satisfies the triangle inequality, then a comparison between the solution
provided by the double tree algorithm and the optimal solution can be inferred.
Lemma 6.13. Let G be an undirected weighted and complete graph satisfying the triangle inequality. Then
the solution for the sTSP produced by the double tree algorithm provided in Figure 6.11 is never worst than
twice the optimal value.

Proof. Let C ∗ be an optimal solution for the sTSP, and let T ∗ be a minimum spanning tree constructed on G.
Let W be the Eulerian tour constructed on the two copies of T ∗ , as indicated in the double tree algorithm, and

65
let C be the Hamiltonian cycle obtained by the double tree algorithm. If ω(X) denotes the total edge-weight
of the graph X then one has clearly

ω(T ∗ ) ≤ ω(C ∗ ) and ω(W) = 2ω(T ∗ ).

In addition, since any shortcut corresponds to an edge in the initial graph, one infers from the triangle inequal-
ity that ω(C) ≤ ω(W). By putting these inequality together one gets:

ω(C) ≤ ω(W) = 2ω(T ∗ ) ≤ 2ω(C ∗ )

which is the desired inequality. □

We shall now improve the double tree algorithm. Indeed, part of the construction in the algorithm is not
optimized: the shortcuts have been chosen rather randomly. But a clever solution has already been introduced
in Algorithm 6.5, and it was based on the choice of an optimal perfect matching. Thus, the main steps in
the new algorithm will be: 1) Find the minimum spanning tree T ∗ of the initial weighted graph, 3) Find a
minimum perfect matching M ∗ between the vertices of odd degree of T ∗ , 3) Return T ∗ + M ∗ and take some
shortcuts. Let also provide the details:
Algorithm 6.14 (Christofides’s algorithm). Let G be an undirected weighted and complete graph satisfying
the triangle inequality.
(i) Create a minimum spanning tree T ∗ of G,
(ii) Let O be the subgraph of G induced by the vertices with odd degree in T ∗ ,
(iii) Find a minimum perfect matching M ∗ in the subgraph O,
(iv) Combine the edges of M ∗ and of T ∗ in an Eulerian graph H,
(v) Construct an Eulerian tour W of H,
(vi) Construct a Hamiltonian cycle in G from W, as in the double tree algorithm, namely: follow the se-
quence of edges and vertices of W until the next edge in the sequence is joined to an already visited
vertex. At that point, skip to the next unvisited vertex by taking a shortcut, using an edge that is not part
of W. Resume the traversal of W, taking shortcuts whenever necessary, until all the vertices have been
visited. Complete the cycle by returning to the starting vertex via the edge joining it to the last vertex.
An illustration of this construction is provided in Figure 6.12.
The interest of this improved algorithm can be seen in the following statement:
Lemma 6.15. Let G be an undirected weighted and complete graph satisfying the triangle inequality. Then
the solution for the sTSP produced by Christofides’s algorithm provided in Algorithm 6.14 is never worst than
3
2 times the optimal value.

Proof. Let C ∗ be an optimal solution for the sTSP, and let T ∗ be a minimum spanning tree constructed on G.
One always has ω(T ∗ ) ≤ ω(C ∗ ). Consider O and M ∗ as described in Algorithm 6.14, and let us show that
ω(M ∗ ) ≤ 21 ω(C ∗ ).
For that purpose, let us enumerate the vertices of O in cyclic order around C ∗ and call them {x1 , x2 , . . . , x j }
with j an even number. Consider then a split of C ∗ into two sets of paths: the ones starting at xk with k even,
and the ones starting at xk with k odd. Each of these two sets of paths define a perfect matching of O that

66
 Figure 6.12: The four main steps of Christofides’s algorithm.

matches the two endpoints of each path. The weight of these perfect matching is at most equal to the weight of
the corresponding paths, by the triangle inequality. Since these two sets of paths partition the edges of C ∗ , one
of the two sets has at most half of the weight of C ∗ . Thus, the corresponding perfect matching has a weight
that is also at most half the weight of C ∗ . As a consequence, the minimum perfect matching can not have a
larger weight, which means that ω(M ∗ ) ≤ 21 ω(C ∗ ), as stated.
Finally, adding the weights of T ∗ and M ∗ gives the weight of the Euler tour W, which is thus at most 23 ω(C ∗ ).
Thanks to the triangle inequality, shortcuts do not increase the weight, so the weight of the output is also at
most 23 ω(C ∗ ). □

Let us mention that Christofides’s algorithm has been the best heuristic algorithm for more than 30 years for
the aTSP. It is only since 2010 that some improvements have been proposed. As of 2020, the best algorithm
provided a result which is never worst than 1.4 times the optimal value, see A. Sebö and J. Vygen, Combi-
natorica 34 (2014), 597–629. Let us however note that the setting is slightly different: all weight are 1 and
the graph G is not complete. In this framework one looks for a minimum length closed walk in G that visits
every vertex at least once. Equivalently, one looks for the shortest Hamiltonian cycle in the metric closure
of G. Here, the metric closure of a connected, undirected graph G consists in the complete weighted graph
Ḡ = (V̄, Ē, ω̄) where V̄ = V, Ē contains all possible edges between the elements of V̄, and ω̄(e) = 1 if e ∈ E,
while for e ∈ Ē \ E the weight ω̄(e) is given by the shortest distance in G between the two endpoints of e.
For digraphs, the TSP is much harder, and significants results have only been obtained during the last couple of
years. For the aTSP, the framework is a strongly connected digraph with non-negative weights, see Definition
1.18 for the notion of strongly connected. It is also assumed that the graph is Eulerian, which corresponds to
the equality of the indegree and the outdegree at every vertex, as mentioned in Theorem 6.2. For such graphs,
the best result so far is provided in the next statement (explanations are provided after the statement).
Theorem 6.16 (Theorem 1.1 of [21]). There is a polynomial-time algorithm for aTSP that returns a tour of
value at most 506 times the Held-Karp lower bound.
As already mentioned, the Bellman-Held-Karp Algorithm would require too much time for a large graph,

67
and therefore can not be implemented. However, there exists a lower bound for the minimum weight for a
TSP (oriented or not), the so-called Held-Karp lower bound (HK). There exist estimates about the difference
between the Held-Karp lower bound, and the minimum value of the aTSP, and the current estimate seems
to be ω(aTSP) ≲ 2 HK. The main difference between the content of Theorem 6.16 and this estimate is that
the theorem provides a constructive solution for the Hamiltonian cycle, while the lower estimate does not.
As already mentioned, investigations on the aTSP are currently taking place, and lots of information (rather
advanced) are available on internet.

68
Chapter 7

Graph colorings

In this chapter we discuss the colorings of graphs obtained by putting colors on the vertices. Such colorings
have several practical applications. All graphs in this chapter are undirected, since orientation does not play
any role in this context.

7.1 Vertex-colorings
In this section, colors are applied to vertices. In fact these colors can be identified with weights assigned to
vertices, and this is how they are often represented: a number assigned to a vertex corresponds to a color put
on this vertex. In other context, one speaks about labeled vertices. For internal coherence we shall continue
using the notation introduced in Section 1.4 on weighted graphs. In the following definition, C represents a
finite set whose elements are called colors. Usually, one sets C = {1, 2, 3, . . . k}, but a set of colors or a set of
letters can also be used. For several applications, it is useful to have a total order on C. For numbers or letters,
this is clear, for colors one can just set a bijection between a set of numbers and the set of colors.
Definition 7.1 (Vertex-coloring). Let G = (V, E) be a loopless graph and let C be a set containing k elements.
A vertex k-coloring or simply k-coloring of G is a map ω : V → C such that ω(x) , ω(y) whenever x and y
are the two endpoints of an edge in E.
Note that some authors would speak about a proper k-coloring for this definition, and about a k-coloring if the
last condition of the definition is not imposed. However, since this condition is always the key condition, it
seems natural to include it in the main definition. Note also that the graph is loopless, because any loop would
directly invalidate this definition.
Definition 7.2 (Color class). For a k-coloring of G, the set of all vertices sharing the same color is called a
color class.
In mathematical terms, it would be natural to define a color class by ω−1 ( j) for any j ∈ C. Indeed, this notation
corresponds to the set of all elements x of V such that ω(x) = j. Since ω(x) is well defined for any x ∈ V,
each vertex belong to one and only one color class. For that reason, the set of color classes defines a partition
of V. Namely, if we denote by V1 , V2 , . . . , Vk the color classes, then ∪ j V j = V and V j ∩ Vℓ = Ø for any j , ℓ.
Let us also emphasize that any e ∈ E has its endpoints in two different sets V j .
It is clear that a finite graph always admits a k-coloring for k large enough. On the other hand, for small k it is
not clear that a given graph admits a k-coloring since the condition about the endpoint of any edge could be

69
impossible to satisfy. In this context, the following definition is quite natural.

Definition 7.3 (k-colorable and chromatic number). A loopless graph G is k-colorable if it admits a k-coloring.
The vertex chromatic number, or simply chromatic number of G denotes the minimum number k required for
a k-coloring of G. This number is denoted by χ(G), and if χ(G) = k, the graph G is said to be k-chromatic. A
χ(G)-coloring is called a minimum coloring.

Clearly, a k-chromatic graph is k-colorable, but it is not (k − 1)-colorable. A few examples of chromatic
numbers can be easily computed. Note that Cn denotes the cycle graph consisting of a cycle with n vertices.

Graph G χ(G)
no edge 1
bipartite graph 2
non trivial tree 2
cycle graph Cn with n even 2
cycle graph Cn with n odd 3
complete graph Kn n

Table 7.1: Chromatic numbers

Finding the chromatic number of a given graph is usually not an easy task. In fact finding an upper bound
is quite simple, but showing that there does not exist any k-coloring for some small k is a hard problem.
Nevertheless some results can be easily obtained. Before presenting them, we introduce the simplest algorithm
in this context:

Algorithm 7.4 (Sequential vertex-coloring). Let G be a loopless finite graph with vertices {x1 , x2 , . . . , xN },
and let C = {1, 2, . . . }.

(i) Fix i := 1,

(ii) Define ω(xi ) as the smallest element of C not used by any vertex x j adjacent to xi with j < i, and set
i := i + 1,

(iii) Repeat (ii) until i = N + 1.

This algorithm always return a coloring of G but it is rarely a minimum coloring. The example of an appli-
cation of this algorithm is provided in Figure 7.1: the first figure indicates the initial ordering of the vertices,
the second figure presents the result of the sequential vertex-coloring, while the last figure corresponds to a
minimum coloring of the graph. However, note that there was some arbitrariness in indexing the vertices in
a certain order x1 , x2 , . . . . By choosing a different initial ordering another coloring (probably with a different
number of colors) would have been obtained. An interesting observation is that there always exists an initial
ordering of the vertices which would lead with this algorithm to a minimum coloring. However, finding this
very good initial ordering is not simpler than looking directly for a minimum coloring.

Let us now state and prove some easy results. Recall that the maximal degree ∆(G) of a graph has been intro-
duced in Section 1.1, the clique number w(G) has been introduced in Definition 2.16, and the independence
number α(G) has been introduced in Definition 2.17.

Lemma 7.5. For any loopless finite graph G, one has χ(G) ≤ ∆(G) + 1.

70
 Figure 7.1: Initial ordering, sequential vertex-coloring, minimum coloring, from [GYA, Sec. 8.1]

Proof. By using the sequential vertex-coloring algorithm, no more than ∆(G) + 1 colors will ever be used, no
matter what is the initial ordering of the vertices. □

Lemma 7.6. For any loopless finite graph, one has χ(G) ≥ w(G).

Proof. Since the elements of a clique are all mutually connected, it is necessary to use k colors for a clique
containing k elements. The statement follows directly from this observation. □

For the next lemma, we introduce the ceiling function: For any s ∈ R we write ⌈s⌉ for the least integer greater
than or equal to s. This function is clearly related to the floor function: For any s ∈ R we write ⌊s⌋ for the
greatest integer less than or equal to s The graphs of these two functions are represented in Figure 7.2, and
additional properties can be found in [22].

(a) The ceiling function (b) The floor function

Figure 7.2: Two integer valued functions, from [22]

l |V|
m
Lemma 7.7. For any finite graph G = (V, E) one has χ(G) ≥ α(G) , where |V| denotes the cardinality of V,
namely the order of G.

Proof. Since each

l |V| color
m class contains at most α(G) vertices, the number of different color classes must be at
least equal to α(G) . □

71
Let us add one more easy observation: For any finite graph G and any subgraph H of G one has χ(G) ≥ χ(H).
This is quite clear since any minimum coloring of G is also a minimum coloring of H. Note however that in
general a minimum coloring of H can not be used as a starting point for a coloring of G. This observation can
be used for guessing some lower bound for χ(G). Indeed, if one subgraph H of G is not k-colorable for some
k, then the graph G itself won’t be k-colorable. In such a case, we say that the subgraph H is a k-obstruction.
Let us provide now a result which sharpen the easy Lemma 7.5. The statement has been proved by Brooks in
1941, and several proofs are available over the internet, see also [GYA, Thm. 8.1.21].
Theorem 7.8 (Brooks’ theorem). For any connected, undirected, loopless and finite graph G, one has χ(G) ≤
∆(G), unless G is a complete graph Kn or a cycle graph Cn with n odd, in which case χ(G) = ∆(G) + 1.
Remark 7.9. For some applications, it might be useful to look for a k-coloring of a graph even if k is smaller
than the chromatic number of the graph ! In such a case, one consider k-colorings by disregarding some edges
for which the condition of not having the same color at their endpoint does not hold. Then, one look for the
k-coloring which minimizes the number of edges which have to be excluded. Alternatively, one can consider
edge weights and try to minimize the total weight of the edges which have to be disregarded. If the weight
corresponds to the importance of an edge, it means that some edges of lower importance can be disregarded.
We end this section with a heuristic algorithm. Based on our intuition, when coloring a graph a vertex with
a large degree should be considered before a vertex with a small degree. In addition, for two vertices with
the same degree, the one having a denser subgraph generated by its neighbours should be treated first, see
Definition 1.4 for the notion of neighbours. We shall say that a vertex x is uncolored if no value to ω(x) has
been attributed so far. We also call the colored degree of a vertex x the number of different colors that have
been assigned to vertices adjacent to x.
Algorithm 7.10 (Largest-degree-first algorithm). Let G be a loopless and finite graph, and let C = {1, 2, . . . }.
(i) Set i = ∆(G),
(ii) Among all uncolored vertices of degree i, choose a vertex x with a maximum colored degree, and set
ω(x) = k with k the smallest possible color,
(iii) Repeat (ii) as long as there exists some uncolored vertices of degree i,
(iv) Set i := i − 1 as long as i ≥ 1, and go back to (ii).
An application of this algorithm is provided in Figure 7.3. In this case, this algorithm has a better outcome
than the sequential vertex-coloring algorithm. However, this is not always the case, it all depends on the initial
ordering for the sequential vertex-coloring algorithm. On the other hand, observe that no initial ordering is
necessary for the largest-degree-first algorithm.
Remark 7.11. There exists also a notion of edge-coloring and the theory can be developed as above. For
certain applications, this approach is even more natural, but these two theories are very close to each other
of some dualities between graphs, see Definition 7.23 and its generalization. Some information about edge-
coloring can be found in [Die, Sec. 5.3], in [CH, Sec. 6.5], or in [GYA, Sec. 8.3].

7.2 Plane graphs

In the previous section, representations of a graph did not play any role. For other applications, the represen-
tation is as important as the graph itself, and the ambient space for the representation is also important. In this

72
 Figure 7.3: An application of the largest-degree-first algorithm, see Figure 8.1.4 of [GYA]

section we shall stick to the ambient space R2 (the usual plane). Note however that representations on other
surfaces (like on a sphere or on a 2-torus) are also important.
Definition 7.12 (Plane graph). A plane graph is a finite graph G = (V, E) with the set of vertices V given by
{x1 , x2 , . . . , xN } ⊂ R2 , with the set of edges E given by a finite family of simple arcs (bijective and bicontinuous
images of [0, 1]) having endpoints in V, and such that the interior of any arc contains no vertex and no point
of any other edge.
In simpler terms, a plane graph is sometimes defined by a planar drawing of a finite graph with no edge-
crossing, but the above definition is certainly more precise. Note that this definition allows loops and multiple
edges, which is sometimes not accepted in the definition of a plane graph (it depends on the authors). In this
setting, we call faces of the plane graph G the open components defined by R2 \ G. For any plane graph G,
there is always one face which is unbounded (called the outer face) and a finite number of bounded faces
(called the inner faces). The set of faces of G is denoted by F(G), see Figure 7.4 which contains 4 faces. For
two distinct faces, we say that they are adjacent if they are separated by one (or more) edge. Equivalently,
they are adjacent if their closure in R2 contain at least one common edge.
For plane graphs, there exists a quite famous formula linking the number of vertices, the number of edges,
and the number of faces (including the unbounded one).
Theorem 7.13 (Euler’s theorem). Let G = (V, E) be a connected plane graph, then the following equality
holds:
|V| − |E| + |F(G)| = 2, (7.2.1)
where |F(G)| denotes the number of faces of G.
There exist many proofs of this result, which can be stated in a more general framework. For simple plane
graph we refer for example to [Die, Thm 4.2.9], or to [23] for twenty-one different proofs of this result. We
shall now derive additional relations on plane graphs. We first give a definition related to the boundary of a
face.
Definition 7.14 (Size of a face). Let G be a connected plane graph, and let f ∈ F(G) be one of its faces. The
size of f is the number of edges of G on a boundary walk around f . We set size( f ) for the size of the face f .
If the plane graph is simple, the size of a face is rather easy to com-
pute, and this number is always bigger than or equal to 3. For plane
graphs with loops or multiple edge, one has to be more careful, and

73

Figure 7.4: Plane graph with 4 faces

this number can be 1 or 2. For example, in Figure 7.4, the face f1 is of size 1, the face f2 is of size 2, the face
f3 is 3, and the face f4 is of size 6. Based on this definition, a simple relation based on faces can be obtained:
Lemma 7.15 (Face-size relation). Let G = (V, E) be a connected plane graph, and let F(G) denote the set of
its faces. Then the following relation holds
X
2|E| = size( f ). (7.2.2)
f ∈F(G)

Proof. Each edge either occurs once in each of two different face boundary walks or occurs twice in the same
boundary walk. Thus, by definition of face-size, each edge contributes two sides to the sum. □

Recall now that the girth of a graph has been introduced in Definition 1.20. It corresponds to the length of the
shortest cycle in a graph, as long as the graph is not a tree. Then, by a minute of thought, or by looking at
[GYA, Prop. 7.5.5] one easily observes that for a plane graph which is not a tree the relation

girth(G) ≤ min size( f ) (7.2.3)

f ∈F(G)

always holds. Based on this observation and on the previous lemma, one infers:
Lemma 7.16 (Face-edge relation). Let G = (V, E) be a connected plane graph, and let F(G) denote the set of
its faces. Then the following relation holds:

2|E| ≥ girth(G) |F(G)|. (7.2.4)

Proof. The inequality is a direct consequence of the equality (7.2.2) together with the inequality (7.2.3). □

These various easy results lead to a rather important property of simple plane graphs. Recall that if G is
simple, it has no loop and no multiple edge, and as a consequence its girth is always bigger than or equal to 3.
Theorem 7.17. Let G = (V, E) be a connected simple plane graph with |V| ≥ 3. Then the following inequality
holds
|E| ≤ 3|V| − 6. (7.2.5)

Proof. From (7.2.4) with girth(G) ≥ 3 one infers that 2|E| ≥ 3|F(G)|, or equivalently 32 |E| ≥ |F(G)|. By
inserting this inequality in (7.2.1) one infers that |V| − |E| + 23 |E| ≥ 2, which is equivalent to |V| − 31 |E| ≥ 2.
The statement follows easily from this inequality. □

Let us briefly mention some direct consequence of this result, proofs can be done as an exercise. For example,
it follows from the previous theorem that the complete graph K5 can not be represented as a plane graph.
Also, any simple graph G = (V, E) with |V| = 8 and |E| ≥ 19 can not be represented as a plane graph. More
generally we say that a graph which can not be represented as a plane graph that it is not a planar graph. In
the next statement, we strengthen the previous result in the special case of a bipartite graph.
Theorem 7.18. Let G = (V, E) be a connected, simple, and bipartite plane graph with |V| ≥ 3. Then the
following inequality holds
|E| ≤ 2|V| − 4.

74
Proof. The proof is quite similar to the previous one, but this time the girth of a simple bipartite graph is
at least 4 (it can not be 3 by the bipartiteness property). Thus one gets from (7.2.4) that 2|E| ≥ 4|F(G)|, or
equivalently 21 |E| ≥ |F(G)|. By inserting this inequality in (7.2.1) one infers that |V| − |E| + 21 |E| ≥ 2, which is
equivalent to |V| − 12 |E| ≥ 2. The statement follows easily from this inequality. □

As for K5 before, the previous result has an important consequence on

the so-called graph K3,3 , see Figure 7.5. This graph is connected, sim-
ple and bipartite, with 6 vertices and 9 edges. As a consequence of the
previous Theorem, this graph can not be represented as a plane graph,
and therefore is not a planar graph. The two graphs K5 and K3,3 are
sometimes referred to as the Kuratowski graphs. This name comes
from the important result presented below. Before it, one needs to
introduce two more concepts: Figure 7.5: The K3,3 graph
Definition 7.19 (Subdivision). A subdivision of a graph G is a new
graph obtained by subdividing some of the edges of G by adding new vertices on these edges. Any subdivision
of G is denoted by T G.
A graph and one of its subdivision are presented in Figure 7.6a.

(a) A graph H and one subdivision (b) A graph with H as a topological minor

Figure 7.6: A subdivision and a topological minor, from Sec. 1.7 of [Die]

Definition 7.20 (Topological minor). A graph H is a topological minor of a graph G if G contains T H as a

subgraph.
In Figure 7.6b the previous figure appears as a topological minor of the graph. We can now state a character-
ization of planar graphs. More precisely, the following theorem provides necessary and sufficient conditions
for a graph to have a planar representation.
Theorem 7.21 (Kuratowski’s theorem). A graph G admits a plane graph representation (i.e. is a planar graph)
if and only if G does not contain the graphs K5 or K3,3 as a topological minor.
Note that necessity of the absence of these two graphs is quite simple, but the difficult part of the proof is the
sufficiency. We refer to [Die, Sec. 4.4] for a proof in the case of simple graphs, or to [GYA, Sec. 7.4] for a
proof without the assumption of simplicity. Note however that multiple edges or loops do not play a role here.
Having now a criterion for the planarity of graphs, we can state one of the best known results for plane graphs.
As shown in the following section, this results implies that any map can be coloured with four colors.
Theorem 7.22 (Four colors theorem). Every loopless plane graph is 4-colorable.
This theorem is one milestone in graph theory, and a lot of information on it are available, as for example
in [24] or in every book on graph theory. Note that its proof has been one of the most challenging problem

75
in computer’s assisted mathematics. However, there exists a weaker statement which is perfectly accessible:
Every loopless plane graph is 5-colorable. Its proof is provided in Section 7.4.

7.3 Map-colorings
Let us start by introducing the notion of plane duality. The idea is the following: Starting from a plane graph
G = (V, E), we construct a new plane graph G∗ by first placing a new vertex in each face of G. This defines a
set V ∗ . Edges are then added with the following rule: for any e ∈ E we link the two vertices of V ∗ separated by
e by an edge e∗ crossing e; if e is incident with only one face, we attach a loop e∗ to the vertex corresponding
to that face, again crossing the edge e. The set of such e∗ defines E ∗ , and the dual graph is G∗ = (V ∗ , E ∗ ).
Before stating a more precise definition, two examples are provided in Figures 7.7.

(a) A simple graph (b) A graph with mutiple edge and loop

Figure 7.7: Dual graphs, in red

Definition 7.23 (Dual graph). Let G = (V, E) and G∗ = (V ∗ , E ∗ ) be two connected and plane graphs, with
corresponding set of faces F and F ∗ . The graph G∗ is dual of G if there exist bijections
F ∋ f 7→ x∗ ( f ) ∈ V ∗ , E ∋ e 7→ e∗ ∈ E ∗ , V ∋ x 7→ f ∗ (x) ∈ F ∗
satisfying the following conditions
(i) x∗ ( f ) ∈ f for any f ∈ F,
(ii) e intersects G∗ only on one point, e∗ intersects G only on one point, and these intersections correspond
to an intersection between the interior of e and the interior of e∗ ,
(iii) x ∈ f ∗ (x) for any x ∈ V.
It is rather clear from this definition that any connected and plane graph admits a dual, and in fact the initial
graph is the dual of its dual graph. In other words, the map G → G∗ is an involution. Note also that this notion
of a dual graph can be abstracted to more general graph (they don’t have to be plane graphs anymore). In this
extended framework, a graph is a planar graph if and only if its dual is a planar graph. We shall not develop
this theory here, but refer to [Die, Sec. 4.6] for more information. We also mention one additional property
which can be proved as an exercise. In fact, [CH, Sec. 5.6] contains several nice properties of the dual graph
which can be obtained rather easily.
Exercise 7.24. An edge of G is a loop if and only if the associated edge e∗ is a bridge in G∗ .
Let us now define a special instance of a connected plane graph. The name is surprisingly natural, as we can
easily observe.

76
Definition 7.25 (Map). A map is a connected plane graph with no bridge.
As a consequence of Exercise 7.24, the dual graph of a map is a plane graph with no loop. In fact, the
absence of loop in the dual graph is one of the interest of the definition of a map. The following definition is
a reminiscence of the a vertex k-coloring.
Definition 7.26 (Map-coloring). Let G be a plane graph without bridge (i.e. a map), and let C be a set
containing k elements. A map k-coloring of G is a function F(G) → C with the requirement that any two
adjacent faces are colored differently.
Let us observe that the absence of bridge is a necessary requirement for the existence of a map k-coloring.
Indeed, the graphs presented in Figure 7.8 contain bridges and do not accept any map-coloring.

Figure 7.8: Graphs with a bridge

We can finally make the link between the notion of map-coloring and the four colors theorem stated in The-
orem 7.22. Indeed, since any map G has a dual graph which is loopless, the four colors theorem applies to
its dual graph G∗. Then, since any vertex x∗ of G∗ belong to a unique face of G, one can color this face with
the color of x∗ . The condition that any edge in G∗ has two endpoints of two different colors implies that two
adjacent faces in G have also two different colors. By calling a region what has been named a face, one has
thus proved:
Theorem 7.27. No more than four colors are required to color the regions of any map so that no two adjacent
regions have the same color.
An illustration of this result is presented in Figure 7.9.

7.4 The five color theorem

The material of this section has been studied and provided by Tomoya Tatsuno. It is based on references [Die,
Sec. 5.1] and [26].
There is a very famous theorem in graph theory called the four color theorem, which states that every loopless
plane graph is 4-colorable. As a consequence of this theorem, every map can be colored with at most four
colors so that no two adjacent regions have the same color. Although the four color theorem is known to be
very difficult to prove, there is a weaker version of this theorem that can be proven much more easily:
Theorem 7.28 (Five Color Theorem). Every loopless plane graph is 5-colorable.
We shall first state an important lemma that we use in the proof of the five color theorem, which has already
been proven in the lecture. First of all, the meaning of every terminology and notation used in this article is
the same as in the lecture. However, let us just recall the definition of plane graphs for clarity.

77
 Figure 7.9: Illustration of the four colors theorem, from [25]

Definition 7.29. A plane graph is a finite graph G = (V, E) with the set of vertices V given by {x1 , x2 , . . . , xN } ∈
R2 , with the set of edges E given by a finite family of simple arcs (bijective and bicontinuous images of [0, 1])
having endpoints in V, and such that the interior of any arc contains no vertex and no point of any other edge.

Note that this definition does not assume that plane graphs are simple. As written in the lecture notes, it
depends on each author if plane graphs are assumed to be simple or not. However, it should be noted that
when we discuss the coloring of loopless plane graphs, multiple edges do not play a role at all, and next lemma
for a connected simple graph plays an important role in the proof of Theorem 7.28:

78
Lemma 7.30. Let G = (V, E) be a connected simple plane graph with |V| ≥ 3. Then the following inequality
holds:
|E| ≤ 3|V| − 6 (7.4.1)

Observe that the assumption that G is simple cannot be eliminated. Indeed, if G is allowed not to be simple,
then the inequality does not hold because we can choose two vertices and increase the number of edges
between them arbitrarily without changing the number of vertices.
Let us now prove the main result of this section.

Proof of Theorem 7.28. Let G = (V, E) be any loopless plane graph. First, we may assume that G is simple
since multiple edges do not play a role at all in coloring. Since G is simple, we can use the notation (x, y) ∈
V × V for an edge e such that i(e) = (x, y). Also, since G is a union of its connected components, it suffices to
show that G is 5-colorable when G is connected. Hence we may assume that G is connected and simple. We
give a proof by induction on |V|. If |V| ≤ 5, then by assigning different colors to each vertex, G is 5-colorable.
Suppose that the statement holds for |V| = n for some integer n ≥ 5. Let us show that the statement holds for
|V| = n + 1. Let |V| = n + 1.
Claim 1 There exists v ∈ V such that deg(v) ≤ 5.
Proof for Claim 1
Suppose for any v ∈ V, deg(v) ≥ 6. Since each vertex has at least 6 edges starting from it and one edge is
shared by exactly two vertices, one has
6|V| ≤ 2|E| (7.4.2)
On the other hand, since G is a connected simple plane graph with |V| ≥ 3, it follows from Lemma 7.30 that

|E| ≤ 3|V| − 6 (7.4.3)

Combining the equations (7.4.2) and (7.4.3), one has

6|V| ≤ 6|V| − 12,

which is a contradiction. This proves Claim 1.

Then let v be a vertex of degree 5 or less, and let H = G − {v}. By the induction hypothesis, H is 5-colorable.
Hence there exists a vertex 5-coloring ω : V \ {v} → {1, . . . , 5}. If ω uses at most 4 colors for the neighbours
of v, then we can color v by the color that is not used. Thus we let deg(v) = 5 and assume that the neighbours
of v have distinct colors for the rest of the proof.
Let D be an open small disk such that it meets only five edges starting from v and does not contain any other
edges or vertices other than v. Let us label the intersection of those five edges with D according to their cyclic
position in D as s1 , . . . , s5 , and let (v, vi ) be the edge containing si . Without loss of generality, we may assume
that ω(vi ) = i for each i. The purpose of taking D is to examine the behavior of our graph near v, see Figure
7.10.
Let P be any {v1 } − {v3 } path in H − {v2 , v4 }. We define H − P as follows: if VP denote the set of all vertices
contained in P, then H − P := H − VP .
Claim 2 If there exists a {v1 } − {v3 } path P in H − {v2 , v4 }, then there does not exist a {v2 } − {v4 } path in H − P.
Proof for Claim 2
Let C be the cycle vv1 Pv3 v. Note that since G is simple, the cycle C is uniquely determined. It suffices to
show that there does not exist a {v2 } − {v4 } path in G − C. The notation G − C is defined to be G − VC , where

79
 Figure 7.10: The vertex with degree 5

VC is the set of all vertices contained in C. Indeed, if there exists a {v2 } − {v4 } path Q in H − P, then Q is a
{v2 } − {v4 } path in G − C. By taking a contraposition, if there does not exist a {v2 } − {v4 } path in G − C, then
there does not exist a {v2 } − {v4 } path in H − P. Let x2 ∈ s2 and x4 ∈ s4 . Since C is a cycle, which implies
in particular that C has no self-intersection as a closed path in R2 by the property of plane graphs, R2 \ C has
exactly two components: a bounded open set A and an unbounded open set B. Note that strictly speaking,
we are using Jordan curve theorem here. One has x2 ∈ A and x4 ∈ B. Suppose there exists a {v2 } − {v4 } path
in G − C. By the property of plane graphs and {v2 , v4 } ⊆ R2 \ C, (v, v2 ) and (v, v4 ) contribute paths (in the
topological sense) in R2 \ C between x2 and v2 and between x4 and v4 , respectively. Thus there exists a path
in R2 \ C between x2 and x4 . It contradicts x2 ∈ A and x4 ∈ B. This proves Claim 2.
Given i, j ∈ {1, . . . , 5}, let Hi, j be the subgraph of H induced by the vertices colored i or j.
Claim 3 We may assume that H1,3 contains a {v1 } − {v3 } path P in H − {v2 , v4 }.
Proof for Claim 3
Observe first that H1,3 might consist in several components, and we call C1 the component of H1,3 containing
v1 . If the component C1 also contains v3 , then Claim 3 holds. Suppose that the component C1 of H1,3
containing v1 does not contain v3 . If we interchange the colors 1 and 3 at all the vertices of C1 , we obtain
another 5-coloring of H. Then v1 and v3 are both colored 3 in this new coloring, and we may assign color 1 to
v. Thus it suffices to deal with the case where the component C1 of H1,3 containing v1 also contains v3 . This
proves Claim 3.
Then the component C2 of H2,4 containing v2 does not contain v4 . Indeed, if C2 contains v4 , then C2 is a
{v2 } − {v4 } path in H − P since P is contained in H1,3 . This contradicts Claim 2. It means v2 and v4 lie in
different components of H2,4 . If we interchange the colors 2 and 4 in C2 , we obtain a new 5-coloring of H.
Since v4 is not contained in C2 , v2 and v4 are colored 4 in this new coloring. Now v no longer has a neighbour
colored 2. Thus we can assign color 2 to v. This completes the proof for Theorem 7.28. □

Note that Claim 1, proven by Lemma 7.30, was one of the most crucial steps. By Claim 1, one can find a
vertex v that has a degree of 5 and one may assume neighbours of v have distinct colors since one has 5 colors.
If we could show that for any loopless plane graph there exists a vertex v that has a degree of 4 or less, then by
applying the proof for Theorem 7.28, the four color theorem could be proven. However, it is known that there

80
exists a loopless plane graph such that every vertex has a degree of 5 or more, called an icosahedral graph.
Thus the proof for Theorem 7.28 cannot be used to prove the four color theorem.

81
Chapter 8

Directed graphs

In the previous chapters, we presented the theory simultaneously for directed graphs and for undirected graphs.
However, some notions have been more naturally developed for undirected graphs, like the notion of connec-
tivity or the chapter on graph colorings. In this chapter, we focus on directed graphs, study a few applications
and develop some tools specifically for them.

8.1 Strongly connected components

Let us start by recalling that the notion of a connected graph was introduced in Definition 1.17, and that this
notion does not see the orientation on edges of a directed graph. For such graphs, the notion of connectivity
is sometimes called a weak connectivity, in contrast to the strong connectivity introduced in Definition 1.18.
Recall that an oriented graph is strongly connected if there exists a path from x to y, for arbitrary vertices
x and y. With our convention, it goes without saying that all paths on an oriented graph are oriented paths.
However, the strong connectivity of the entire graph is often a requirement which is too strong. In that context,
the following definition is useful.

Definition 8.1 (Strongly connected component). A strongly connected component of an oriented graph G is
a maximal strongly connected subgraph of G. The vertices of a strong component are said to be mutually
reachable.

In other terms, for any vertices x and y in a strong component of a graph G, there exist a least one path from x
to y and one path from y to x. On the other hand, for any x in a strong component and any y not in this strong
component, either there does not exist a path from x to y, or there does not exist a path from y to x, or both do
not exist. A graph with its strongly connected components is provided in Figure 8.1. As emphasized in this
figure, the set of strongly connected components realizes a partition of the vertices of G. On the other hand,
some edges do not belong to any strongly connected components. Based on these observations, one reduction
of the initial graph is quite natural and useful.

Definition 8.2 (Condensation). Let G be a finite directed graph, and let S := {s1 , s2 , . . . , sn } be an enumeration
of its strongly connected components. The condensation of G consists in the simple graph with vertices S and
with edges defined by the following rule: for j , k there exists an edge from s j to sk if one vertex of the
strongly connected component s j in G is linked to one vertex of the strongly connected component sk in G.

82
 Figure 8.1: A directed graph and its strongly connected components

The condensation of the graph of Figure 8.1 is provided in Figure 8.2. Note that a
condensation is always an acyclic directed graph. Indeed, any cycle in a condensation
would mean that some strongly connected components in G would not be maximal.
A directed acyclic graph is often called a dag, see also Figure 3.1.

Let us now look at an algorithm for identifying the strongly connected components Figure 8.2: A dag
of a large graph. Note that there exist several algorithms for this task, as explained
in [27]. Our approach will be based on the depth-first search (DFS) introduced in Section 4.2. The construc-
tion of a tree was provided in Algorithm 4.4, and it is the specific choice of a vertex in Front(G, T i ) which
characterizes the type of algorithm (DFS, BFS, or others).

We start recalling a few concepts for the growth of a tree. The

discovery number function has been introduced in Remark 4.5.
This function provides an index to the vertices according to their
discovery during the algorithm. We also recall that the notions
of skip-edges or cross-edges have been introduced at the end of
Section 4.1. Figure 8.3 illustrates these concepts: the edges 1
and 3 are skip-edges, the former one being a back-edge while
the latter one is a forward-edge. The edge 2 is a cross-edge
since it links two vertices which belong to the tree but none is

83

Figure 8.3: A directed tree

an ancestor of the other one. If the tree is constructed with Algorithm 4.4 following the DFS rule, then the
following result can easily be obtained.
Lemma 8.3. Let e be a cross-edge of a depth-first search tree performed on a directed graph. If the origin
of e is x and the terminal vertex of e is y, with x and y belonging to the tree, then one has dfnumber(x) >
dfnumber(y).
The following proof has been studied and written by some students:

Proof. We are going to prove by contradiction. Assume that there exists a cross-edge e = (x, y) such that
dfnumber(x) < dfnumber(y). After conducting DFS, we obtained the DFS-tree, denoted by T . The cross-edge
e = (x, y) implies that x and y are not in the same “family”, in other words, neither of them is the ancestor of
the other one. This means that there exists a subtree T x of T which contains x but not y and a subtree T y of T
which contains y but not x , together with a vertex a in T being the root of the minimal subtree of T containing
both T x and T y , see Figure 8.4. Among all the roots corresponding to subtrees of T that contains both T x and
T y , the vertex a has the largest depth.
Based on the rules of DFS, since dfnumber(x) < dfnumber(y), one has to finish discovering all vertices in T x ,
then backtrack to a, before proceeding to T y . However, the existence of the edge e, which points from x to
y, means that x is not finished yet, which contradicts to the operation of DFS. Hence, the assumption is not
correct and thus dfnumber(x) > dfnumber(y). □

Figure 8.4: Subtree of T with its root a and both T x and T y

We shall now present an algorithm for identifying the strongly conected components of a graph, following the
approach of [GYA, Sec. 9.5]. A more complete (but longer) presentation is also available in [BG, Sec. 7.5].
For the subsequent algorithm, additional functions have to be introduced. The setting is the construction of a
DFS-tree for a digraph G = (V, E).
(i) For any x ∈ V, the value low(x) corresponds to the smallest discovery number of all vertices which are
known to be in the same strongly connected component as x,
(ii) For any x ∈ V, the binary function placed(x) takes the value TRUE if the vertex x has been placed in a
strongly connected component, while it takes the value FALSE otherwise,
(iii) If x belongs to a tree (and is not the root), parent(x) refers to the parent of x in the tree,

84
 (iv) For any e ∈ E, the binary function examined(e) takes the value TRUE if the edge e has already been
examined (treated), while it takes the value FALSE otherwise,
(v) For any e ∈ E, the value head(e) denotes the target of e, which had been denoted by t(e) in Section 1.1.
Let us also recall that the structure of a stack has been introduced in Section 3.4.4 and illustrated in Figure
3.20b. In the following algorithm, we denote by holdstack a stack which keeps the vertices that have been
processed but which are not placed yet in any strong component. Another stack will be denoted by vertexstack
and will take care of vertices. Before running the algorithm, the initialization of its values is necessary. This
process is described in Figure 8.5. Note that the strongly connected components are simply called strong
components, that vertices are denoted by v, w, and that edges are also called arcs. For coherence, we shall
follow these conventions in the rest of this section.

Figure 8.5: Initialization of the algorithm, from Algorithm 9.5.2 of [GYA]

Before providing the algorithm, let us still describe how the function low is going to be computed. For that
purpose, we shall say that a vertex v is completely processed if all arcs connected to v have been examined. On
the other hand, we shall say that v is active if an arc having v as its origin is currently examined. The values
of the function low will be updated as the algorithm proceeds. Once a vertex is completely processed, one
has low(v) = dfnumber(v) if and only if the vertex v is at the root of a subtree whose vertices form a strongly
connected component. During the process, the value of low(v) will be updated according to the following
rule:
1) If v has been completely processed and if low(v) < dfnumber(v), then one sets

low parent(v) := min low parent(v) , low(v) .



2) If v is active and if the arc being examined is a back-arc from v to an ancestor w of v, then one sets

low(v) := min low(v), dfnumber(w) .



3) If v is active and if the arc being examined is a cross-arc from v to w, then one sets

low(v) := min low(v), dfnumber(w)

85
 if and only if w has not already been assigned to a strongly connected component, namely if and only if
placed(w) = FALS E.
An algorithm for exhibiting the strongly connected components of a directed graph is provided in Figure 8.6.
Observe that this algorithm does not always produce a tree containing all vertices of the initial graph. This
was already observed when the algorithm about the growth of a tree was proposed, without looking at the
strongly connected components. However, once the above algorithm has stopped, one can initiate it again on
G − VT , with VT the set of vertices of the tree. By performing again this algorithm, new strongly connected
components of the remaining part of G can be found.

86
Figure 8.6: Strongly connected component’s algorithm, from Algorithm 9.5.2 of [GYA]

87
8.2 Tournaments
In this section and in the following one, we discuss some applications of directed graphs, and introduce a
few more concepts related to them. Recall that a round-robin tournament or all-play-all tournament is a
competition in which each contestant meets all other contestants in turn. The mathematical counterpart is
provided by the following definition.
Definition 8.4. A tournament is a simple directed graph whose underlying unoriented graph is complete.
One can immediately observe that any tournament is obtained by adding an orientation on all edges of a
complete graph Kn with n vertices. In applications, whenever there is an edge from x to y one says that x
dominates (or beats) y. It is easy to remember this since x → y can also be seen as x > y. According to this
convention, the outdegree of a vertex x corresponds to the score of the vertex x. Note that since the complete
graph Kn has n(n − 1)/2 edges and if we attribute 1 point for each contest between two vertices, then there
exists a total number of n(n − 1)/2 points to be distributed inside the graph.
A special example of a tournament corresponds to a transitive tournament. Before considering them, we
introduce the notion of transitivity for arbitrary directed graphs.
Definition 8.5 (Transitive digraph). A directed graph is transitive if whenever there exists an edge from x to y
and an edge from y to z, then there exists an edge from x to z.
For tournament, transitivity can be expressed by several equivalent properties. We list some of them in the
following statement.
Lemma 8.6. Consider a tournament G = (V, E) with n vertices. Then the following statements are equivalent:
(i) G is transitive,
(ii) G is acyclic,
(iii) G has exactly one Hamiltonian path,
(iv) V admits a strict total ordering,
(v) The sequence of scores attributed to the vertices is (0, 1, 2, . . . , n − 1),
(vi) G does not contain a cycle of length 3.
Transitive tournaments are convenient because they naturally offer a unique
ranking. What about tournaments which are not transitive ? How can one
choose a Hamiltonian path which would correspond to a ranking ? The next Figure 8.7: A transitive
result shows that there always exists a least one Hamiltonian path in any tourna- tournament
ment. The proof (by contradiction) is left as an exercise.
Lemma 8.7 (Rédei, 1934). Any tournament contains at least one Hamiltonian path.
If more than one Hamiltonian path exists, additional work is necessary in order to provide a ranking of the
vertices. One easy solution is to provide a ranking by considering the strongly connected components of the
graph. Recall that the condensation of a directed graph has been introduced in Definition 8.2. Then one has:
Lemma 8.8. The condensation of any tournament is a transitive tournament.
As a consequence, even for tournaments that are not transitive, the strongly connected components of the
tournament are totally ordered. The theory of ranking in tournaments is very well developed and not trivial.

88
A nice account for this theory is provided in [Mo]. We mention below just a few results, starting with the
definition of a king !

Definition 8.9 (A king). In a tournament, a king is a vertex which can reach any other vertex with a path of
length at most 2.

In the next statement, we observe that kings always exist.

Proposition 8.10. Any tournament possesses at least one king.

Proof. The proof is by induction. Clearly, the statement holds if the tournament consists only in two vertices.
So, let us assume that the statement is true for any tournament of n vertices, and let us consider a tournament
G = (V, E) of n + 1 vertices. Let y be any vertex in this tournament, and consider the n vertices tournament
obtained by G − {y}. By assumption, this tournament has a king, which we denote by x. Let D be the set of
vertices of G − {y} containing x and all the vertices dominated by x. Clearly, x reaches all elements of D by a
path of length at most 1 and all the element of V \ D by a path of length 2 (passing through an element of D).
If there exists in D one vertex which dominates y, then x is a king for G. Otherwise, y dominates all elements
of D, and therefore can reach all elements of G − {y} by a path of length at most 2. In this case, y is a king. □

Several results of this type can be found is the seminal paper [Ma] with beautiful illustrations as represented
in Figure 8.8. For example, it is shown that a king is unique if and only if it is an emperor (it dominates all
other vertices). Also it is shown that two kings can not coexist, but more than two can coexist.

Figure 8.8: About the King chicken theorems, picture from [Ma]

Another application of tournaments leads to a rather famous paradox in social choice theory. Very briefly, this
so-called Condorcet paradox occurs because a collective preference can be cyclic, even if the preferences of
individual voters are not cyclic. Let’s be more explicit. A tournament with n vertices can be used to indicate
the preferences between n candidates. This is often realized when candidates are evaluated by pair, with
all possible pairs represented in a tournament. If the tournament is transitive, it means that the candidates are
strictly ordered, but more complicated patterns can also appear. In this framework, each tournament represents
the voting preferences provided by one person. What about the voting preferences of a group of persons ?
N be a family of tournaments of n vertices. The majority digraph
Definition 8.11 (Majority digraph). Let {Gi }i=1
based on this family is a tournament in which an edge is oriented from x to y if x dominates y in a majority of
graphs Gi .

89
Note that for simplicity we have assumed that a majority always exist. This will always be the case if the
N consists in a odd number of tournaments, namely if N is odd. The majority digraph represents
family {Gi }i=1
the preferences obtained over the N individual preferences. If the majority digraph is transitive, then the
outcome of such a selection procedure is rather clear. However, more surprising situation can take place.
For example, assume that N = 3 and that each individual voting preferences are organized as a transitive
tournament. In this case, one can simply represent the graph by an ordered set, with the emperor on the top.
When the majority digraph is drawn, the complexity of the tournament can be much higher. An example of
this situation is represented in Figure 8.9. In this situation, one speaks about the Condorcet paradox because
of the appearance of cycles in the majority graph.

Figure 8.9: 3 individual preferences, and the majority digraph, see Figure 9.3.3 of [GYA]

The paradox can be explained by looking at the cycle generated by the three vertices A, B and C on Figure
8.9. Indeed, a majority of voters prefer A to B, a majority prefer B to C, and a majority prefer C to A. Thus,
if candidate A wins, then a majority of the voters would have been happier if C had won, if candidate C wins,
then a majority of the voters would have been happier if B had won, and if candidate B wins, then a majority
of the voters would have been happier if A had won.
We refer to [28] for other references about social choice theory and for various additional links to applications
of graph theory in social sciences.

8.3 Project scheduling

In this section, digraphs are used for scheduling several activities which are interrelated: some activities have
to be finished before others can start, while other activities are completely independent. Establishing such a
graph helps for a better planing, for minimizing the necessary time for the completion of the project, and for
identifying the key activities which can delay the entire project.
One way to represent such complex activities is to use an activity-on-arc network, or in short AOA network.
In this representation, each directed edge of the graph represents one activity, with the head of the arrow
indicating the direction of progress of the project. A weight on the edge represents the duration of the activity
corresponding to this edge. Each vertex in the AOA network represents an event that coincides with the
completion of one or more activities and with the beginning of new activities. Equivalently, the final vertex
of an edge represents the completion of the activity, while the origin of an edge corresponds to the start of the
activity. If the end vertex of an edge A coincides with the origin of an edge B, we say that the activity A is a
predecessor of the activity B. In particular, it means that B can not start before A is completed. In Figure 8.10

90
different activities are organized. In (a) the completion of A is necessary before the start of B; in (b) A and B
have to be completed before C can start, but A and B are independent; in (c) A has to be completed before the
two independent activities B and C can start.

(a) (b) (c)

Figure 8.10: Three AOA-networks

Let us now fix some rules when establishing an AOA network. Clearly, the graph corresponding to the network
should be acyclic, otherwise none of the activities will ever start. In addition, we shall require that there is a
unique start (with indegree 0) and a unique end (with outdegree 0). Additional requirements are:

(i) Vertex 1 corresponds to the start of the project, while vertex N corresponds to its end,

(ii) Each activity with no predecessor is represented by an edge starting at the vertex 1,

(iii) Vertices are labeled with elements of N chosen such that for each edge, the initial vertex has a label
which is smaller than the label of its end vertex,

(iv) Each activity is represented only by one edge in the network,

(v) The graph is simple and finite.

Note that in order to satisfy the rules imposed above, it is sometimes nec-
essary to add a dummy activity which does not take any time. For example,
if A and B can be performed simultaneously, with the same initial vertex
and the same final vertex, then it is necessary to introduce an activity with Figure 8.11: Dummy activity
a zero weight, as shown in Figure 8.11. Also, since the graph is simple,
edges can be indexed without ambiguity by the labels of their endpoints. Thus, any edge will be denoted by
(i, j) with i ∈ N corresponding to the label of the vertex at the origin of the edge, and j ∈ N corresponding to
the label of the vertex at the end of the edge. By the convention imposed in the above rules, one has i < j.

Let us now set a few notations: the indices i, j ∈ N correspond to labels on vertices.

(i) ω(i, j) denotes the weight on the edge (i, j) (the duration of the corresponding activity),

(ii) ET(i) denotes the earliest time at which the event corresponding to vertex i can occur,

(iii) LT(i) denotes the latest time at which the event corresponding to vertex i can occur without delaying
the completion of the project,

(iv) pred( j) denotes the vertices preceding j, which means the set of vertices i for which there exists an edge
(i, j). These vertices are called the immediate predecessors of the vertex j,

(v) succ(i) denotes the vertices following i, which means the set of vertices j for which there exists an edge
(i, j). These vertices are called the immediate successors of the vertex i.

91
By convention, one sets ET(1) = 0. In addition, the following recursive formula always holds:

ET( j) := max {ET(i) + ω(i, j)} (8.3.1)

i∈pred( j)

which means simply that the activities starting at j can take place only when all preceding activities are
finished. Clearly, the following result holds:
Lemma 8.12. In an AOA network, the earliest time ET(i) is given by the length of the longest path from vertex
1 to vertex i.
In the rest of this section we provide some simple algorithms for computing quantities in an AOA network. The
setting will always be the same: an AOA network with N vertices. Note that these algorithms use implicitly
the fact that any acyclic and finite directed graph possesses a least one vertex with indegree 0 and one vertex
with outdegree 0. The first algorithm provides the earliest time for every vertex, with the convention that
ET(1) = 0.
Algorithm 8.13 (Earliest event time). Let G = (V, E) be an AOA network.
(i) Set ET( j) = 0 for any j ∈ {1, . . . , N}.
(ii) For i ∈ G with degin (i) = 0, and for each j ∈ G with (i, j) ∈ E, set

ET( j) := max{ET( j), ET(i) + ω(i, j)}.

Set G := G − {i}.
(iii) Repeat (ii) until G = Ø.
(iv) Return ET(1), ET(2), . . . , ET(N).
The next algorithm provides the latest event time. Its computation is rather sim-
ilar to the computation of the earliest time, but it goes backward. The necessary
convention is that LT(N) = ET(N). In order to understand the algorithm, con-
sider a vertex j which is a immediate successor of a vertex i, see Figure 8.12. If
the event corresponding to vertex i occurs after LT( j) − ω(i, j), then event j will Figure 8.12: Immediate
occur after LT( j), thereby delaying the completion of the project. Since this is successor
true for any immediate successor of i, LT(i) is the minimum of these differences
taken over all immediate successors of i. This leads to a relation similar to (8.3.1) and which reads

LT(i) = min {LT( j) − ω(i, j)}. (8.3.2)

j∈succ(i)

Based on this relation, one infers the following algorithm:

Algorithm 8.14 (Latest event time). Let G = (V, E) be an AOA network, and let T be the earliest completion
time.
(i) Set LT( j) = T for any j ∈ {1, . . . , N}.
(ii) For j ∈ G with degout ( j) = 0, and for each i ∈ G with (i, j) ∈ E, set

LT(i) := min{LT(i), LT( j) − ω(i, j)}.

Set G := G − { j}.

92
 (iii) Repeat (ii) until G = Ø.
(iv) Return LT(1), LT(2), . . . , LT(N).
By using the previous two concepts, namely the earliest time ET and the latest time LT, one can introduce more
more useful concept: the total float. For the activity on the edge (i, j), the total float TF(i, j) corresponds to the
amount by which this activity can be increased without delaying the full project. Equivalently, it corresponds
to the amount of time the start of the activity (i, j) can be delayed without having an effect on the project.
Knowing this information is an important issue since it might allow to start this activity at an optimal time
during a certain interval of time. Once the previous two algorithms have been performed, one can directly
compute the total float. The proof of the following statement is easy, see also [GYA, Prop. 9.4.3].
Lemma 8.15. The total float for the activity (i, j) is given by

TF(i, j) = LT( j) − ET(i) − ω(i, j).

Let us conclude this section with one more remark. Clearly, a critical activity is one activity for which the
total float is 0. Accordingly, any path in the graph from the vertex 1 to the vertex N made of critical activities
is called a critical path. Such paths are the longest ones in the graph, and dictate the duration of the entire
project. Usually, such paths are not unique.

93
Chapter 9

Flows

In this chapter we continue the investigations on directed graphs.

9.1 Capacity, flows and cuts

For shortness, a finite directed and loopless graph G = (V, E) will simply be called a network. We start by
introducing a few definitions related to arbitrary networks. First of all and in relation with the indegree and
the outdegree functions, let us define two natural notions.
Definition 9.1 (In and out sets). For any vertex x of a network G = (V, E) we set in(x) := {e ∈ E | t(e) = x}
and out(x) = {e ∈ E | o(e) = x}.
In other terms, in(x) corresponds to the set of edges targeting x, while out(x) corresponds to the set of edges
leaving x. Clearly, the cardinality of the first set is degin (x) while the cardinality of the second set is degout (x).
Let us also introduce a rather convenient notation which is somehow related to the A-B-path introduced in
Definition 5.5. Let G = (V, E) be a network and let A, B be two subsets of V. For any e ∈ E we set

e ∈ (A, B) ⇐⇒ o(e) ∈ A and t(e) ∈ B. (9.1.1)

In other words, e ∈ (A, B) means that the edge e starts in A and ends in B. Observe that for this definition, it is
not necessary that A and B are disjoint, of even different. In the sequel, special pairs of subsets of V will play
an important role. For that reason, for any U ⊂ V we write U c for V \ U. Clearly, U and U c define a partition
of V. In this case relation (9.1.1) reads

e ∈ (U, U c ) ⇐⇒ o(e) ∈ U and t(e) < U.

From now on we shall consider networks with two distinguished vertices s and t satisfying degout (s) , 0 and
degin (t) , 0 (and impose that s , t). Such networks are called st-networks6 , see Figure 9.1. Note that the
AOA networks introduced in Section 8.3 are special instances of st-network. The two distinguished vertices
are usually called the source and the sink (or target). If G is a st-network, any pair (U, U c ) with s ∈ U and
t ∈ U c is called a cut of G. Special examples of cuts are {s}, {s}c ≡ {s}, V \ {s} and {t}c , {t} ≡ V \ {t}, {t} .

6
It is sometimes required that degin (s) = 0 and that degout (t) = 0, but this is not strictly necessary. However, by adding new vertices,
one can always come back to this situation. Also, networks with multiple sources and multiple sinks can easily be transformed into a
network with a single source and a single sink.

94
 Figure 9.1: st-network with cut
From now on, we shall endow the edges of the net-
work with weights. In the present context, an edge
weight ω : E → [0, ∞) is called capacity function,
or simply a capacity, and is denoted by the letter c,
see Figure 9.2. We also introduce a second type of
functions on edges. Note that these functions have
some relations with the capacity function.
Definition 9.2 (Flow). Let G = (V, E) be a st- Figure 9.2: st-network with capacity
network endowed with a capacity c. A flow on G is a function f : E → R+ satisfying the following conditions:
(i) f (e) ≤ c(e) for any e ∈ E,
(ii) For any x ∈ V with x < {s, t} one has the conservation constraint
X X
f (e) = f (e). (9.1.2)
e∈in(x) e∈out(x)

The equality (9.1.2) is also called the conservation of flow. It is a requirement which naturally appears in
several applications. It prevents the accumulation of the quantity represented by f at any vertex.
Let us now come back to two subsets A, B of V. For any capacity or any flow on G we set
X X
c(A, B) := c(e) and f (A, B) := f (e).
e∈(A,B) e∈(A,B)

In particular, it follows from the conservation constraint that for any x ∈ V with x < {s, t} one has
X X
f {x}, {x}c = f {x}, V = f (e) = f (e) = f V, {x} = f {x}c , {x} .





(9.1.3)
e∈out(x) e∈in(x)

In the special case of a cut (U, U c ), the quantity c(U, U c ) is also called the capacity of the cut (U, U c ).
So far, the source s and the sink t of the st-network have not played a special role. The next definition is
related to them:
Definition 9.3 (Value of a flow). Let G = (V, E) be a st-network endowed with a capacity c, and let f be a
flow on G. We define the value val( f ) of the flow f , also denoted by | f |, by
X X
val( f ) := f (e) − f (e).
e∈out(s) e∈in(s)

Clearly, this definition put more emphasize on the source s than on the sink t. We shall see later on that this
asymmetry is not a real one. The next statement is of central importance in our framework.

95
Proposition 9.4. Let G = (V, E) be a st-network endowed with a capacity c, let f be a flow on G, and let
(U, U c ) be any cut of G. Then, one has
val( f ) = f (U, U c ) − f (U c , U) ≤ c(U, U c ). (9.1.4)

Before the proof, observe that (9.1.4) contains two pieces of information. The first one is about the invariance
of the expression f (U, U c ) − f (U c , U) for any cut (U, U c ). The second one is that val( f ) is dominated by the
capacity of any cut (U, U c ).

Proof. From (9.1.3) one infers that for any x ∈ U \ {s} one has f {x}, V − f V, {x} = 0. Thus,



X X
val( f ) = f (e) − f (e)
e∈out(s) e∈in(s)

= f {s}, V − f V, {s}



Xn
o
=


f {x}, V − f V, {x}
x∈U
= f (U, V) − f (V, U)
= f (U, U) + f (U, U c ) − f (U, U) − f (U c , U)
= f (U, U c ) − f (U c , U)
which provides the equality in the statement. For the inequality, observe that
f (U, U c ) − f (U c , U) ≤ c(U, U c ) − f (U c , U) ≤ c(U, U c ) (9.1.5)
since f (U c , U) ≥ 0. This inequality corresponds to the one of the statement. □

By choosing U = {t}c , one directly gets

val( f ) = f {t}c , {t} − f {t}, {t}c



X X
= f V, {t} − f {t}, V =



f (e) − f (e).
e∈in(t) e∈out(t)

Thus, the following statement corrects the apparent asymmetry of Definition 9.3 :
Corollary 9.5. In the previous setting, one has val( f ) = e∈in(t) f (e) − e∈out(t) f (e).
P P

There is an other important consequence of Proposition 9.4 which has to be emphasized. The value val( f ) is
always smaller than or equal to the capacity of any cut (U, U c ). In particular, it means that
val( f ) ≤ min c(U, U c ) | U ⊂ V with s ∈ U and t ∈ U c .


For that reason, it is natural to call a subset U ⊂ V realizing this inequality a minimum cut of the network.
Such a cut will be denoted by U ∗ , (U ∗ )c .

In the sequel we shall look for a maximal flow f ∗ , which means a flow on G which satisfies val( f ) ≤ val( f ∗ )
for any flow f on G. It follows from the previous observations that the inequality
val( f ∗ ) ≤ c U ∗ , (U ∗ )c

always holds. In addition, if for some flow f and some cut (U, U c ) one has val( f ) = c(U, U c ), then it turns out
that f is a maximal flow, and that (U, U c ) is a minimal cut. Observe finally that (9.1.5) provides a condition
for a flow to be maximal. Indeed, suppose that there exist a flow and a cut (U, U c ) satisfying f (e) = c(e)
for any e ∈ (U, U c ) and f (e) = 0 for any e ∈ (U c , U), then the inequalities in (9.1.5) are saturated, and one
deduces that f is a maximal flow and that (U, U c ) is a minimum cut.

96
9.2 Maximum flow problem
In this section, we look for the maximal flow on a given st-network endowed with a capacity c. The simplest
solution for increasing a flow f is through a single st-path in the network. Indeed, suppose that there exists
a path from s to t satisfying the condition ϵ := min{c(e) − f (e)} > 0, where the minimum is taken over all
edges of the path. Then the flow fϵ defined by fϵ (e) = f (e) + ϵ if e belongs to the st-path, and fϵ (e) = f (e)
otherwise, is a new flow on G. Indeed, it is easy to check that the conservation constraint is still satisfied for
the new flow. A representation of this situation is provided in Figure 9.3. In the first picture, the values of the
flow and of the capacity are represented with the notation flow/capacity7 . In the second picture, a st-path with
ϵ = 1 is presented. Note however that this simplest solution is rarely the best one. Its weakness is that a single
path is considered, while a network usually admits several st-paths.

(a) (b)

Figure 9.3: Flow increasing through one path, from [29]

Before developing some tools for the search of a maximal flow, it is natural to wonder if such a flow exists ?
The answer is yes as long as the capacity takes integer values. More precisely, the following statement holds:

Theorem 9.6 (Max-flow Min-cut theorem). In every st-network with integer-valued capacity function there
exists a maximal flow which is also integer-valued.

This theorem is due to Ford and Fulkerson and a proof can be found in [Die, Thm. 6.2.2]. An extension to
capacities with values in the set of rational numbers is easy (just multiply by a sufficiently large integer to
be back to the integer-valued setting). On the other hand, for irrational capacities, the convergence of the
algorithm to a maximal flow might fail.

In order to extend the construction mentioned above with one st-path, let us introduce a generalization of a
path.

Definition 9.7 (st-quasi path). In a st-network a st-quasi path or st-semi path is a path on the underlying
undirected graph which starts at s and ends at t.

When considering such a quasi path, the edges can be divided into two families: the ones going in the direction
of the path, and the ones going backward. Accordingly, they are called forward edges or forward arcs, and
backward edges or backward arcs.

Consider now a flow on a st-network endowed with a capacity. We shall say that a st-quasi path is f -
augmenting if f (e) < c(e) for any forward edge e on the path, and f (e) > 0 on any backward edge e on
7
Note that different authors use different notations for representing the flow and the capacity. One easily finds out who is who
since the inequality f (e) ≤ c(e) always holds.

97
 Figure 9.4: 3 forward edges, 2 backward edges

the path. In particular, if one sets


c(e) − f (e)
 if e is a forward edge
∆e = 

 f (e)
 if e is a backward edge

then ∆e > 0 for any f -augmenting st-quasi path. The quantity ∆e is called the slack on edge e. So far, this
quantity has been computed on each edge individually. However, for the conservation of the flow, one can not
change the flow on edges independently, and one has to consider a path as a whole. For that reason, for any
f -augmenting st-quasi path P let us set

∆P := min{∆e | e ∈ P}.

Note that this notion corresponds to the value ϵ introduced at the beginning of this section for an oriented
st-path, and corresponds to the value 1 on the blue path in Figure 9.3. By two minutes of thought one easily
infers the following result:
Lemma 9.8. Let G = (V, E) be a st-network endowed with a capacity c, let f be a flow on G, and let P be a
f -augmenting st-quasi path. Let us set




 f (e) + ∆P if e is a forward edge of P
f (e) − ∆P if e is a backward edge of P .

fP (e) := 




 f (e)

otherwise

Then fP is a new flow on G, and val( fP ) = val( f ) + ∆P .

In addition to the previous result, one can also infer that a flow is maximal if and only if there does not exist
any f -augmenting st-quasi path. A proof of this statement is presented in [GYA, Thm. 10.2.3]. Putting the
information obtained so far, one has essentially proved Theorem 9.6. However, the missing information so far
is how do we find f -augmenting st-quasi path ? Indeed, once such a quasi path has been identified, Lemma
9.8 provides us with an increased flow.
There exist several algorithms for identifying f -augmenting st-quasi paths, which are more or less compli-
cated, but also less or more time consuming. We provide only the one of Edmond and Karp, based on the
early solution provided by Ford and Fulkerson. The main idea for is to construct a tree starting at s. Once the
sink t is reached, one uses the path between s and t as a st-quasi path.
Recall firstly that the algorithm for constructing a tree has been provided in Algorithm 4.4. When growing the
tree, the elements of Front(G, T i ) play a crucial role. For unoriented graphs, Front(G, T i ) consists of edges with
one endpoint in T i and one endpoint outside of T i . In the current application, we shall consider Front(G, T i )
consisting of two types of edges e:
(i) o(e) ∈ T i , t(e) < T i , and c(e) − f (e) > 0,
(ii) o(e) < T i , t(e) ∈ T i , and f (e) > 0.

98
Such edges are usually called usable. They are clearly related to the forward and backward edges in the final
st-quasi path. The choice of an edge inside Front(G, T i ) will then be performed following the breadth-first
search, namely the frontier edge ei+1 ∈ Front(G, T i ) is chosen with a tree endpoint at x j with the minimal
number j (starting from j = 0 and then upward).
The following algorithm puts these ideas together. Note that a function backpoint : V → V is used during the
implementation.
Algorithm 9.9 (Finding a f -augmenting st-quasi path).
(i) Set T 0 := {s} and fix i := 0,
(ii) In Front(G, T i ), choose the edge ei+1 with tree endpoint x j with the minimal number j, set xi+1 as the
non-tree endpoint of ei+1 , define backpoint(xi+1 ) := xi , set T i+1 = T i ⊔ {ei+1 }, and set i := i + 1,
(iii) Repeat (ii) until t ∈ T i or until Front(G, T i ) = Ø,
(iv) If t ∈ T i , reconstruct the f -augmenting st-quasi path starting from t and using the information contained
in backpoint, while if Front(G, T i ) = Ø, then (T i , T ic ) is a minimum cut.
Note that one has to be slightly careful in the above algorithm since it provides a st-quasi path, and not a
st-path. This implies that xi+1 corresponds sometimes to o(ei+1 ) and sometimes to t(ei+1 ). This depends on
the type of usable edge ei+1 . Also, if the tree does not reach t, it means that the flow f is already a maximal
flow, and therefore the algorithm can be used for exhibiting a minimal cut.
As a final remark, by combining Lemma 9.8 and the previous algorithm one easily gets a maximal flow on
any st-network endowed with an integer-valued capacity. It is enough to start with a flow f identically equal
to 0, find a f -augmenting st-quasi path with the algorithm, update the flow, and iterate the process again.
We illustrate the construction in Figure 9.5. In these figure, A is the source, G is the sink, and the notation
flow/capacity is used. The final value val( f ∗ ) of the maximal flow is 5. Note that the increase of the length of
the paths is due to the choice of the bfs algorithm. At every step one looks for the shortest possible path.

9.3 Applications
In this section we briefly sketch a few applications of the results obtained in the previous section.

9.3.1 Flow and Menger’s theorem

The first application of the Max-flow Min-cut theorem provided in Theorem 9.6 is usually dedicated to the
proof of Menger’s theorem, both for oriented and unoriented graphs, see Section 5.2. We shall not present the
construction here, but refer for [GYA, Sec. 10.3]. We only provide two statements which can be easily proved
and which might be useful later on. Recall that the notion of internally disjoint paths has been introduced in
Definition 5.3 and was related to the absence of common vertices in different paths. Similarly, edge-disjoint
paths correspond to paths which do not share any common edge.
Lemma 9.10. Let G = (V, E) be a st-network satisfying the three conditions:

degout (s) − degin (s) = m = degin (t) − degout (t)

for some m ∈ N∗ , and degin (x) = degout (x) for all x ∈ V \ {s, t}. Then there exist m edge-disjoint st-paths in G.

99
 (a) Initial network (b) Path with ∆P = 1

(c) Path with ∆P = 2 (d) Path with ∆P = 1

(e) Quasi path with ∆P = 1

Figure 9.5: Construction of a maximal flow, figures from [30]

Proposition 9.11. Let G = (V, E) be a st-network endowed with a constant capacity c = 1. Then val( f ∗ ) for
a maximal flow in G is equal to the number of edge-disjoint st-paths in G

9.3.2 Matching
Recall that the notion of a matching has been introduced in Definition 6.4 and corresponds to a set of edges
having no common endpoints. If e belongs to a matching M and has endpoints x and y, we also say that x
is matched with y by M. For a given graph, we speaks about a maximum matching if the matching contains
the greatest possible number of edges. A problem which appears quite frequently is to look for a maximum
matching in a bipartite graph, see Figure 9.6. How many edges are contained a maximum matching ?
Let us transform this problem into a maximal flow problem, as solved in the previous section. Let G = (V, E)
be the initial bipartite graph with bipartition subsets V s and Vt , and let us construct a st-network G′ = (V ′ , E ′ )
based on G as follows:
(i) V ′ := V ⊔ {s, t},
(ii) The set E ′ consists of three types of oriented edges: one oriented edge from s to each vertex of V s , one

100
 Figure 9.6: Looking for a maximum matching in a bipartite graph

oriented edge from V s to Vt for each edge of E, one oriented edge from each vertex of Vt to t,
In addition, we consider G′ endowed with the constant capacity c = 1. A representation of this construction
is provided in Figure 9.7.

Figure 9.7: The construction of a st-network

Once this st-network with capacity c = 1 is available, tools from the previous section can be used. The
relation between the maximal flow problem, and the current maximum matching is established in the following
statement, see [GYA, Prop. 10.4.1] for a proof.
Proposition 9.12. Let G be a finite bipartite graph, and let G′ be the st-network constructed from G as
mentioned above. Then there is a bijective relation between integer-valued flows on G′ and matching in G. In
particular, f ∗ is a maximal flow if and only if val( f ∗ ) corresponds to the number of elements of a maximum
matching.
With this result at hand, one can now apply the Algorithm 9.9 for constructing a maximal flow f ∗ . Once done,
the edges in a maximum matching if obtained by keeping all e ∈ E ⊂ E ′ with f ∗ (e) = 1.

9.3.3 Transversals
Another application of the maximal flow problem is related to the transversal problem.
Definition 9.13 (Transversal). Let A be a finite set, and let F = {S 1 , . . . , S r } with S j ⊂ A be a finite family
of subsets of A. A transversal for F is a sequence T = (a1 , . . . , ar ) with a j ∈ S j and a j , ak for any
j, k ∈ {1, . . . , r} and j , k.
In other terms, a transversal consists in choosing one element in each subset S j such that the r chosen elements
are different. Fortunately, the problem of finding a transversal can be reformulated in terms of a bipartite graph
and a matching problem. Indeed, let us define the bipartite graph G = (V, E) with bipartition subsets VF and

101
VA defined by VF = {S 1 , . . . , S r } and VA = A. Note that in this definition, S j is just considered as a vertex,
it is not considered as a set containing other elements. We also define e ∈ E with endpoints S j ∈ VF and
a ∈ VA whenever a ∈ S j . Then, finding a transversal corresponds to finding a matching in this bipartite graph.
Figure 9.8 corresponds to the transposition of the initial problem (5 persons interested in 6 gifts, but with some
preferences) into a bipartite graph. Obviously, one is interested in the situation when all elements of VF are
enpoints of the edges in the matching. For that purpose, the next definition is natural:

Figure 9.8: Looking desperately for a transversal, from [31]

Definition 9.14. Let G be a bipartite graph with bipartition subsets V1 and V2 . A matching M in G is V1 -
saturated if each vertex of V1 are endpoints of the edges in M.
It follows clearly from this definition that if the matching M is V1 -saturated, then the cardinality of M and of
V1 should be equal. An example of a VF -saturated matching is provided in Figure 9.9.

Figure 9.9: A VF saturated bipartite graph

Once the initial problem has been recast in the framework of a bipartite graph, the tools developed before can
once again be used. However, there is one important issue: when is it possible to find a VF -saturated matching.
Or equivalently, when is it possible to find a transversal ? The following theorem provides a necessary and
sufficient condition. It is stated in the framework of bipartite graph, but its transposition to the initial problem
is straightforward. For its statement, recall that the set N(x) of neighbours of the vertex x has been introduced
in Definition 1.4 and corresponds to the set of all vertices connected to x. For a subset U ⊂ V of vertices, we
set N(U) for the set of all vertices which are connected to at least one element of U.
Theorem 9.15 (Hall’s theorem for bipartite graphs). Let G be a finite bipartite graph with bipartition subsets
V1 and V2 . Then G has a V1 -saturated matching if and only if for any subset U of V1 one has |U| ≤ |N(U)|,

102
where |U| and |N(U)| denote the cardinality of these sets.
A proof of this theorem is provided in Section 9.3.4. It uses the theory of maximal flow developed in the
previous section. For our initial transversal problem, it means that a transversal exists if the union of any k
different subsets S j contains at least k distinct elements of A.

9.3.4 Hall’s marriage theorem

This section has been studied and written by some students.
The marriage theorem, proved in 1935 by Philip Hall, answers the following question, known as the marriage
problem: if there is a finite set of girls, each of whom knows several boys. Under what conditions can all the
girls marry the boys in such a way that each girl marries a boy she knows? For example, if there are four girls
{g1 , g2 , g3 , g4 } and five boys {b1 , b2 , b3 , b4 , b5 }, and the friendship are shown below, then a possible solution is
for g1 to marry b4 , g2 to marry b1 , g3 to marry b3 , and g4 to marry b2 .

Theorem: A necessary and sufficient condition for a solution of the marriage problem is that each set of k
girls collectively knows at least k boys, for 1 ≤ k ≤ m.

Proof. The necessity is clear, so we can concentrate on the sufficiency.

Let the girls be g1 , g2 , g3 , . . . , gn , and the boys be b1 , b2 , b3 , . . . , bm , with m ≥ n. The relation between a girl
and a boy and whether they know each other constructs a bipartite graph V = V1 ∪ V2 where V1 is the set of
vertices g1 , g2 , . . . , gn , V2 is the set of vertices b1 , b2 , . . . , bm , and there exists an edge of G between gi and b j
if the girl gi knows the boy b j . In this way, we construct a simple bipartite graph.
Let A is a subset of V1 . Denote P(A) for the subset of V2 that all the edges from A to V2 have an endpoint
in P(A), and each vertex in P(A) has an edge connected to a vertex in A . Let |A| represent the number of
elements contained in the subset A. Then, proving the necessity is to proving that if any A subset of V1
satisfies |A| ≤ |P(A)|, then there is a complete matching from V1 to V2 , namely any gi is connected with a
different b j . Thus, assume that

|A| ≤ |P(A)|

for any subset A of V1 .

Let us add to G a vertex of v adjacent to (and only to) every vertex in V1 and a vertex w adjacent to (and only to)
every vertex in V2 . Menger’s theorem says that if S is a vw-separating set, then |S | ≥ # internalydisjoint path form v to w.

103
(here, # means “the number of”). Clearly, |V1 | ≥ #internally disjoint path from v to w because V1 is a vw-
separating set.
Let S = A ∪ B be a v-w separator in which A is a subset of V1 and B is a subset of V2 . Then |S | ≥
#internally disjoint path from v to w by Menger’s theorem. Clearly, (V1 − A) and (V2 − B) are not connected
with each other by any edge since if they are connected by some edges to each other, then A ∪ B = S would
not be a separator of v-w. Thus, P(V1 − A) is a subset of B since V1 − A is connected with vertices in V2 but
not in V2 − B as we argued above.
With our assumption, we obtain that

|V1 − A| ≤ |P(V1 − A)| ≤ |B.|

As |S | = |A| + |B| (A subset of V1 and B subset of V2 are disjoint),

|S | ≥ |A| + |V1 − A| = |V1 |.

From the above relations, we have

|V1 | ≥ #internally disjoint path from v to w

|S | ≥ #internaly disjoint path from v to w by Menger’s theorem.
|S | ≥ |V1 |

Thus, we get the total relation:

|S | ≥ |V1 | ≥ #internally disjoint path from v to w.

But Menger’s theorem says that |S |min = max(#internally disjoint path from v to w). Thus, |S |min = |V1 | =
max(# internally disjoint path from v to w). Therefore, |V1 | = max(#internally disjoint path from v to w. This
means there exists a set of |V1 | internally disjoint paths from v to w in which each path includes a different
vertex in V1 and a different vertex in V2 from any other path in order to satisfy the internally disjoint condition.
Thus, we have the perfect matching from this set of internally disjoint paths. □

104
Chapter 10

Random graphs: the G(n, p) model

In this chapter we touch the surface of random graphs, much more could and should be said. We also do it
without requiring any real prerequisite in probability theory, and for that reason several arguments will only
be sketched.
Let us start by recalling some notations. For any p ∈ N we set

p! := p · (p − 1) · (p − 2) . . . 2 · 1
  p!
for the factorial of p. Also, for any two positive integers p and q with p ≥ q we set qp := q!(p−q!) for
the binomial coefficients. This number represents the number of ways to choose an (unordered) subset of q
elements from a fixed set of p elements. This number can also be written

p · (p − 1) · (p − 2) . . . (p − q + 1)
!
p
= .
q q · (q − 1) · (q − 2) . . . 2 · 1
 
In particular, the number 2p will often appear, and is equal to 21 p(p − 1). One can also observe that it
corresponds to the number of elements in the upper (of lower) half of a square p × p matrix once the diagonal
has been eliminated.

10.1 Basic results

The Gilbert-Erdős-Rényi model for random graphs is certainly the simplest, most natural and most studied
model. It is often simply called random graphs, but also Poisson random graphs or Bernoulli random graphs8 .
Since other models of random graphs exist, we shall use the name Gilbert-Erdős-Rényi model in honor of the
authors who introduced and popularized the model in late 1950s and early 1960s. Note that for this section
we shall mainly follow the approach proposed in Chapter 11 of [Ne], and borrow several pictures from this
reference.
The Gilbert-Erdős-Rényi model is often denoted by G(n, p)9 . The idea behind this notation is the following:
for any n ∈ N we consider n fixed vertices. Then, the number p ∈ [0, 1] represents the probability that an
8
The name Bernoulli comes from the fact that the existence of an edge follows a Bernoulli distribution. The reason for Poisson
will appear later on.
9
There exists a variant of this model, denoted by G(n, m) where the number m of edges is fixed. We shall not consider it here, see
[32].

105
edge between two vertices exists. It is assumed that the graphs are simple (no loop, no multiple edge) and
unoriented, and that the existence of any edge is independent of the existence (or non-existence) of any other
edge. Thus, given two distinct vertices x j and xk , the probability that there exists an edge between them is p,
no matter if other edges have x j or xk as endpoints (but not both) and no matter if other edges exist between
the other vertices, see Figure 10.1. For the time being, we shall consider a fixed p, but this parameter could
also depend on other quantities, and could depend for example on n, see Remark 10.1.

Figure 10.1: Three elements of G 10, 12

Observe firstly that there exists n2 distinct pairs of vertices between n vertices, when (x j , xk ) and (xk , x j ) with


j , k are identified, and when (x j , x j ) are disregarded. It thus follows that in G(n, p), any graph G with m
edges has a probability to appear given by
n
P(G) = pm (1 − p) 2 −m . (10.1.1)
Indeed, it is necessary that m edges are present and n2 − m edges are absent. Note that many of these graphs


could be isomorphic, as introduced in Definition 2.8. On the other hand, if vertices are considered with
labels, or equivalently endowed with different weights, then none of these graphs are isomorphic as labeled or
weighted graphs.
One information which can be directly deduced from (10.1.1) is the distribution of graphs having m edges,
namely:
n

! n
P ∥G∥ = m = 2
pm (1 − p) 2 −m


(10.1.2)
m
where the notation ∥G∥ for the number of edges of G has been introduced in Definition 1.3. For information,
this function m → P ∥G∥ = m corresponds to the binomial distribution B n2 , p . A representation of B(n, p)




is provided in Figure 10.2.
Let us now compute some quantities related to the family of graphs G(n, p). In that respect, we should not
think anymore about the realization of a single graph, but about generic properties of all graphs in G(n, p),
which means all graphs of n vertices, with an arbitrary number m of edges. The only condition for each edge
is its probability p of existence. As an example of such quantity, what is the average number of edges among


all these graphs ? This average will be denoted E ∥G∥ and can be easily computed. Indeed, for a single pair
of vertices, this average is p, which implies that it is n2 p for any graph (recall that each graph contains n2



distinct pair of vertices). As a consequence,
!
n 1
E ∥G∥ = p = n(n − 1)p.


(10.1.3)
2 2

106
 Figure 10.2: The Binomial distributions B(n, p)

From this number, one can directly deduce the average degree (or mean degree) for each vertex. Indeed, this
mean degree is given by 2E ∥G∥ /n, the factor 2 coming from the fact that each edge has two endpoints. In


summary, for any vertex x of the graph,
1
c := E deg(x) = 2 n(n − 1)p/n = (n − 1)p.


(10.1.4)
2
Note that we shall simply denote this quantity by c, and that it will play an important role in the sequel.
Remark 10.1. By looking carefully at (10.1.4) one observes that a fixed p can not always be a good idea.
Indeed, if p is fixed and if we consider a sequence of graph in G(n, p) with n growing, then the average number
of vertices at each vertex will grow with n. This is not a really natural situation, and a constant c is much
more preferable. For a constant average degree c it is thus necessary that p = n−1 c
, or roughly p = nc . Note
however that one could be more general by considering p (or c) having a more complicated dependence on n,
and one is naturally led to the notion of sparse or dense graphs.
The above information is an average over all individual degrees. It is also interesting to know the distribution
of these degrees, namely the ratio of the number of vertices having a degree k among all possible degrees.
 and not to the other n − k − 1
For any vertex x, the probability that this vertex is connected to k other vertices
remaining ones is given by pk (1 − p)n−p−1 . In addition, since there are n−1 k ways to choose these k vertices,
one obtains the probability that deg(x) = k:
!
n−1 k
P deg(x) = k = p (1 − p)n−k−1 .


(10.1.5)
k

Observe that deg(x) follows also a binomial distribution, see Figure 10.2.
It is natural to wonder if a simpler expression for P deg(x) = k can be obtained in the limit n → ∞. This is


indeed possible if the average degree c defined in (10.1.4) remains constant, see Remark 10.1. Indeed, if we
set p = (n−1)
c
, it then turns out that

n→∞ ck
P deg(x) = k −→ e−c . (10.1.6)
k!
We shall not prove it but the main idea is the following. By setting p = (n−1)
c
on the r.h.s. of (10.1.5) and by
considering some approximations for n large, then one infers the above expression as n → ∞. It should be

107
mentioned that this expression corresponds to a Poisson distribution, and this is why this model is also called
the Poisson random graphs: it refers to the Poisson distribution taken by the degree function, see also Figure
10.3.

Figure 10.3: The Poisson distribution, for different value of c.

Let us provide two additional results which can be proved with similar arguments. Proofs are given in [Die,
Sec. 11.1]. For the first one we recall that the notion of independent vertices has been introduced in Definition
2.17 and corresponds to vertices which are not related by any edge. In particular, The independence number
α(G) of a graph G corresponds to the number of vertices of a largest independent set in G.
Proposition 10.2. For any integers n ≥ k ≥ 2 and for any G ∈ G(n, p), the probability that α(G) ≥ k is upper
estimated by
!
n k
 
P α(G) ≥ k ≤ (1 − p) 2 .


k

The next result is about k-cycles, namely closed

paths of length k. How many of them can one expect
in any G ∈ G(n, p) ? The next statement is about
this expectation, or in other words about the aver-
age number of k-cycles in G. For the statement, we
introduce the Pochhammer symbols or Pochhammer
functions: for x ∈ R and n ∈ N one sets

(x)n = x(x − 1)(x − 2) . . . (x − n + 1)

with the convention that (x)0 = 1.

Proposition 10.3. For any integers n ≥ k ≥ 3 one
has
(n)k k
E(k-cycles) = p.
2k
Figure 10.4: Pochhammer’s functions (x)n
108
10.2 Components
So far in these notes, most graphs were considered connected, and if not the analysis was performed indepen-
dently on each connected component. The notion of connectivity was also discussed in Chapter 5. For random
graphs the existence of one or more connected components takes a different interest, and this is related to the
average degree c. Two extreme situations are presented in Figure 10.5 which consists in a totally disconnected
graph of 16 vertices, and the graph K16 . The first one is obtained for p = 0 while the second one is obtained
for p = 1.

Figure 10.5: One graph with 16 components, and K16

One central question is about the existence of a giant component. This notion is not defined for a single graph
but for a family of graphs whose number of vertices is going to infinity. Recall from Definition 1.3 that the
number of vertices of a graph G corresponds to its order and is denoted by |G|. A working definition of such
a giant component is provided in:
Definition 10.4 (Giant component). A family of graphs {Gn }n∈N , satisfying |Gn | → ∞ as n → ∞, possesses a
giant component if there exist some connected subgraphs Λn ⊂ Gn and ϵ > 0 with |Λn | > ϵ|Gn | for all n ∈ N.
By looking at the two examples provided in Figure 10.5 one guesses that the existence of a giant component is
linked to the parameter c. Indeed, in the special case c = 0 (which corresponds to p = 0), no giant component
exists, while in the case c = n − 1 (which corresponds to p = 1) it is clear that a giant component exists, since
all graphs Kn are connected. What about c ∈ (0, n − 1) ? Our next aim is to answer this question.
In the setting of the previous definition, and if one assumes that there exists a giant component, let us set u
for the probability that a vertex does not belong to the giant component. For simplicity, we assume that this
probability is independent of n, which is correct if |Λn |/|Gn | is a constant independent of n. Consider now one
vertex x of Gn which is not in the giant component, and let y be any other vertex of Gn . The relation between
x and y is either they are not connected (which takes place with probability 1 − p) or they are connected (with
a probability p) but it is then necessary that y is not in the giant component (with happens with the probability
u), since otherwise x would also belong to it. Thus, the probability for x not to be in the giant component
through y is given by (1 − p) + pu10 . Since y can be any of the n − 1 vertices of the graph, it follows that the
probability u of not being in the giant component satisfies the relation
 c(1 − u) n−1
u = (1 − p) + pu n−1 = 1 − ,


(10.2.1)
n−1
10
We use here the fact that the probability of a union of two mutually exclusive events is given by the sum of their probability.

109
 Figure 10.6: Function S 7→ 1 − e−cS

where the average degree c defined in (10.1.4) has been introduced. By assuming c fixed, as explained in
Remark 10.1, and by considering the limit n → ∞, one gets from (10.2.1) that u = e−c(1−u) , or alternatively if
one sets S = 1 − u
S = 1 − e−cS . (10.2.2)

Equation (10.2.2) can not be solved explicitly, but its solutions can be easily visualized, see Figure 10.6.
Indeed, one can plot the function S 7→ 1 − e−cS for various values of c, and also the function S 7→ S . The
intersections of these curves give the solutions of (10.2.2), and the value S = 0 is always a solution. If
c = 1, the two curves are tangent at S = 0, which implies that only one solution exists, and the same happens
for c < 1. On the other hand, for if c > 1 a second solution always exists, even if its explicit expression
can not be obtained. Numerically, this second solution can easily be obtained, as a function of c, and the
graph of this second solution as a function of c is reported in Figure 10.7. Clearly, this second solution is
monotically increasing from the value 0 to the value 1 as c goes from 0 to ∞. Observe finally that since u
was the probability of not being in the giant component, the variable S corresponds to the probability of being
in the giant component. As visible in Figure 10.7, this probability is 0 as long as c ≤ 1 and then is strictly
positive. Thus, a giant component can exist whenever c > 1, and in this case its relative size is given by the
function c 7→ S . For this model, the value c = 1 corresponds to a phase transition, since a giant component
does not exist for c ≤ 1 while it exists for c > 1.
By a separate argument, as presented in [Ne, Sec. 11.5.1] one can show that if a giant component exists, then
it is unique. In other words, it is not possible in this model that two giant components coexist, although it is
not prohibited by the definition of a giant component. The argument goes roughly as follows: if they were
two giant components, the probability that they would not be connected can be computed and is exponentially
small. In the limit n → ∞, this exponentially small term vanishes, and therefore the probability that the two
components are not connected is 0.
Now, what about the small components ? Indeed, the giant component does not cover the entire graph, as a

110
 Figure 10.7: The solutions of (10.2.2) as a function of c

consequence that S < 1. What can one say about the remaining parts of the graph ? Since the size of the small
components grow with a rate smaller then |Gn |, their number has to increase as n → ∞. For this model, the
behavior of the small components is well understood and can be studied analytically. We only summarize the
outcomes, and refer to [Ne, Sec. 11.5] for more information and additional references.
Let us consider a small component G s of fixed s ∈ N vertices. The first observation is that this component will
be a tree with probability 1 as n → ∞. The argument is the following: first of all, observe that a tree contains
s − 1 edges, which is the minimal number of edges for any connected graph of s vertices. Then, there exists
2 − (s − 1) = 2 (s − 1)(s − 2) possibilities for adding one edge in this graph, and the probability of adding
s
1

one edge is p = n−1c

. Thus, the average total number of additional edges to this component is

1 c c(s − 1)(s − 2)
(s − 1)(s − 2) =
2 n−1 2(n − 1)

and this number goes to 0 as n → ∞. As a consequence, each small component is likely to be a tree in the
limit n → ∞.
Let us now denote by π s the probability that a randomly chosen vertex belongs to a small component of size
s. Clearly, s∈N∗ π s = 1 − S , which is the probability of not being in the giant component, if this one exists. It
P
is possible but rather long to deduce the explicit expression for π s , we only provide the final result in the limit
n → ∞, namely
e−sc (sc) s−1
πs = .
s!
It is also possible to get the average size of the small component G x to which the randomly chosen vertex x
belongs to, namely P P
s∈N∗ sπ s ∗ sπ s 1
E(|G x |) := P = s∈N = , (10.2.3)
s∈N∗ π s 1−S 1 − c + cS
where S is the value provided by Figure 10.7. A representation of E(|G x |) as a function of c is provided in
Figure 10.8. There is clearly a singularity as c = 1. In fact, when one approaches c = 1 either from the left
or from the right, the small components tend to become bigger and bigger. For understanding what happens
precisely at c = 1, further refined analysis is needed.

111
Figure 10.8: In black, the function c 7→ E(|G x |) given in (10.2.3); in red, the function
c 7→ E(|G s |) given in (10.2.4)

Let us finish this section with one tricky but interesting point. Does (10.2.3) give us the mean size E(|G′ |)
for any small component G′ ? The answer is no because the computation is biased. Indeed, recall that π s is
the probability that a randomly selected vertex is in a component of size s. It is therefore not the probability
of existence of a component of size s (which leads to the average size of the small components). Thus, in
order to correct the computation, let us observe that if n s denotes the number of components of size s, then
the following equality holds:
sn s
πs = .
n
For the computation of the mean size E(|G′ |) of the small components one has

n s∈N∗ π s
P P
s∈N∗ sn s 1−S 2
′
E(|G |) := P = P πs = P πs = . (10.2.4)
s∈N∗ n s n s∈N∗ s s∈N∗ s 2 − c + cS

It is interesting to see that this function does not possess a singularity at c = 1, as shown in Figure 10.8.

10.3 Clustering coefficient and path lengths

Let us start by introducing the clustering coefficient which plays an important role in the analysis of real
graphs. This coefficient is a measure of the degree to which nodes in a graph tend to cluster together. It is also
related to the notion of transitivity which has been introduced in Definition 8.5. More precisely, the clustering
coefficient is going to estimate the lack of transitivity of a graph. Two versions of this measure exist: the
global one and the local one. The global version was designed to give an overall indication of the clustering
in the network, whereas the local gives an indication of the embeddedness of single nodes.

For the following definition, we call triplet three vertices which are connected either by 2 edges (open triplet)
or by 3 edges (closed triplet). Since the graphs considered are simple, it means that open triplets consist in one
vertex connected to two distinct vertices, while closed triplets correspond to 3-cycles, also called triangles.

Definition 10.5 (Global clustering coefficient). For a finite simple graph, its global clustering coefficient C is

112
defined by
♯(closed triplets) 11
C := . (10.3.1)
♯(triplets)

For example, if a graph is transitive, then C = 1. On the other hands, trees have a global clustering coefficient
equal to 0 since they do not possess a single closed triplet. For the local clustering coefficient, recall from
Definition 1.4 that the neighbours N(x) of x consist in the vertices connected to x. Clearly, the cardinality of
N(x) is equal to the degree deg(x) of x.
Definition 10.6 (Local clustering coefficient). For a finite simple graph G = (V, E) and for any x ∈ V, the
local clustering coefficient C x is defined by

(y, z) ∈ E} | y, z ∈ N(x)
C x := 2
. (10.3.2)
deg(x) deg(x) − 1

More explicitly, the numerator consists in the number of edges with both endpoints in N(x) while 12 deg(x) deg(x)−


1 consists in the total number of possible edges with two endpoints in N(x). This coefficient measures again
the lack of transitivity around x, since it considers if the two vertices y and z, which are connected to x, are
also connected to each others. Based on this local notion, it is also possible to compute its average, namely

1 X
C := Cx
|G| x∈G

but in general this value is not equal to the global clustering coefficient.
What about these concepts applied to the random model G(n, p) ? Since in this model the probability of any
two vertices to be connected is always the same, namely p = (n−1)
c
, and since this probability is independent
of all the other existing or missing edges one infers that
c c
E(C) = p = , E(C x ) = p = (10.3.3)
n−1 n−1
which vanish in the limit n → ∞. We shall see later on that this constant value of the clustering coefficients is
one of the factors which make random graphs quite different from real-world graphs.
There is a second quantity which provides some important information about a graph, namely the so-called
length path. In fact, this name is slightly misleading since the correct notion is the diameter introduced in
Definition 1.15. More precisely, one looks for the shortest path between two arbitrary vertices, and if one
considers the longest such path, it is precisely the diameter of the graph. Note that one could also consider the
mean of the distance between two arbitrary vertices.
The computation of the diameter of random graphs is heuristically very simple, but precisely rather delicate,
and there exist several research papers dealing only with this question. Here, we shall consider only the
heuristic argument, and refer [Ne, Sec. 11.7] and references therein for more precise considerations. Note that
a precise computation has to take into account the precise dependence on n of the average degree c.
11
Note that on has to be consistent when computing these numbers: if the triplet (x, y, z) is considered different from the triplet
(y, z, x), then this rule should be taken into account both for the numerator and for the denominator. For that reason, slightly different
3♯(triangles)
formulations also appear in the litterature: for example it is sometimes written C = .
♯(triplets)

113
The heuristic argument goes as follows: starting from an arbitrary vertex x, c vertices are at a distance 1,
c(c − 1) new vertices are at a distance 2, c(c − 1)3 new vertices are at a distance 3, and c(c − 1) j−1 new vertices
are at a distance j. It means that at a distance at most j one can reach

j−1
X
c + c(c − 1) + c(c − 1)2 + · · · + c(c − 1) j − 1 = c (c − 1)i = (c − 1) j − 1  c j
i=0

new vertices, if we assume that c is large enough. Of course, this estimate is really a rough estimate since for
a fixed i there may exist several paths of length i between x and a given y. This observation means that in the
above summation, there are several redundancies. We should clearly think about this estimate as a first order
approximation. Thus, whenever c j = n, with n the number of vertices of the graph, it means that we have
“roughly” been able to visit all vertices of the graph. Based on this equality, one deduces an estimate on the
diameter of the graph, namely
ln(n)
c j = n ⇔ j ln(c) = ln(n) ⇔ j = .
ln(c)
In fact, a more precise approach leads to the estimate

ln(n)
E diam(G) = A +


(10.3.4)
ln(c)

for some constant A which can be computed. As for the clustering coefficient, this result will have to be
compared with the diameter of real-world graphs.

10.4 Weaknesses
The random graph model G(n, p) has been one of the first ones introduced, and is considered as a simple
model. However, when compared to real networks or real-world graphs, some of its properties do not match
with the observations. There exist numerous analysis of real and social networks, and we shall not go in this
direction. However, let us just mention a few weaknesses of the Gilbert-Erdős-Rényi model, and refer to [Ne,
Chap. 10] for more information.
A table containing several example of networks and their basic properties is provided in Figure 10.9. In this
table, the following information are mentioned:
(i) The type of the graph: directed or undirected,
(ii) The total number of vertices n,
(iii) The total number of edges m,
(iv) The mean degree c,
(v) The probability S of being in the giant component,
(vi) The mean distance ℓ between connected vertices,
(vii) The exponent α of the power law distribution of the degrees, if it follows a power law as introduced in
(10.4.1),
(viii) The clustering coefficient, as defined in (10.3.1).

114
 Figure 10.9: Basic properties of several networks, from Table 10.1 of [Ne]

One important difference between the content of this table and the outcome of the random model G(n, p) is
the clustering coefficient. Indeed, all values for C is this table range between 0.005 and 0.2, with a majority
close to 0.1. On the other hand, the result obtained in (10.3.3) for G(n, p) reads C = n−1
c
, which leads to values
which are much smaller than the ones measured.
Another striking difference is about the degree distribution of
vertices. It was shown in (10.1.6) that the distribution of de-
grees in the G(n, p) model follows a Poisson distribution, in the
limit n → ∞. On the other hand, several real networks present
a power law distribution for deg(x). A typical power law distri-
bution over R+ is shown in Figure 10.10, and it corresponds to
the graph of a function of the form x 7→ x−α . Note that some
regularization near 0 should be considered, or one should only
consider x ≥ xmin > 0. The discrete version of a power law
reads Figure 10.10: Power law distribution
N∗ ∋ k 7→ k−α ∈ R+ . (10.4.1)
The coefficient α provided in Figure 10.9 corresponds to the exponent of this function, whenever the degrees
follow such a lower law. The clear difference between the Poisson distribution provided by the G(n, p) model,
and the degree distribution of a network like internet is presented in Figure 10.11, despite the fact that these
two distributions have the same average.

115
Figure 10.11: Comparison of two degree distributions, from Figure 11.8 of [Ne]

116
Chapter 11

The configuration model

In this chapter we introduce another model of random graphs which is one of the most important theoretical
models for the study of networks. It is often used as a first model before turning to more specialized ones. Let
us mention that we shall consider only undirected graphs, but alternative solutions for directed graphs exist.
One of the important feature of the configuration model is that the degree distribution can be easily tuned. The
notion of modularity is also introduced in the last section of this chapter.

11.1 Construction, and basic properties

In the configuration model, the degree of each vertex is pre-defined, which means that any degree distribution
can be implemented. In other words and as opposed to the G(n, p) model, the degree distribution is not
restricted to have a Poisson-distribution, the model allows the user to give the network any desired degree
distribution.
Let us start by dealing with a sequence of positive integers. For a fixed n ∈ N, consider a sequence {ki }ni=1
with ki ∈ N and with the property that ni=1 ki = 2m for some m ∈ N. In other words, the positive integers
P
ki sum up to an even number. We call such a sequence {ki }ni=1 a nm-degree sequence. Note that the number n
will correspond to the number of vertices of the future graph, the number m will correspond to its number of
edges, while the numbers ki will correspond to the degree of the vertex xi .
For any nm-degree sequence, let us also define nk as the number of elements in the sequence satisfying ki = k.
In other words, nk is going to be the number of vertices with degree k. Clearly, k∈N nk = n. Let us set
P
pk := nnk . The distribution {pk }k∈N is going to provide the degree distribution of the future graph. Thus, by first
choosing a distribution {pk }, and then a suitable nm-degree sequence having this degree distribution, one can
construct graphs with any prescribed degree distribution.
Let us now concentrate on the construction of the graph, with the notation introduced in the previous para-
graphs. The graph is constructed for any given nm-degree sequence:
(i) For any i ∈ {1, . . . , n} endow xi with ki half edges, also called stubs, see Figure 11.1a,
(ii) Connect the half edges uniformly at random by creating proper edges, see Figure 11.1b.
With this construction, it is clear that one ends up with a graph containing n vertices and m edges. Note that
multiple edges can appear, and loops as well. It is also clear why the condition ni=1 ki is even is necessary: if
P

117
 (a) First step: half edges (b) Second step: uniform matching

Figure 11.1: Construction of the configuration model

not, one half edge would not match with any other. The resulting graph has a prescribed degree distribution,
given by the distribution {pk }k∈N introduced above. On the other hand, any half edge is equally likely to be
connected to any other half edge.
There are two standard choices for the distribution {pk }k∈N : a power law distribution or a Poisson distribution.
In the latter case, observe that the resulting graph is very close to a graph obtained by the G(n, p) model.
However, graphs obtained by the configuration model can have multiple edges and loops, while no such
graphs exist in the G(n, p) approach. On the other hand, since many real-world graphs are observed to have a
power law degree distribution, the configuration model with power law degree distribution allows us to study
them theoretically and to understand some of their properties.
Let us now study some simple properties of the configuration model. For the time being we do not impose any
condition on the nm-degree sequence {ki }ni=1 , or equivalently on the distribution {pk }k∈N . Note that we shall
always consider large n and m, or even the limits n → ∞ and m → ∞.
First of all, given two distinct vertices xi and x j , what is the probability of having an edge from xi to x j ? One
stub at xi can be connected to 2m − 1 other stubs, among them k j belong to x j . Thus the probability of this
kj ki k j
stub to be connected to x j is 2m−1 . If xi has ki stubs, then the probability that xi is connected to x j is 2m−1 . In
summary, the probability pi j of having an edge between xi and x j is given by

ki k j
pi j = . (11.1.1)
2m − 1

A similar derivation for loops holds: one easily find that the probability of a loop at xi is given by12

ki (ki − 1)
pii = .
2(2m − 1)

For future investivations, let us introduce the notations

1X 1X 2
⟨k⟩ = ki and ⟨k2 ⟩ = k . (11.1.2)
n i n i i
 
12 ki
The factor 2 is due to the factor 2
for the possible choices of the two stubs.

118
We immediately observe that the following equalities hold:
1X 1X X nk X
⟨k⟩ = ki = nk k = k= kpk = E degx


n i n k k
n k

and
1X 2 1X X
⟨k2 ⟩ = ki = nk k2 = k2 pk = E deg(x)2


n i n k k

with x an arbitrary vertex of the graph. The expressions ⟨k⟩ and ⟨k2 ⟩ correspond thus to the first and second
moments of the degree distribution13 .
For the following computations, we mention that our understanding is based on [1]. What about the expecta-
tion for the number of loops ? If L denotes the random variable corresponding to the number of loops, then
one has
X X ki (ki − 1) ⟨k2 ⟩ − ⟨k⟩ 1 ⟨k2 ⟩ − ⟨k⟩
E(L) = pii = = = 1 + O(1/n)


(11.1.3)
i i
2(2m − 1) 2(⟨k⟩ − 1/n) 2 ⟨k⟩

which means that the density of loops by vertex goes again like 1n . In the limit n → ∞, loops become very
rare in the configuration model.
Let us now compute the probability of having at least two distinct edges between xi and x j . First of all, observe
 
1
that the probability of two stubs at xi to connect to two stubs at x j is (2m−1)(2m−3) . Furthermore, there are k2i
 
choices of 2 stubs at xi , and similarly k2j choices of 2 stubs at x j . Finally, since there are 2 possible ways for
the 2 stubs at xi to be paired to the two stubs at x j , we find that the probability of a double edge between xi
and x j is given by
ki (ki − 1) k j (k j − 1)
.
2(2m − 1)(2m − 3)

What is now the expected number of double edges in the graph ? If D denote the random variable correspond-
ing to the number of double edges, then we have
X ki (ki − 1) k j (k j − 1)
E(D) =
1≤i< j≤n
2(2m − 1)(2m − 3)
n
⟨k2 ⟩ − ⟨k⟩ 2 ki (ki − 1) 2

X

= −
4(⟨k⟩ − 1/n)(⟨k⟩ − 3/n) i=1 2(2m − 1)(2m − 3)
!2
1 ⟨k2 ⟩ − ⟨k⟩
1 + O(1/n)


≤ (11.1.4)
4 ⟨k⟩
Observe that the leading term in (11.1.4) does not depend on n, which means that the expected number of
double edges remains bounded by a constant as the graph grows (when n → ∞). Accordingly, the density
of multiple edges by vertex goes at most like n1 , which means that double edges are rare in the configuration
model, when n is large enough. Let us mention that the expectation of multiple edges could be slightly bigger,
since triple or higher multiplicity edges have not been taken into account in this computation.
13
If these quantities are computed with a power law distribution one should be a little bit more careful. Indeed, as long as these
quantities are computed for a finite degree sequence, all sums are finite, but in the limit n → ∞ these sums might contain an infinite
number of contributions, and accordingly their convergence might not hold. In fact, one easily observes that if pk = k−α for all k ∈ N∗ ,
then only a finite number of moments exist, if any, and this number depends on α. As a rule, whenever we write ⟨k s ⟩ for some s > 0
we assume that this quantity exists and is not infinite.

119
11.2 Additional properties
In this section we study a few additional properties of the configuration model, and one of them turns out
to be rather surprising. As mentioned in the previous section, the model is either described by a nm-degree
sequence, or by a degree distribution {pk }k∈N . We opt for the latter setting. In this context, pk is the probability
that a vertex chosen uniformly at random has a degree k.
Suppose firstly that we start at one vertex, and follow one of its edges. What is the probability that the second
endpoint of this edge has a degree k ? The naive answer pk can not be correct, since for example one would
never be able to reach a vertex with degree 0, while such vertices exist with probability p0 . Less naively, our
current edge can end at any of the 2m − 1 other stubs, among which knpk belong to vertices with degree k.
Thus, the probability of ending at a vertex of degree k is given by

knpk k
= pk 1 + O(1/n) .


(11.2.1)
2m − 1 ⟨k⟩

This result is in fact rather natural, since one has a bigger chance of reaching a vertex with degree k than a
vertex of degree 1 (assuming that k ≥ 1) even if pk = p1 .
Let us infer a rather surprising result from (11.2.1). By starting again at an arbitrary vertex x, what is the
average degree of its neighbours ? This quantity is obtained by averaging k over the probability of having
degree k given by (11.2.1), namely

X kpk
⟨k2 ⟩
E {deg(y) | y ∈ N(x)} = k 1 + O(1/n)  .
k
⟨k⟩ ⟨k⟩

Thus, the average degree of the neighbours of x is different from the average degree in the graph, which is
⟨k⟩ ≡ E(k) ! In addition, one observes that

⟨k2 ⟩ 1 σ2k
− ⟨k⟩ = ⟨k ⟩ − ⟨k⟩ =
2 2

⟨k⟩ ⟨k⟩ ⟨k⟩

where σ2k = ⟨k2 ⟩ − ⟨k⟩2 > 0 corresponds to the variance of the degree distribution. In other words, the average
degree of the neighbours of x is bigger than the average degree of an arbitrary vertex in the graph. In terms of
/
a grumpy person : your friends have more friends than you do. Let us emphasize that this phenomenon is
not a special feature of the configuration model, it can be measured on various networks, as shown in Figure
11.2. Note also that this surprising property can be fully explained. In short, any vertex with degree k will
appear as neighbour of exactly k other vertices, and hence will appear in k averages. At the same time, all
vertices with 0 edge won’t play any role in this computation (simply because they are never reached), while
they are counted in the computation of ⟨k⟩.

Figure 11.2: The degree of neighbours is always higher, from Sec. 12.2 of [Ne]

120
Still based on (11.2.1) let us introduce one more quantity, the excess degree of a vertex. Again, starting at
x and arriving at a neighbour y, its excess degree is simply the number of its edges minus the one used for
reaching it. Thus the probability that the excess degree is k simply given by
(k + 1)pk+1
qk = (11.2.2)
⟨k⟩
which is obtained by considering (11.2.1) for k + 1. The distribution defined by {qk }k∈N is called the excess
degree distribution. Its average can be easily computed, namely
X 1 X 1 X ⟨k2 ⟩ − ⟨k⟩
E(q) = kqk = k(k + 1)pk+1 = k(k − 1)pk = .
k
⟨k⟩ k ⟨k⟩ k ⟨k⟩

Let us now turn our attention to the clustering property of the configuration model, as defined in Definition
10.5. Consider a vertex x with at least two edges, and let xi and x j the two distinct vertices connected to x.
Their remaining number of edges is denoted by ki and k j respectively, and are distributed according to the
excess degree distribution qki and qk j . In addition, the probability that they share an edge is given by (11.1.1),
ki k j
namely 2m−1 . The clustering coefficient is obtained by summing all these contributions:
X ki k j 1 X 2
E(C) = qki qk j = kqk
ki ,k j
2m − 1 2m − 1 k

1  ⟨k2 ⟩ − ⟨k⟩ 2 1 (⟨k2 ⟩ − ⟨k⟩)2

= = 1 + O(1/n) .


3
(11.2.3)
2m − 1 ⟨k⟩ n ⟨k⟩
This result can be compared to the one obtained in (10.3.3) for the random model G(n, p). Their similar feature
is the decay in 1n , which does not really take place for real-world graphs. However, the factor ⟨k2 ⟩ appearing
in (11.2.3) can take very large values, depending on the degree distribution considered, and therefore lead to
a clustering coefficient more in line with the observations.
What about a giant component and about the small components, as studied in Section 10.2 for the random
model G(n, p). It turns out that a similar analysis can be performed for the configuration model, and that
similar results hold. More precisely, it can be shown that a giant component exists if the following condition
is satisfied:
⟨k2 ⟩ − 2⟨k⟩ > 0. (11.2.4)
This condition can be obtained from different approaches, and we refer to [Ne, Sec. 12.6] for the details. Let
us just mention that one approach is to set u for the probability that a vertex does not belong to the giant
component, and by a clever reasoning one infers that u has to satisfy the equation

u = g1 (u) (11.2.5)

with X
g1 (u) = qk uk . (11.2.6)
k
In general (it depends on the initial degree distribution {pk }) this equation can not be solved explicitly, but
some arguments leads to the condition (11.2.4).
If a giant component exists, then one can also look at the small components. As in the previous model, these
small components are trees, in the limit of an infinite graph. As we already did in (10.2.3), let us provide the

121
average size of the small component to which a randomly chosen vertex belongs. If s denotes the size of a
small component to which a randomly chosen vertex belongs to, then for the configuration model one has

u2 ⟨k⟩
E(s) = 1 +
,
g0 (u) 1 − g′1 (u)

with g0 (u) = k pk uk . Clearly, this expression is complicated. However, if there is no giant component,
P
namely when u = 1, it can be simplified. In this situation one gets

⟨k⟩2
E(s) = 1 + .
2⟨k⟩ − ⟨k2 ⟩

Another quantity which has been mentioned for the G(n, p) model is the diameter of a graph containing n
vertices. We only provide the result, and refer to [Ne, Sec. 12.9] for its precise computation. Note however
that the approach is rather standard for any type of graphs, and often lead to similar results. For the current
model of graphs with n vertices, it turns out that
ln(n)
E diam(G) = A +


(11.2.7)
⟨k2 ⟩−⟨k⟩

ln ⟨k⟩

for some constant A which can be computed. Note that this result is quite similar to the one already obtained
in the previous model.
As already mentioned at the beginning of this chapter, one interest in the configuration model is the ability of
choosing the degree distribution. For example, it is possible to implement that only a few pk are not 0, meaning
that one vertex can only have a prescribed number of edges attached to it. In such a case, the computations
are usually quite simple, as shown in an explicit example provided in [Ne, Sec. 16.1]. Another example is to
consider exact power law provided for α > 0 by the formula

1  0 if k = 0
pk = ,

ζ(α) k −α

 if k ≥ 1

where ζ(α) = ∞ −α is the Riemann zeta function. In such a situation, some additional computations can
P
k=1 k
be performed, as for example
∞ ∞
X 1 X −α+1 ζ(α − 1)
⟨k⟩ = kpk = k = ,
k=0
ζ(α) k=1 ζ(α)

or
∞ ∞
X 1 X −α+2 ζ(α − 2)
⟨k ⟩ =
2
k pk =
2
k = .
k=0
ζ(α) k=1 ζ(α)
With this explicit expression, condition (11.2.4) for the existence of a giant component reads ζ(α − 2) >
2ζ(α − 1) which can be solved numerically: one gets this existence if α < 3.4788....
As already mentioned in the footnote on page 119, the power law distribution suffers from the non-existence
k=1 k pk = ζ(α) k=1 k
of most of its moments. Indeed, it is easily seen that ∞
P s 1 P∞ s−α exists if and only if s < α − 1.

Thus, the expression ⟨k⟩ is finite if α > 2 and ⟨k ⟩ is finite if α > 3. Nevertheless, it is sometimes possible to
2

cut the tail of this distribution (put pk = 0 for k large enough) and get some meaningful result. For example,
one infers from this approach that (11.2.4) is always satisfied for α ∈ (2, 3]. If α ∈ (3, 3.4788...) there is still a

122
giant component, but not for larger α. Note that for α ≤ 2, a giant component also exists, but other tools are
necessary for proving it.

Let us end this section with one key word: generating functions. These functions are very useful in probability
and should have been introduced. Some results of this section can be easily obtained with them. However,
these functions have to be properly introduced in a course on probability. Don’t miss to attend such a course,
very powerful techniques will then be available.

11.3 Community structure, or modularity

In this section, we introduce one more concept which is useful for arbitrary graphs. This notion, called com-
munity structure or modularity, provides one measure of the structure of a graph. It was designed to measure
the strength of division of a network into modules (also called groups, clusters or communities). Networks
with high modularity have dense connections between the vertices within modules but sparse connections
between vertices in different modules. Modularity is often used in optimization methods for detecting com-
munity structure in networks. However, it has been shown that modularity suffers a resolution limit and,
therefore, it is unable to detect small communities. A graph with two clear communities is presented in Figure
11.3. Note that there is a third community (grey dots) which is spread on the other two communities.

Figure 11.3: A graph with 3 communities, from Sec. 7.7 of [Ne]

The relation between the search of community structure and the configuration model is the following: the
number of edges inside a suspected community will be compared to the configuration model, in which edges
are placed uniformly at random. In other words, the configuration model is used as a test model. If there exist
more edges than the one provided by the configuration model, then the community really exist. But note that
it might not be the tighter community (or the one with the biggest number of edges between its members).

123
The computation is based on the adjacency matrix AG = {ai j } introduced in Definition 2.1, and will also use
the probability pi j of having an edge between xi and x j inspired by (11.1.1) for the configuration model.
We consider a graph G = (V, E) with |V| = n and |E| = m, both numbers being large but finite. Let U ⊂ V
be a subset of vertices, and let us simply write i for the vertex xi . The number of edges between vertices in
U is then given by 21 i, j∈U ai j , where the factor 12 compensates the fact that we count each edge twice. Note
P
that even for loops, it gives the right answer due to our convention in the definition of the adjacency matrix
for undirected graphs. On the other hand, for the configuration model the expected number of edges between
ki k j
vertices in U is approximately given by 21 i, j∈U 2m
P
, as a consequence of (11.1.1). Thus, the important
quantity is the difference between the existing edges and the expected ones, namely

1 X ki k j 
ai j − .
2 i, j∈U 2m

So far, we have used only one set U ⊂ V which could correspond to one community. What about a situation
where we would like to consider several communities ? For that purpose, we can complicate a little bit the
above expression. Assume that the vertices are distributed within N communities, or equivalently that they are
labeled with N different labels (or weights). Without loss of generality we can consider the set {1, 2, . . . , N}
as this set of labels, and write ℓi ∈ {1, 2, . . . , N} for the label of the vertex xi . With the usual notation of the
Kronecker delta function we shall write δℓi ℓ j = 1 if ℓi = ℓ j , and δℓi ℓ j = 0 if ℓi , ℓ j . Then one defines the
modularity
1 X ki k j 
Q := ai j − δℓ ℓ . (11.3.1)
2m i, j 2m i j
1
Note that the preliminary factor 2m provides a kind of normalisation: we do not count edges anymore, but
fraction of the total number of edges.
Note that so far, the modularity has been computed once the labels are given. In that sense, it is possible
to check if a partition into some communities is valuable or not. However, the correct question is how to
detect communities, and check that they are real ? Such investigations are often called community detecting or
modularity maximization, and it is considered as a complicated problem. If falls into the general framework
of discrete optimization problems. Indeed, first of all the problem is not really well posed, since the number
and the size of the communities have not been specified. In addition, what makes a good partition, and is it
possible to find a better one ? It is certainly not possible to look for all possible partitions of the vertices in
different subsets and to compute Q for all of them.
Let us just sketch a few ideas, and refer to the specialized literature for further information. Note that we
provide information only in the very special case of two communities.
First of all, let us define
ki k j
Bi j := ai j −
2m
kj
Bi j = k j − = k j − k j = 0, and similarly Bi j = 0. Let us also use the labels
P P P
and observe that i 2m i ki j
ℓi ℓ j +1
{−1, 1} instead of {1, 2}. With these labels, namely with ℓi ∈ {−1, 1} one gets that δℓi ℓ j = 2 . Thus, by
rewriting (11.3.1) and by using the special property mentioned above one infers that

1 X 1 X 1 t
Q= Bi j (ℓi ℓ j + 1) = Bi j ℓi ℓ j = ℓBℓ (11.3.2)
4m i j 4m i, j 4m

124
where we have used the notation B for the matrix {Bi j } and ℓ for the vector with the n components ℓ j ∈ {−1, 1}.
One has also used t ℓ for the transpose vector. Observe that ∥ℓ∥2 = n, where ∥ · ∥ denotes the Euclidean norm in
Rn . Once recast in this framework, we are looking at a maximization problem: Find the extremum of (11.3.2)
√
under the constraint that ∥ℓ∥ = n. There is just one problem: the solution we are looking for should take
place in {−1, 1}n , but we shall reformulate the probem in Rn (which is necessary for using tools from calculus)
and therefore obtain a solution in Rn . Nevertheless, it will be possible to look at the closest solution inside
our framework, and hope that the error by imposing ℓ j ∈ {−1, 1} will not change the result drastically. Let us
mention that in such a problem, one rarely looks for the best solution, but for a solution quite close to it.
Our new problem can now be solved with the technique of Lagrange multiplier. Namely, one looks for a
solution of the system of equations

∂ hX  X i X
Bi j ℓi ℓ j + λ n − ℓi2 = 0 ⇐⇒ Bi j ℓ j = λℓi .
∂ℓi i, j i j

By writting this system with matrices, we look for a solution of

Bℓ = λℓ.

which corresponds to an eigenvalue / eigenvector problem. But which eigenvalue ? By inserting this solution
into (11.3.2) one infers that
1 t 1 t n
Q= ℓBℓ = ℓλℓ = λ.
4m 4m 4m
Since we want to maximize Q, the corresponding eigenvalue should be maximum, or in other terms we look
for the maximal eigenvalue of B, and for the corresponding eigenvector ℓ.
The solution of this problem will certainly not have its solution in {−1, 1}n . However, if u ∈ Rn denotes the
eigenvector corresponding to the highest eigenvalue, then we can always set ℓ j = +1 if u j ≥ 0 and ℓ j = −1
if u j < 0. The corresponding vector ℓ is not an eigenvector of the matrix B, but it turns out that the partition
of the graph according to the label given by ℓ is often quite good. In fact, this method provides a surprisingly
good solution in many situations, and has the advantage of being easily implementable. More sophisticated
methods exist, but as a first and simple approach, this spectral method works well.

125
Chapter 12

Epidemics on graphs

In this final chapter we look at applications of graphs for the modelization of epidemic spread. It is certainly
a hot topic, but clearly we can only touch its surface. Further investigations are encouraged. Note that in the
first section, no graph is involved.

12.1 Basic models

In this section we introduce the simplest models for the spread of infections. These models always consist
in a certain number of compartments which contain a population in a homogeneous state. For example, the
compartment S contains the population susceptible of getting a disease, while the compartment I contains the
population which has been infected. Now, these populations can consist of individuals (which means that the
compartments contain an integer number of elements) or can consist in a percentage of the total population.
In the first picture, the sum of the different compartments provide the total number of individuals in the
population, while in the second picture the number in each compartment sum up to 1. Note that for simplicity,
we shall continue speaking about individuals even in the second picture. In both pictures, the content of
each compartment is time dependent. The evolution of the system is usually given by a system of differential
equations relating the content of the different compartments. The number of compartments and the relations
between their content determine the complexity of the model. Several parameters are often involved, and
determining these parameters is often part of the problem.

12.1.1 The SI-model

This model is the simplest one and consist only of two compartments: S and I, which means that once
an individual has been infected, it remains infected and can forever infect susceptible individuals. Let us
introduce two variables describing the content of S and I, namely s and ι (pronounced iota). We shall assume
that s + ι = 1, which means that s = 1 − ι. In fact, we should write ι(t) and s(t) = 1 − ι(t) with the variable t
representing the time, but the notation ι and s is commonly admitted.

For this system, the flow between the two compartments corresponds to the individuals which get infected. In
other words, some elements of S with leave this compartment, and join I. On the other hand, I will simply
receive this flow of individuals from S, but nothing will escape from this compartment. The corresponding

126
system of equations is 
 dt = −βsι

 ds
(12.1.1)
 dι = βsι


dt

where β > 0 corresponds to a transmission coefficient or contact average. More precisely, β provides the
contact rate with random other individuals per unit time. Observe that in this model, it is considered that
the probability of getting infected is propositional to the number of infected persons and to the number of
susceptible individuals. Note that since s + ι = 1 we don’t need both equations, and in addition the second one
can be rewritten as
dι
= βι(1 − ι). (12.1.2)
dt

The equation (12.1.2) appears at many places, and is called the logistic equation. Its solution is also known,
namely
ι0 eβt
ι(t) = ,
1 − ι0 + ι0 eβt
where ι0 corresponds to the value of ι at t = 0. Note that an initial condition is always necessary for such an
equation, but the choice of t = 0 for the initial condition is rather arbitrary. A representation of the function
t 7→ ι(t) for t ≥ 0 is provided in Figure 12.1. It is easy to observe that for this model limt→∞ ι(t) = 1, whenever
ι0 > 0. As a consequence, s(t) will converge to 0 while ι(t) will converge to 1. In other terms, for this model,
whenever a tiny part of the population is infected, then the entire population will become infected, even if it
takes a long time. This model is useful for some diseases, but its outcome is clearly not the only possible one.

Figure 12.1: The solution of the logistic equation, from Sec. 16.1 of [Ne]

12.1.2 The SIR-model

Another common model consists in three compartments, which are commonly called S, I and R, where the
new compartment corresponds to individuals who have recovered from the infection. Typically, an infected
individual stays a couple of time unit in the compartment I before leaving for the compartment R. Note
that there are different ways to modelize the time spent in I before moving to R. Here we consider only the

127
simplest situation, see Remark 12.1. The variables for this system are s, ι, and r, and they satisfy s + ι + r = 1.
The corresponding system of equation reads

dt = −βsι

 ds


dt = βsι − γι

 dι

 (12.1.3)

 dr = γι


dt

where the additional parameter γ > 0 is interprated as 1/(mean infectious time).

Remark 12.1. With the value γ, one can calculate the probability that an individual is still infected after a
time t. Since the probability of recovering in any time interval ∆t is equal to γ∆t, and the probability of not
recovering is 1 − γ∆t, one gets that the probability of still being infected after a total time t is given by

lim (1 − γ∆t)t/∆t = e−γt . (12.1.4)

∆t→0

As a consequence, the probability that an individual is still infected after a total time t and recovers during
the following interval ∆t is given by γe−γt ∆t, which corresponds to an exponential distribution. This behavior
is certainly not very realistic, since usually an individual has a disease for about a fixed duration (1 week, 2
weeks, 1 month,...), while with the current model the individual is most likely to recover immediately, but might
also keep the disease for an exponentially long time. Nevertheless, this model is often kept for its simplicity.
As for the SI-model, an initial condition has to be given. Here the natural choice is ι0 > 0 and r0 = 0, meaning
that no individual has recovered at time t = 0. Obviously, other choices are possible. Then, by eliminating the
variable ι between the first and the third equation of (12.1.3) one obtains

1 ds β dr
=−
s dt γ dt

leading to the solution

s = s0 e−βr/γ
with s0 = 1 − ι0 . By inserting into the third equation of (12.1.3) the relation ι = 1 − s − r and the previous
result for s one then infers that
dr
= γ 1 − r − s0 e−βr/γ .


(12.1.5)
dt
Unfortunately, an explicit solution of this equation can be not obtained, but numerical evaluations are at hand.
Typical outcomes for the system (12.1.3) are shown in Figure 12.2. In this picture, the value β = 1, γ = 0.4,
ι0 = 0.01, s0 = 0.99, and r0 = 0 have been chosen.
Let us emphasize that the final outcome here is different from the one of the SI-model. Indeed, s(t) does not
converge to 0 as t → ∞, which means that part of the population will never be infected. More precisely,
when t → ∞, there is no more evolution, and therefore dr dt = 0. Thus, by using (12.1.5), one infers that
limt→∞ (1 − r − s0 e −βr/γ ) = 0. In other words, it means that r(∞) satisfies the equation
β
r(∞) = 1 − s0 e− γ r(∞) .

Usually, the value s0 is very close to 1, and therefore one looks for a solution of
β
r(∞) = 1 − e− γ r(∞) . (12.1.6)

128
 Figure 12.2: The solution of the system (12.1.3), from Sec. 16.1 of [Ne]

Quite surprisingly, this equation is similar to (10.2.2) which appears in relation with the existence of the giant
component for the G(n, p) model. This means that we can borrow the results obtained in that context, namely:
when γβ > 1 there exists a solution r(∞) of (12.1.6) satisfying r(∞) < 1, and accordingly that s(∞) > 0.
When γβ ≤ 1, no epidemic is taking place. The initial infected population recovers faster than the susceptible
individuals become infected. The variable ι(t) will simply decrease, and no local maximum like in Figure 12.2
will take place. Note that some tools for visualizing the behavior of the evolution as a function of β and γ are
easily available on internet, see for example [33]. Note that the transition γβ = 1, which means β = γ is called
β
a epidemic threshold. Because of its importance, the ration γ is called basic reproduction number and is often
denoted by R0 .

12.1.3 Other models

There exist plenty of models based on the same ideas but with more compartments and a more complicated
differential systems. Some key ideas are for example that

(i) Some individuals might come back from R to S if they have not got any immunity during the infected
period,

(ii) The total population is not constant, due to births, deaths, or other factors,

(iii) Several diseases could interact and either facilitate each others, or prevent each others,

(iv) Some diseases need complex contagions, which means that the exposition to one infected person is not
sufficient, but additional contacts with other infected persons are necessary.

This list could be continued endlessly, see [34] for further information. We shall not complicate any further
our models, but let us mention that current models used for the Covid-19 can take up to 21 compartments into
account, see Figure 12.3, and involve a system of 21 related equations.

129
 Figure 12.3: One model used for the modelization of Covid-19, from [35]

12.2 Percolation
In the previous section, it was considered that any individual could be in contact with any other. In reality,
individuals have often a set of acquaintances, and do not interact so often with other individuals uniformly at
random. In the sequel, the set of acquaintances will be described by a graph, with individuals represented by
vertices, and with edges representing the relations between the individuals.

In this framework, a concept which is going to play an important role is the one of percolation or more
precisely of site percolation or bond percolation. The idea of site percolation is the following: consider
a connected undirected graph, and let us start removing some vertices uniformly at random. What is the
proportion of vertices which have to be removed such that the graph becomes disconnected ? The central
point in percolation theory is the existence of a threshold value such that the properties of the graphs below
or above this value are very different. This threshold value is also called a phase transition, and it appeared
already in the setting of random graphs in Chapters 10 and 11.

There exist different strategies for removing vertices of a graph. For example, one can remove some of them
independently of their degree, or choose only the ones with the minimum or with the maximum degree.
Depending on the purpose, a particular strategy can be more useful than others. Let us look at the situation in
which the vertices are removed independently of their degree, they are chosen uniformly at random. We shall
use the parameter ϕ for quantifying the removal process: ϕ is called the occupation probability, and ϕ = 1
means that all vertices are present, and none has been removed. On the other hand, ϕ = 0 means all vertices
have been removed, there is no more any graph.

Let us now consider again the configuration model with a degree distribution {pk }k∈N , and set u for the average
probability that a vertex is not connected to the giant component via a particular neighbour. Suppose also that
part of the vertices have been removed uniformly at random, and that ϕ provides the fraction of the remaining
ones. Then, the relation that u has to satisfy is not more provided by (11.2.5) but has to be adapted if ϕ , 1.
There are two ways to not be connected to the giant component via a neighbour: either this neighbour has

130
 Figure 12.4: A graphical resolution of (12.2.1), from Section 15.2.1 of [Ne]

been removed, which happens with a probability 1 − ϕ, or the neighbour is present (with a probability ϕ) but
this one is not connected to the giant component. As a consequence, the new relation that u has to satisfy is

u = 1 − ϕ + ϕg1 (u) (12.2.1)

with g1 defined in (11.2.6), see [Ne, Sec. 15.2.1] for the details. There is no way to solve (12.2.1), but a
graphical approach is proposed in Figure 12.4.
From the graphical approach, it is quite clear that the threshold value for ϕ takes place when the r.h.s. of
(12.2.1) satisfies
d
1 − ϕ + ϕg1 (u) u=1 = 1


du
which means that the two functions represented on Figure 12.4 are tangent at u = 1. Thus, this threshold ϕc
satisfies ϕc = g′ 1(1) , which can be computed explicitly. By using (11.2.6) for the explicit expression for g1 one
1
finds
⟨k⟩
ϕc = 2 . (12.2.2)
⟨k ⟩ − ⟨k⟩

131
Interestingly, if the degree distribution follows a Poisson distribution, as for the G(n, p) model, then one gets
ϕc = 1c , with c = ⟨k⟩ the mean degree of the graph. If the degree distribution follows a power law with
α ∈ (2, 3), it has already been mentioned that ⟨k2 ⟩ = ∞. In such a situation, ϕc = 0 meaning that no matter
how many vertices will be removed from the graph, a giant component will persist ! This is the sign of the
strong robustness of graphs with a degree distribution provided by a power law.
The previous construction is based on a uniform removal of nodes, but as already mentioned, other strategies
might be useful. We refer to Section 15.3 of [Ne] for alternative constructions.

12.3 Epidemic on graphs and percolation

From now on, let us consider a fixed graph, with vertices representing individuals and edges representing
the relation between these individuals. Clearly, graphs are loopless and unoriented, but an orientation could
be added for some applications. Let us also introduce a transmission rate or infection rate β which is the
probability per unit time that an infection will be transmitted between two individuals through an edge between
the corresponding two vertices. Let us emphasize that this coefficient is slightly different form the one already
introduced in (12.1.1) since in the present situation it corresponds to the rate of contact with just one individual
connected through one edge. Observe that the transmission rate β depends on the disease itself, but also on
the social and behavioural parameters of the population.
A precise evolution equation for a disease on a graph will only be introduced in the next section. We provide
here only some heuristic considerations, together with a trick. We start by emphasizing a major difference
between the previous continuous models, and any models on graphs. Indeed, if the transmission of a disease
takes place trough edges and if at the initial time there exists only one single infected individual, then only
the component of the corresponding vertex might expect an epidemic. The other components will remain
uninfected. As a consequence, if a graph contains a giant component and several small components, with
a fraction S of vertices in the giant component, the maximum fraction of individuals that one single initial
individual can infect is precisely S , if this initial individual is in the giant component. If the corresponding
vertex is in a small component, only a very small number of individuals might get the disease. In summary,
the connected components play now a role which simply do not exist in the continuous models.
In a graph’s version of the SI-model, one expects that the entire connected components of the initial infected
individual will become infected, as soon as β > 0. This outcome is due to the fact that once infected, one
individual will remain infected and can infect others forever.
Let us now present an heuristic argument for an analog of the SIR-model on graphs. Consider firstly one
infected vertex which is connected to a susceptible vertex. By a computation similar to the one performed
in (12.1.4), one infers that the probability that the disease is not transmitted during an interval of time τ is
given by e−βτ , where β is the transmission rate. Thus, the probability that the disease is transmitted during this
interval is
ϕ = 1 − e−βτ . (12.3.1)
If we now consider that the infected individual recovers precisely after a period of time equal to τ, the proba-
bility that he would have infected any connected vertex before recovering is precisely given by (12.3.1). We
call this quantity the transmission probability. Let us emphasize that in this argument, the paradigm used in
Remark 12.1 is changed: now the infected person is no more infectious after a time τ.
In this framework, the transmission probability is a constant over the graph, and any susceptible individual
has an equal probability ϕ of getting the disease through an infected neighbour. A trick, already introduced

132
decades ago, is to use some ideas coming from the theory of percolation. Assume that an edge in the graph is
present with a probability ϕ, and absent with a probability 1−ϕ. Equivalently, one can assume that the fraction
1 − ϕ of the edges has been removed. As a consequence, the remaining edges correspond to the ones along
which the disease can propagate. However, if too many edges has been removed, an initially connected part
of the graph might now be no more connected. The threshold and phase transition mentioned in the previous
section are now going to play a role. Note however that there is a small difference between the current situation
and the one of the previous section: here one should speak about bond percolation or edge percolation while
site percolation was discussed before. Fortunately, this difference will not play any role for our purpose.
Let us again consider the configuration model, and let ϕ be the transmission probability given in (12.3.1).
Even though the transmission probability is associated with edges, if we set u for the average probability that
a vertex is not connected to the giant component via a particular neighbour, one gets again the self-consistent
equation for u obtained in (12.2.1), namely u = 1 − ϕ + ϕg1 (u) with g1 defined in (11.2.6). It follows that the
result obtained in the previous section for site percolation can be used again, and one infers a transition for ϕ
given by (12.2.2). This result together with (12.3.1) leads to the relation
 ⟨k2 ⟩ − ⟨k⟩ 
βτ = − ln 1 − ϕc = ln 2 .


(12.3.2)
⟨k ⟩ − 2⟨k⟩

Let us recall that the denominator on the r.h.s. is positive precisely when a giant component exists, see (11.2.4).
Thus, if βτ is bigger that the value on the r.h.s. and if the initial infected individual belongs to the giant
component, an epidemic is expected. On the other hand, if βτ is smaller than the r.h.s. then an epidemic will
not take place, no matter where the initial infected individual is located. In the former case, note however that
not all the individuals might get infected, only the one in the giant component, which does not represent the
entire population in general.
As a consequence of (12.3.2), a certain control on the propagation of the disease is possible through β. This
parameter is partially due to the inherent propagation properties of the disease itself, but also to the behavior
of the population (wear a mask !). The r.h.s. is a property of the social relations, it can also be adjusted (less
interactions between individuals) even if the effect is less clear through this formula.

12.4 Time dependent evolution

The link between epidemic on graphs and percolation can only lead to some asymptotic results. For a more
precise picture, an evolution equation is necessary, and has not been introduced so far. We shall use the
shorter notation introduced in Section 11.3, namely a vertex is simply denoted by i. Then, we write si ≡ si (t)
for the probability that the vertex i is susceptible, ιi ≡ ιi (t) for the probability that the vertex i is infected,
and ri ≡ ri (t) for the probability that the vertex i has recovered. For the graph’s version of the SI-model, the
relation si + ιi = 1 holds, while for the analog of the SIR-model the condition is si + ιi + ri = 1 for any i.
Let us recall that the adjacency matrix has been introduced in Definition 2.1. Here, we shall simply denote
it by A = {ai j }. We first consider the SI-system. In this case, the natural analog of the differential system
(12.1.1) takes the form
 ds  ds
 dti = −βsi j ai j ι j  dti = −βsi j ai j (1 − s j )
 P  P
 
⇐⇒  (12.4.1)
 dιi = βsi P j ai j ι j

  dιi = β(1 − ιi ) P j ai j ι j

dt dt

for any i. Again, one of these equations is sufficient since si + ιi = 1. For SIR-system, the natural analog of

133
the differential system (12.1.3) takes the form
 ds
dt = −βsi j ai j ι j
 i
P



dt = βsi j ai j ι j − γιi
 dιi
 P

 (12.4.2)

 dri = γιi ,


dt
where γ is the recovery rate, or more precisely the probability per unit time that an infected individual will
recover. Note that the content of the last equation is closer to the approach taken in Section 12.1.2 than to the
approach mentioned in Section 12.3.
An initial condition has to be associated to these systems. One possibility if to consider ιi = nc for any i, where
c is a small positive integer and n represent the number of vertices of the graph or of the giant component. The
idea is that c vertices are initially infected, and that the probability of being infected is distributed uniformly
at random over all vertices. Clearly, other choices are possible.
The systems of equations (12.4.1) and (12.4.2) are usually not solvable explicitly, and several approaches have
been developed. One can either look at numerical simulations, or get some analytical results after imposing
some simplifications to these systems. Let us just mention a few key ideas. One approach is to consider the
initial condition as mentioned above, which makes all initial ιi small, and then approximate the second term
in (12.4.1) as dιdti  β j ai j ι j . In other terms, it means ignoring the second order terms. This can be done
P
for a short time approximation of the evolution, but the result is usually not so good. A better approach is
called pair approximation and consider the product si ι j as a new variable. More precisely, one sets pi j for the
probability that j is infected given that i is not infected. Then, it is possible to rewrite a system of equation
for the variable pi j and solve it rather explicitly (once a suitable assumption is taken on the relations between
triplet of vertices). The outcome is usually much better than in the first approach, but whenever the graph is
highly transitive, the approximation is no more suitable. Finally, a heuristic approach is to suppose that all
vertices with the same degree have the same probability of getting infected at any time. With this assumption,
one ends up with new variables which depend only on the degree k and no more on any specific vertex i.
Surprisingly, this approach leads to rather accurate prediction. We refer to Sections 16.5 and 16.6 of [Ne] for
more information on these approaches. For finite graphs of different types, simulations are quite enlightening
and can be easily be found on internet.
Let us end this section with the so-called mean field approach. The main idea of mean field theory is the study
the behavior of high-dimensional random models by studying a simpler model that approximates the original
by averaging over degrees of freedom. Here, the simpler variables will the average number of vertices in a
prescribed state. For that purpose, let us first denote by Xi = Xi (t) the function (random variable) taking the
three values S , I, or R depending if the vertex i is susceptible, infected or has recovered at time t. We then
define for A ∈ {S , I, R} the expected value
X
P Xi (t) = A


[A](t) :=
i
there P is the probability, and where we have assumed that the summation is taking place on the vertices
of a finite simple graph. Then, [S ](t) represents the expected value for the number of vertices which are
susceptible, [I](t) the one for the number of infected vertices, and [R](t) the one for the number of vertices
which have recovered. Clearly, for the SI-model one has [S ](t) + [I](t) = n, if n denotes the number of vertices
of the graph, while for the SIR-model one has [S ](t) + [I](t) + [R](t) = n
Let us now define for A, B, C ∈ {S , I, R} the new quantity
X
ai j P Xi (t) = A, X j (t) = B


[AB](t) :=
i, j

134
and X
ai j a jk P Xi (t) = A, X j (t) = B, Xk (t) = C ,


[ABC](t) :=
i, j,k

where {ai j } denote the adjacency matrix for the graph. These quantities correspond to number of expected
connected vertices which are in a prescribed states. Note that the role of the adjacency matrix is precisely to
keep track of the vertices which are connected. Note also that [AB](t) = [BA](t), but that such relations with
three sets do not hold in general. Note also that for the SI-model, the relation

[S S ](t) + [S I](t) + [IS ](t) + [II](t) = nc ≡ n⟨k⟩

where c or ⟨k⟩ denote the mean degree or (average degree) in the graph. Clearly, a similar relation holds for
the SIR-model as well.
With these notations, the individual dynamics introduced in (12.4.1) and (12.4.2) can be transformed into
collective dynamics, namely  . d[S ](t)
[S ](t) ≡ dt = −β[S I](t)


. (12.4.3)
[I ](t) ≡ d[I](t) = β[S I]


dt

and  .

 [S ](t) ≡ d[Sdt](t) = −β[S I](t)
 .


[I ](t) ≡ d[I](t)
dt = β[S I](t) − γ[I](t)

 (12.4.4)
.


[R](t) ≡ d[R](t) = γ[I](t).


dt

Observe that the r.h.s. of (12.4.4) depends on the dynamics of [S I](t). Thus, in order to solve this system, we
could look for an additional equation. In fact, all quantities [AB](t) with A, B ∈ {S , I, R} are related, as shown
in Figure 12.5. Note that in this figure, τ should be replaced by β. Thus, we can look for additional relation
and find that
d[S I](t)
= −γ[S I](t) + β [S S I](t) − [IS I](t) − [S I](t)


dt
and
d[S S ](t)
= −2β[S S I](t).
dt
Similar relation can also be found for [II](t), [S R](t), [IR](t) and [RR](t). Clearly, one could go one, and get
an infinite set of differential equations. However, the trick is do do some approximations for some products
[A . . . Z](t). For example, a common approximation takes the form
[AB](t) [BC](t)
[ABC](t) 
[B](t)
and such a formula will “close” the system of equations. Note that such approximations can be justified
according to the structure of the graphs, but they are always approximations. Clearly, by keeping more terms,
one gets a better approximation of the true solution, but the price is an increase of complexity. Life is all about
,
balance . For further investigations about epidemics on networks, we refer to the monograph [KMS].

135
Figure 12.5: The first two flow diagrams for the SIR-model, from Fig. 4.3 of [KMS]

136
Bibliography

[1] O. Angela, R. van der Hofstad, C. Holmgren, Limit laws for self-loops and multiple edges in the config-
uration model, Annales de l’Institut Henri Poincaré - Probabilités et Statistiques Vol. 55, No. 3, 1509–
1530, 2019.
[BG] S. Baase, A. van Gelder, Computer algorithms, Introduction to design and analysis, Addison-Wesley,
2000.
[CH] J. Clark, D.A. Holton, A first look at graph theory, Wold Scientific, 1991.
[Die] R. Diestel, Graph theory, Fifth edition, Springer, 2017.
[GYA] J.L. Gross, J. Yellen, M. Anderson, Graph theory and its applications, CRC press, 2019.
[KMS] I. Kiss, J. Miller, P. Simon, Mathematics of epidemics on networks, Springer, 2017.
[Ma] B. Maurer, The King Chicken Theorems, Mathematics Magazine Vol. 53, (1980), pp. 67-80.
[Mo] J.W. Moon, Topics on tournaments, Holt, Rinehart and Winston, Inc., 1968.
[Ne] M. Newman, Networks, second edition, Oxford University Press, 2018.
[2] [Link] group
[3] [Link] Matrix
[4] [Link] acyclic graph
[5] [Link]
[6] [Link] tree
[7] [Link] traversal
[8] [Link] expression tree
[9] [Link] search tree
[10] [Link] number
[11] [Link] formula
[12] [Link] tree proble
[13] [Link] algorithm
[14] [Link]

137
[15] [Link] theorem
[16] [Link] Bridges of Königsberg
[17] [Link]
[18] [Link] factorial
[19] [Link] graph
[20] [Link] (computer science)
[21] O. Svensson, J. Tarnawski, L. Végh, A Constant-Factor Approximation Algorithm for the Asymmetric
Traveling Salesman Problem, Preprint arXiv:1708.04215, 2017.
[22] [Link] and ceiling functions
[23] [Link]
[24] [Link] color theorem
[25] [Link] 23572634232
[26] [Link] color theorem
[27] [Link] connected component
[28] [Link] choice theory
[29] [Link] [Link]
[30] [Link] algorithm
[31] [Link]
[32] [Link] model
[33] [Link]
[34] [Link] models in epidemiology
[35] E, Amstrong, M. Runge, J. Gerardin, Identifying the measurements required to estimate rates of COVID-
19 transmission, infection, and detection, using variational data assimilation, medRxiv preprint doi:
[Link]

138