Graph Theory

MATH20150
2
Contents

1 Basic notions 5

2 Graphic sequences, adjacency matrix 15

3 Eulerian graphs 23

4 Trees 27

5 Hamiltonian graphs 35

6 Graph isomorphisms 43

7 Bipartite graphs 45

8 Planar graphs 49

9 Networks 55

3
4 CONTENTS
Chapter 1

Basic notions

Definition 1.1. A graph G = (V, E) is an ordered pair of finite sets, where

• V is non-empty;

• E is a set of finite subsets of V , each of which contains 2 elements. E

may be empty.

Definition 1.2. An element of V is called a vertex.

An element {p, q} of E is called an edge, and we say that it joins the vertices p
and q.

From the definition, an edge cannot join a vertex to itself (because it would
then be of the form {p, p} = {p} which is a set with only one element).

Remark 1.3. What we call a graph is sometimes called a simple graph in texts
(so: check the terminology when you look at a book).

A graph can always be represented as a picture: Represent each vertex in

V by a point, and draw a line between any two vertices joined by an edge (the
lines may intersect).

Example 1.4. 1. G = (V, E) with V = {1, 2, 3, 4, 5}, E = {{1, 2}, {1, 3}, {4, 5}}.

2. G = ({a}, ∅).

5
6 CHAPTER 1. BASIC NOTIONS

3.

These two pictures represent the same graph:

G = ({1, 2, 3, 4}, {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}.

The fact that the edges {1, 3} and {2, 4} intersect in the first picture has
no meaning. It is not always possible to avoid such intersections, see the
section on planar graphs.
Notation 1.5. We will usually simply denote the edge {p, q} by pq.
The following types of edges are excluded by definition:
1. A self-loop: An edge from a vertex to itself.

2. Parallel edges:

(Since E is a set, the edge {u, v} is an element of E, and elements of a set

are not repeated.)
Definition 1.6. A multigraph is a graph in which the existence of several edges
joining 2 vertices (parallel edges) is permitted.
(In this case we need to replace E by something allowing repetition, for
instance E could be a tuple that contain subsets of V of 2 elements.)
Example 1.7.

Definition 1.8. A pseudograph is a multigraph in which self-loops are permitted

(as well as parallel self-loops).
Example 1.9.

Vy
 7

It is also sometimes useful to give a direction to the edges:

Definition 1.10. A directed graph (or digraph) is an ordered pair of finite sets
(V, E) where
• V is non-empty;
• E is a set of ordered pairs of distinct elements of V (called arcs).
Example 1.11.

({1, 2, 3, 4}, {(1, 4), (1, 2), (3, 2), (3, 4), (4, 2)})

Definition 1.12. Let G = (V, E) be a graph with V = {v1 , . . . , vn } and E =

{e1 , . . . , em }. The order of G is equal to |V | = n (i.e., is the number of vertices)
and the size of G is |E| = m (i.e., the number of edges).
Example 1.13. The graph

has order 7 and size 8.

Definition 1.14. The complete graph of order n, denoted Kn , is the graph with
n vertices such that every pair of distinct vertices is joined by an edge.
Example 1.15.

K1 : K2 : K3 :

K4 : K5 :

n(n−1)
Proposition 1.16. The size of Kn is 2 .
Proof. An edge in Kn is given by any 2 different
  vertices. The number of ways
n
of picking 2 different vertices among n is   = n(n−1)
2 .
2

Definition 1.17. 1. If p, q are two vertices of a graph and e = {p, q} is an

edge of the graph, we say that p is adjacent to q (and of course q is adjacent
to p), and that e is incident with p and with q.
8 CHAPTER 1. BASIC NOTIONS

2. If v is a vertex of a graph G, the degree of v, denoted d(v), is the number

of edges incident with v.
Example 1.18. The graph

has d(1) = 1, d(2) = 4, d(3) = 1, d(4) = 2, d(5) = 2, d(6) = 0.

Proposition 1.19. If G is a graph of order n and v is a vertex of G, then
0 ≤ d(v) ≤ n − 1.
Proof. Obvious.
Definition 1.20. Let G be a graph of order n and let d1 , . . . , dn be the degrees
of the vertices of G, in non-decreasing order (d1 ≤ d2 ≤ · · · ≤ dn ). The sequence
d1 , . . . , dn is called the degree sequence of G.
Proposition 1.21 (Degree sum formula, a.k.a. the handshaking lemma). Let
d1 , . . . , dn be the degree sequence of a graph G = (V, E) or order n. Then
n
X
di = 2|E|.
i=1

Proof. If rs is an edge in G, itP

contributesP
1 to d(r) and 1 to d(s). Thus each
n n
edge contributes 2 to the sum i=1 di , so i=1 di = 2|E|.
Corollary 1.22. In any graph, the number of vertices of odd degree is even.
Proof. Let v1 , . . . , vk be the vertices of odd degree and u1 , . . . , u` be the vertices
of even degree. Then

d(v1 ) + · · · + d(vk ) + d(u1 ) + · · · + d(u` ) = 2|E| .

| {z } |{z}
even even

Therefore d(v1 ) + · · · + d(vk ) is even. Since it is a sum of odd numbers, we must

have that k is even.
Example 1.23. There is no graph with degree sequence 1, 1, 1, 2, 4, 5, 6, 7, 7, 7.
Corollary 1.24. If G is a graph of order n > 1 then G has at least two vertices
of the same degree.
Proof. Suppose not. Then the degree sequence of G is such that

0 ≤ d1 < d2 < · · · < dn ≤ n − 1.

The only possibility is d1 = 0, d2 = 1, . . . , dn = n − 1. Since d1 = 0 there is a

vertex adjacent to no other vertex. Since dn = n − 1, there is a vertex adjacent
to every other vertex. Contradiction.
 9

Definition 1.25. Let G = (V, E) be a graph.

1. A graph G0 = (V 0 , E 0 ) is called a subgraph of G if V 0 ⊆ V and E 0 ⊆ E.
We write G0 ⊆ G.
2. If G0 is a subgraph of G, we denote by G \ G0 (G without G0 ) the graph
obtained from G by removing all the vertices from G0 and all the edges
adjacent to at least one vertex of G0 .
Definition 1.26. Let G be a graph. A walk in G is an alternating sequence of
vertices and edges in G:

W = v0 , e1 , v1 , e2 , . . . , v`−1 , e` , v`

where ei is the edge vi−1 vi for i = 1, . . . , `.

The length of the walk W is `, the number of edges in W . We write for short
W = v0 v1 · · · v` (since there is only one edge between vi−1 and vi ).
A closed walk is a walk with v0 = v` .
Example 1.27.

1 2 3 4 3 5 6 is a walk in G.
Definition 1.28. 1. A trail is a walk in which no edge is repeated (but a
vertex could be repeated).
2. A path is a walk with no repeated vertices. A path is always a trail since
to repeat an edge you must repeat at least one vertex.
3. A circuit is a trail v0 v1 . . . v` where v0 = v` (and ` ≥ 3 because it is a
trail).
4. A cycle is a walk v0 v1 . . . v` with l ≥ 3, v0 = v` and v0 , . . . , v`−1 are all
different (so that no edge and no vertex is repeated; a cycle is a path that
is also a circuit).
Example 1.29. In the graph

1 2 3 4 5 3 1 is a circuit, but 1 2 1 is not a circuit;

1 2 5 4 1 and 1 2 3 1 are cycles, but 1 2 3 4 5 3 1 is not a cycle.
10 CHAPTER 1. BASIC NOTIONS

Proposition 1.30. If K is a circuit, then K contains a cycle.

Proof. Let L be a subgraph of K that is a circuit with the smallest possible num-
ber of edges (it could be K itself): L = v0 v1 . . . vn v0 . We show that v0 , . . . , v`
are all different (i.e., the L is a cycle): If it were not the case, say vr = vs for
some 0 ≤ r < s ≤ n then vr vr+1 . . . vs would be a circuit in K with less edges
than L, contradiction.
Definition 1.31. Let x and y be vertices in a graph G, with x 6= y. We say
that x and y are connected if and only if there exists a path in G of the form
xv1 · · · vr y (connecting x and y).
A graph G is called connected if every pair of vertices x, y in G with x 6= y
is connected, or if G has only one vertex.
Example 1.32.

are connected graphs.

The graph

is not connected.
Proposition 1.33. Let x, y be distinct vertices in a graph G. If there exists a
walk in G from x to y, then there exists a path in G from x to y.
Proof. Take W a walk from x to y of minimal length (i.e., with minimal number
of edges): W = (x = v0 )v1 v2 · · · vn (y = vn+1 ).
We check that W is a path: If not then we have vr = vs for some 0 ≤ r < s ≤
n + 1. If we remove the section vs vs+1 · · · vr−1 from W we get v0 · · · vs−1 (vr =
vs )vr+1 · · · vn+1 , which is also a walk from x to y, but is shorter than W , a
contradiction.
Proposition 1.34. Let G = (V, E) be a graph. There exist k ∈ N and subgraphs
G1 , . . . , Gk of G such that
1. G is the union of G1 , . . . , Gk , i.e., if Gi = (Vi , Ei ) then V = V1 ∪ · · · ∪ Vk
and E = E1 ∪ · · · ∪ Ek .
2. Each Gi is connected.
3. For every i 6= j, Gi and Gj have no vertex in common.
Example 1.35.
 11

Proof. By induction on n, the order of G:

• n = 1. Then G has only one vertex and is thus connected.

• If n > 1 (we assume that the result has been checked for graphs of order
< n).
Let v be a vertex of G and let

V1 = {x | x vertex of G, x connected to v} ∪ {v},

E1 = the set of all edges xy of G with x, y ∈ V1 .

Let G1 = (V1 , E1 ). G1 is a graph and is connected: If x, y ∈ V1 , then
there are paths from x to y (and thus at least a walk from x to y).
If G1 = G the proof is finished
If G1 6= G, let G0 be the graph obtained from G by removing every edge
and every vertex from G1 (i.e. G0 = G\G1 in the terminology of definition
1.38).
Then G = G1 ∪ G0 , G1 and G0 have no common vertex, and G0 has order
less than n. By induction we have G0 = G2 ∪ · · · Gn where the Gi are
connected and have no vertices in common. Therefore G = G1 ∪ G2 ∪ · · · ∪
Gn where the Gi are connected and have no vertices in common.

The graph Gi in the proof is a maximal connected subgraph of G, i.e., a

connected subgraph that is not contained in a larger connected subgraph.

Definition 1.36. A maximal connected subgraph of G is called a component of

G.

So each graph is the disjoint union of its components (see the previous ex-
ample).

Definition 1.37. We denote by ω(G) the number of components of G.

Definition 1.38. Some operations with graphs:

1. The union: If G1 = (V1 , E1 ) and G2 = (V2 , E2 ) then

G1 ∪ G2 = (V1 ∪ V2 , E1 ∪ E2 ).

For instance:

Adding edges: If E2 is a set of new edges in G1 , we define

G1 ∪ E2 = (V1 , E1 ∪ E2 ).
12 CHAPTER 1. BASIC NOTIONS

For instance, if G1 is

and E2 = {14}, then G ∪ E2 is

2. The difference: Let H = (VH , EH ) be a subgraph of G. Then

G \ H = (V 0 , E 0 ), where

V 0 = V \ VH and E 0 = E from which we remove all the edges that have at

least one end in VH .
For instance, if H is the red subgraph, then G \ H is the green subgraph:

3. Induced subgraph (restriction): Let G = (V, E), and let V 0 ⊆ V be a subset

of vertices of G. Then G[V 0 ] = (V 0 , E 0 ) where E 0 is the set of all edges of
E that have both ends in V 0 .
For instance, if V 0 is the red set of vertices:

then G[V 0 ] is
 13

4. Removing edges: Let G = (V, E) and let E 0 be a subset of E. Then

G \ E 0 = (V, E \ E 0 ).
For instance, if G is

then G \ {e1 , e2 } is

Definition 1.39. Let G = (V, E) be a graph.

1. A vertex v ∈ V is called a cut-vertex if ω(G \ {v}) > ω(G).
For instance, if G is

then ω(G) = 1, but ω(G \ {v}) = 3:

2. An edge e ∈ E is called a bridge (also cut-edge) if ω(G \ {e}) > ω(G).

For instance, if G is

then ω(G) = 1, but ω(G \ {e}) = 2:

14 CHAPTER 1. BASIC NOTIONS
Chapter 2

Graphic sequences,
adjacency matrix

Definition 2.1. A sequence of integers (d1 , . . . , dn ) is called graphic if it is the

degree sequence of a graph.

Example 2.2. 1. (1, 2, 2, 3) is graphic:

2. (1, 1, 1, 2, 2, 3, 4, 5) is not graphic (there would be an odd number of vertices

of odd degree, see corollary 1.22).

3. (2, 3, 3, 4, 5, 6, 7) is not graphic (the graph would have 7 vertices and one
of them would have degree 7, which is impossible).

Problem: Given a sequence (d1 , . . . , dn ) of elements of N, determine whether

or not it is graphic. Clearly, if we have di ≥ n for some i, then the sequence is
not graphic (having a vertex with degree equal at least to the number of vertices
would require self-loops or parallel edges). The other case is answered by this
result:

Theorem 2.3 (Havel (1955)- Hakimi (1962)). Let d = (d1 , . . . , dn ) be a se-

quence of elements of N ∪ {0} such that d1 ≤ d2 ≤ · · · ≤ dn < n. Construct

d0 = ( d1 , d2 , . . . , dn−dn − 1, . . . , dn−1 − 1)
| {z } | {z }
n − dn − 1 elements dn elements
can be empty
(if dn = n − 1)

Then d is graphic if and only if d0 is graphic (after being re-ordered to be in

non-decreasing order, if necessary).

15
16 CHAPTER 2. GRAPHIC SEQUENCES, ADJACENCY MATRIX

Example 2.4. 1.
apply Thm .2.3 make it non-decreasing
(0, 1, 1, 1, 2) −→ (0, 1, 0, 0) −→ (0, 0, 0, 1)
apply Thm. 2.3
−→ (0, 0, −1) not graphic

2.
apply Thm. 2.3 make it non-decreasing
(1, 1, 2, 2, 2, 4) −→ (1, 0, 1, 1, 1) −→ (0, 1, 1, 1, 1)
apply Thm. 2.3 make it non-decreasing
−→ (0, 1, 1, 0) −→ (0, 0, 1, 1) −→ (0, 0, 0) graphic:

Remark 2.5. The sequence (0, 0, . . . , 0) is always graphic:

(a graph with no edges).

Consequently: Applying the transformation from theorem 2.3. we can always
reduce to either
• A sequence of zeros (which is graphic, so the starting sequence is graphic)
or
• A sequence containig negative numbers (which is not graphic, so the start-
ing sequence is not graphic).
Proof. (of theorem 2.3)
• We first show that d0 graphic implies d graphic:
By hypothesis d0 is the degree sequence of some graph G0 = (V 0 , E 0 ), and

d0 = (d1 , d2 , . . . , dn−dn − 1, . . . , dn−1 − 1).

If we denote the coefficients of d0 above by d01 , . . . , d0n−1 , we have d0i = d(vi )

where V 0 = {v1 , . . . , vn−1 }.
To get G = (V, E) out of G0 we add one vertex: V = V 0 ∪ {vn } and we
add edges from vn to vn−dn , . . . , vn−1 .:

E = E 0 ∪ {vn vn−dn , . . . , vn vn−1 }.

Then the degree sequence of G is d.

• We now show that d graphic implies d0 graphic:
We write
d = (d1 , . . . , dn−dn , . . . , dn−1 , dn ),
where di = d(vi ) and V = {v1 , . . . , vn }. We consider two cases
Case 1: If vn is adjacent to vn−dn , . . . , vn−1 . Then we remove vn and all
the edges vn vn−dn , . . . , vn vn−1 . The resulting graph has degree sequence
d0 .
 17

Case 2: If vn is not adjacent to all of vn−dn , . . . , vn−1 .

Consider the following Fact
Fact: We can modify the edges in the graph G to
obtain a graph with the same degree sequence
d, but where the amount of neighbours of vn
among vn−dn , . . . , vn−1 is increase by 1
Applying this Fact several times, we will be back to case 1, from which
we can conclude. So we only have to justify why this fact is true:

Let i ∈ {n − dn , . . . , n − 1} be the least integer such that vn is not a

neighbour of vi .
Since d(vn ) = dn , vn is adjacent to some vj with j < n − dn :

If d(vj ) = d(vi ), we simply relabel the vertices and swap vi and vj (the
degree sequence is unchanged).
If d(vj ) < d(vi ): There is a vertex vk adjacent to vi but not to vj (and
vk 6= vn because vn is adjacent to vj ):

In this case we remove the edges vj vn and vi vk , then add the edges vj vk
and vi vn :

Doing this preserves the degree of all vertices, so the degree sequence
is unchanged, but now vn has one more neighbour in vn−dn , . . . , vn−1
(namely vi ).

The proof of theorem 2.3 is an algorithm. We saw in the previous remark

that is a sequence is graphic, repeated applications of theorem 2.3 will give the
sequence (0, . . . , 0), corresponding to the graph
18 CHAPTER 2. GRAPHIC SEQUENCES, ADJACENCY MATRIX

Using the part “d0 graphic ⇒ d graphic” of the proof of theorem 2.3 (the
easy part), and starting from the graph

we can construct a graph with degree sequence d.

Example 2.6. 1.

(1,1,2,2,2,4)

↓ ↑ n = 6, dn = 4
(1,0,1,1,1)

↓ ↑
(0,1,1,1,1)

↓ ↑ n = 5, dn = 1
(0,1,1,0)

↓ ↑
(0,0,1,1)
↓ ↑ n = 4, dn = 1
(0,0,0) −→

2. Ursa major:

Its degree sequence is (1, 2, 2, 2, 2, 2, 3). We know it is graphic, but we still

apply the above algorithm:
 19

(1,2,2,2,2,2,3)

↓ ↑ n = 7, dn = 3
(1,2,2,1,1,1)
↓ ↑
(1,1,1,1,2,2)

↓ ↑ n = 6, dn = 2
(1,1,1,0,1)

↓ ↑
(0,1,1,1,1)
↓ ↑ n = 5, dn = 1
(0,1,1,0)
↓ ↑
(0,0,1,1)
↓ ↑ n = 4, dn = 1
(0,0,0) −→
The result we obtained here does not look like Ursa Major. Conclusion:
There can be different graphs with the same degree sequence.

Definition 2.7. Let G = (V, E) be any graph (graph, multigraph, pseudograph,

directed graph). Consider any labelling V = {v1 , . . . , vn } of the vertices of G.
The adjacency matrix of G (with respect to this labelling) is

A = (aij )i,j=1,...,n ,

where

aij = the number of edges in G starting at vi and ending at vj .

Example 2.8. 1.

 
0 1 1 0
 
 
1 0 1 0
A=

.

1 1 0 1
 
0 0 1 0
20 CHAPTER 2. GRAPHIC SEQUENCES, ADJACENCY MATRIX

2.

 
1 2 0
 
A = 1 1 .
 
0
 
0 0 0

Some properties of A (depending on the type of graph):

• “normal” graph: aij ∈ {0, 1}.
• no self-loops: aii = 0.
• undirected: aij = aji , i.e., A = At .
(k)
Proposition 2.9. Let Ak = |A · A {z
· · · · · A} = (aij )i,j=1,...,n . Then
k times

(k)
aij = the number of walks of length k from vi to vj .

Example 2.10. 1.

 
2 1 1 1
 
 
1 2 1 1
A2 = 

.

1 1 3 0
 
1 1 0 1
There are 2 walks of length 2 from v1 to v1 , and one walk of length 2 from
v2 to v3 .
2.

 
3 2 2
 
A2 =  1 0 .
 
2
 
0 0 0
There are 3 walks of length 2 from v1 to v1 , there are 2 walks of length 2
from v1 to v3 .
 21

Proof. (of theorem 2.9) By induction on k.

• k = 1. It is clear by definition of A:
(1)
aij = aij = the number of edges from vi to vj
= the number of walks of length 1 from vi to vj

• We assume that the statement is true for k and prove it for k + 1. We

have Ak+1 = A · Ak , so
n
(k+1) (1) (k)
X
aij = air arj .
r=1

Every walk of length k + 1 from vi to vj is of the form:

– an edge from vi to some vr , followed by
– a walk of length k from vr to vj .

(1) (k)
The number air arj is the number of walks of length k + 1 from vi to vj
(1)
that have vi vr as first step (indeed: air is the number of different edges
(k)
from vi to vr , and arj is the number of different walks of length k from
vr to vj ).
Pn (1) (k)
Therefore r=1 air arj is the number of all possible walks of length k + 1
from vi to vj .
22 CHAPTER 2. GRAPHIC SEQUENCES, ADJACENCY MATRIX
Chapter 3

Eulerian graphs

Definition 3.1. Let G be a connected multigraph.

1. A walk in G is called an Euler trail if it traverses every edge of G exactly
once.
2. An Euler circuit in G is a closed Euler trail (i.e., and Euler trail with the
same first and last vertex).
3. G is Eulerian if it admits an Euler circuit.
Example 3.2.

Has an Euler trail (exercise). It has even more than just one.
Theorem 3.3 (Euler 1736). A connected multigraph is Eulerian if and only if
every vertex has even degree.
Proof. Let G be the graph.
“⇒” We assume that G is Eulerian. Let C be an Euler circuit in G. In
traversing C, every time we “enter” a vertex by an edge, we “leave” it by
another edge, so this contributes 2 to the degree of the vertex (it is alos true for
the first and last edges: they contribute 2 to the degree of the starting vertex)
Since all the edges are in C and G is connected, every vertex appears in C,
and every edge. So each vertex has even degree.
“⇐” We assume that every vertex has even degree. Let W = v0 e0 v1 . . . ek−1 vk
be a longest walk in G with no repeated edge (but vertices can be repeated).
We will show that W is an Euler circuit. We first consider vk more closely:
1. Every edge adjacent to vk appears in W : Because otherwise we could use
an edge vk vk+1 not in W to a walk longer than W , a contradiction.
2. vk = v0 (so W is a closed walk):

v0 e0 v1 e1 v2 . . . vk−1 ek−1 vk
| {z }
we look at this part of W

23
24 CHAPTER 3. EULERIAN GRAPHS

Since every edge adjacent to vk appears in W exactly once, to determine

d(vk ) it suffices to count the adges adjacent to vk as they appear along
W.

• For each i ∈ {1, . . . , k − 1} such that vi = vk (the “inner” vertices

of W equal to vk ), the number d(vk ) increases by 2 (one for the
“arriving” vertex, one for the “leaving” vertex).
• The final part of W : ek−1 increases d(vk ) by one.

This will give an odd number (which is impossible by assumption), unless

v0 e0 contributes to v(vk ), i.e., v0 = vk .

Suppose now that W is not an Euler circuit. Then:

Fact: G has an edge e outside of W but incident with some vertex vi of W (so
e = uvi ).
Proof of the fact: Since W is not en Euler circuit, there is an edge f = w1 w2 in
G that is not in W . Since G is connected, there is a path C from vk to w1:

C = vk f1 z1 f2 z2 . . . z` f`+1 w1 .

By the observation above we know that f1 is in W . We take for e the first

edge in C that is not in W , if it exists. If it does not exist we take e = f . End
of the proof of the fact.
Then the walk
uevi ei . . . ek−1 vk e0 v1 . . . ei−1 vi
has no repeated edges and is longer than W , a contradiction.

Answer to the Königsberg bridge problem:

The problem is represented by the graph

with d(A) = 5, d(B) = 3, d(C) = 3, d(D) = 3, so there is no Euler circuit.

 25

Corollary 3.4. A connected multigraph G has an Euler trail that is not an

Euler circuit if and only if it has exactly two vertices of odd degree.

Proof. “⇒” Let C be an Euler trail in G, starting at v and ending at w. We

add a new edge e joining v and w, and leT G0 = G ∪ {e}.

We then have an Euler circuit in G0 nad, by theorem 3.3, all vertices in G0

have even degree. Therefore all vertices in G have even degree, except v and w,
which have odd degree.
“⇐” Let v and w be the tw overtices of G with odd degree. We add a new
edge e between v and w and get the graph G0 = G ∪ {e}. In G0 all vertices have
even degree, so by theorem 3.3 there is an Euler cricuit C in G0 . Removing e
from C gives an Euler trail in G.
Example 3.5. 1.

has an Euler trail.

2. Adding one bridge in Königsberg will make an Euler trail possible:
26 CHAPTER 3. EULERIAN GRAPHS
Chapter 4

Trees

Definition 4.1. 1. A connected graph with no cycles in called a tree (termi-

nology: “with no cycles” = acyclic).
2. A graph with no cycles is called a forest (because it is the union of its
components, which are connected graphs with no cycles, i.e., trees).
3. The vertices of degree 1 in a tree are called leaves.
Example 4.2. A tree:

A forest:

Lemma 4.3. Let G be a connected graph which contains a cycle C. Let e be

an edge in C. Then G \ {e} is connected.
Proof. Sketch of the proof:

27
28 CHAPTER 4. TREES

In any path, going from u to v via e = uv can be replaced by going around the
“other side” of the cycle.
Theorem 4.4. Let G be a graph of order n. Then the following are equivalent.
1. G is a tree.
2. G is connected and, whenever e is an edge in G, G \ {e} is not connected.
3. G contains no cycle and, whenever x and y are non-adjacent vertices of
G, G ∪ {xy} contains exactly one cycle.
4. G is connected and has n − 1 edges.
5. G contains no cycle and has n − 1 edges.
6. Whenever x and y are vertices in G, there is exactly one path from x to
y in G.
Proof. 1. ⇒ 2. Let e = xy be an edge of G wiht x, y vertices. Suppose that
G \ {e} is connected, and let xv1 . . . vk y be a path in G from x to y. Then
xv1 . . . vk yx is a cycle in G, contradiction.
2. ⇒ 1. We have to show that G contains no cycle. Suppose that v1 v2 . . . vk v1
is a cycle in G.

Then G \ {v1 vk } is connected (by lemma 4.3), contradiction.

2. ⇒ 3. We assume 2. (and thus 1., since 1. ⇔ 2.) Let x, y be non-adjacent
vertices in G. Since G is connected we have a path xv1 . . . vk y from x to y in G.
Thus xv1 . . . vk yx is a cycle in G ∪ {xy}. We have to show that it is the only
cycle:
Suppose we have another cyle C 0 in G ∪ {xy}. Since G contains no cycle, C 0
must contain the edge xy. We write C 0 starting from y: yu1 . . . ur xy, so

Then D = xv1 . . . vk yu1 . . . ur x is a path from x to x in G with at least 2

different edges (since C 6= C 0 ). Then D contains a cycle (same idea as the proof
of proposition 1.30, exercise), contradicting hypothesis 1.
 29

3. ⇒ 1. We know that G contains no cycleco we only need to check that G

is connected. Let x, y be two different vertices in G. If x and y are adjacent,
then there is a path from x to y. If x and y are not adjacent, by hypothesis
there is a cycle in G ∪ {xy}. The “other side” of the cycle gives a path in G
from x to y.
1. ⇒ 4. We proceed by induction on n the number of vertices of G.
• n = 1. Then G has no edges (only one vertex).
• n > 1 and assume that the result holds for graphs with less than n vertices.
Let xy be an edge in G

The graph G \ {xy} is not connected (by property 2).

Let Gx be the component of G\{xy} containing x, and Gy the component
of G \ {xy} containing y. Since G contains no cycle and is connected, we
can check (exercise) that Gx and Gy have no vertices in common and are
the only components of G \ {xy}.
So G = Gx ∪ Gy ∪ {xy} and both Gx and Gy are connected without cycles
(i.e., are trees). Let nx be the order of Gx and ny be the order of Gy . We
have n = nx + ny and thus nx , ny < n, so by induction hypothesis, the
number of edges in Gx is nx − 1 and the number of edges in Gy is ny − 1.
So the number of edges in G is

(nx − 1) + (ny − 1) + |{z}

1 = nx + ny + 1 = n − 1.
for xy

4. ⇒ 1. We will do it after Proposition 4.9 (and we will not use it before).

1. ⇒ 5 Obvious with 4.
5. ⇒ 1. We have to show that G is connected. Suppose not and let
G1 , . . . , Gk be the components of G (k ≥ 2), of respective orders n1 , . . . , nk .
Each Gi is a tree (connected graph with no cycle), so has ni − 1 edges. There-
fore G has (n1 −1)+· · ·+(nk −1) = n−k edges, contradiction to the hypothesis.
(since k ≥ 2).
1. ⇒ 6. Outline: Since G is connected, there is at least one path between
any two vertices. If there were 2 distinct paths there would be a circuit and
then a cycle, contradiction.
6. ⇒ 1. The graph G is connected. It also has no cycles, since otherwise
there would be two different paths between 2 vertices, a contradiction.
Definition 4.5. Let G = (V, E) be a graph, and let H = (V 0 , E 0 ) be a subgraph
of G. If V = V 0 we say that H is a spanning subgraph of G.
30 CHAPTER 4. TREES

If T is a spanning subgraph of G and is also a tree, we call T a spanning

tree of G (it can only exist if G is connected)

Example 4.6. Let G be

then

is a spanning subgraph, and so is

These are examples of two spanning trees of G:

Trees appear naturally to solve the following kind of problem:

Water is to be supplied by pipelines to n villages, such that the pipelines
only meet at villages. Waht is the lest length of pipeline necessary to connect
all villages?
To solve this we need

Definition 4.7. A weighted graph is a graph such that every edge has a positive
number, its weight, attached to it.
The weight of a graph is the sum of the weights of all its edges.

In the case of the problem above, the weight of the edge betwwe 2 villages
is the length of pipeline necessary to connec them. The problem then amounts
to finding a connected subgraph of miminum weight.
 31

Example 4.8. Let G be the (weighted) graph

A minimum weight connected spanning subgraph is

It has weight 17 and it is also a tree. There is in general more than one minimum
spanning graph (here for instance, you can try to find others).

Proposition 4.9. Let G be a connected weighted graph, and let M be a least

weight connected spanning subgraph in G. Then M is a tree.

Proof. M is connected by definition, so we just want to show that M does

not contain any cycle. If M contains a cycle C and e is an edge in C, then
M \ {e} is a connected subgraph of G of weigth less than the weight of M , a
contradiction.

Proof of 4. ⇒ 1. from Theorem 4.4. Let T be a spanning tree of G (take any

minimum weight spanning subgraph of G). Then T has n − 1 edges by 1. ⇒ 4.
Since G has also n − 1 edges, we must have G = T , so G is a tree.

To find a least weight spanning tree in a connected weighted graph, the use
the following:
Kruskal’s algorithm (1956)
Let G = (V, E) be a weighted connected graph of order n. The algorithm
proceeds as follows.

Step 1 Choose an edge e1 of G such that w(e1 ) is as small as possible.

Step 2 If the edges e1 , . . . , ek have already been chosen, choose ek+1 ∈ E \

{e1 , . . . , ek } such that

(i) {e1 , . . . , ek , ek+1 } does not contain a cycle (i.e., ek+1 does not form
a cycle withe other edges from {e1 , . . . , ek }.
(ii) w(ek+1 ) is as small as possible subject to (i).

Step 3 Repeat Step 2 until it is impossible to do so.

32 CHAPTER 4. TREES

Example 4.10. 1. We apply the algorithm to the graph

Step 1: ac, Step 2: ac, cd, Step 2: ac, cd, ab, we stop. The result
is

and has weight 8.

2. We apply the algorithm to the graph

Step 1: ab, Step 2: ab, de, Step 2: ab, de, ef , Step 2: ab, de, ef ,
cb, Step 2: ab, de, ef ,, cb, cd we stop. The result is

and has weight 15.

Theorem 4.11. This algorithm produces a minimal weight spanning tree.
Lemma 4.12. Let G = (V, E) be a connceted graph and let H = (V 0 , E 0 ) be
an acyclic subgraph of G with as many edges as possible. Then H is a spanning
tree of G.
Proof. We first show that H is a spanning subgraph of G, i.e., that V 0 = V .
Suppose there is v ∈ V such that v 6∈ V 0 . Let w ∈ H. Since G is connected
there is apath P = w0 w1 . . . wk wk+1 in G from w to v.
|{z} | {z }
=w =v
We take such a path with the minimum number of edges outside E 0 . Since
v 6∈ V 0 , the edge wk v is not in E 0 .
 33

Let wi wi+1 be the first edge not in H. So wi−1 wi ∈ E 0 and thus wi ∈ V 0 .

If wi+1 6∈ H we can add the edge wi wi+1 to H (it will not create a cycle),
contradicting the definition of H. So wi+1 ∈ H, and we cannot add wi wi+1 to
H, i.e., H ∪ {wi wi+1 } contains a cycle C = wi+1 wi u1 . . . u` wi+1

Therefore ww1 . . . wi u1 . . . u` wi+1 . . . wk v is a path in G from w to v with

less edges not in E 0 than P, contradiction.
We now show that H is a tree. We know that H is acyclic, so we only have
to show that H is connected. Let H1 , . . . , Ht be the components of H (they are
trees), and assume t ≥ 2.
Since G is connected and H contains all vertices of G, there is an edge
e ∈ E \ E 0 such that e connects H1 and Hi for some i > 1 (take a vertex x in
H1 , y a vertex in H2 and a path P in G from x to y. Take for e the first edge
not in H1 ).
Then we can add e to H without creating a cycle (if it created a cycle, the
“other side” of the cycle could connect H1 and Hi in H, impossuble), contra-
dicting the definition of H.
Proof of Theorem 4.11. Let H be the graph produced by the algorithm. By
lemma 4.12 it is a spanning tree.
Let e1 , . . . , en−1 be the edges of H (where n is the number of vertices of G,
i.e., of H), in the order in which they are added by the algorithm.
If T is a different spanning tree of G, there is an edge of H that is not in T :
Otherwise T would have more edges that H, which is impossible (they are both
trees with n vertices).
We denote by f (T ) the smallest i such that ei is not in T .
Assume now that H is not a minimal weight spanning tree and let T be a
minimal weight spanning tree with f (T ) as large as possible. Let k = f (T ),
i.e., e1 , . . . , ek−1 are in H and T , but ek is not in T . By theorem 4.4, T ∪ {ek }
contains a unique cycle C. Let e0k be an edge in C that is in T but not in H
(there is such an edge: if every edge of T that is in C (=all edges of C, except
ek ) were in H, we would have C in H (since ek ∈ H), contradiction).
Since C is a cylcle, T 0 = (T ∪ {ek }) \ {e0k } is connected and has n − 1 edges.
So by theorem 4.4 T 0 is another spanning tree of G. Clearly:
w(T 0 ) = w(T ) + w(ek ) − w(e0k ).
In Kruskal’s algorithm, ek was chosen with the smallest weigth such that {e1 , . . . , ek }
is acyclic. Since {e1 , . . . , ek−1 , e0k } is a subgraph of T , it is also acyclic, so we
must have w(e0k ) ≥ w(ek ). Therefore w(T 0 ) ≤ w(T ) and T 0 is a minimal weight
spanning tree. However:
f (T 0 ) > k = f (T ),
| {z }
since e1 , . . . , ek are in T0

contradicting the choice of T .

34 CHAPTER 4. TREES
Chapter 5

Hamiltonian graphs

Definition 5.1. A Hamiltonian path in G is a path that contain every vertex

of G exactly once.
A Hamiltonian cycle is a closed Hamiltonian path.
A graph which contains a Hamiltonian cycle is called a Hamiltonian graph.

Example 5.2. 1. A Hamiltonian path:

2. A Hamiltonian cycle:

3. On a chessboard, can a knight visit every square exactly once and finish at
its starting point?

Recall that a knight move is:

35
36 CHAPTER 5. HAMILTONIAN GRAPHS

The answer is yes:

In terms of graph theory: Let G = (V, E) where V is the set of all sqaures
of the chessboard, and there is an edge between two vertices if we can go
from one to the other by a knight move.
A solution to this problam is a Hamiltonian cycle. Observe that there are
several different solutions to this problem.

4. It is related to the traveling salesman problem: A salesman wants to visit

some cities exactly once and go back to his starting point. What is the
path with minimum distance? (mathematically formulated by Hamilton)
On a weighted graph, it means finding a Hamilton cycle of minumum
weight.

5.

This graph is not Hamiltonian: It has vertices of degree 1 and a vertex of

degree 1 cannot be in a cycle. So for a graph to be Hamiltonian we need
each vertex to have degree at least 2. But it is not enough (we will see
graphs like this that are not Hamiltonian).

6. A circuit is a Hamiltonian graph (obviously).

7. The complete graph Kn for n ≥ 3 is Hamiltonian:

 37

• Enumerate the vertices from 1 to n (in any way).

• Start at the first one, go to the second, then the third, . . . , then the
nth one, then go back to the first. It can be done since any two
different vertice are always connected.
Theorem 5.3. Let G = (V, E) be a Hamiltonian graph. Then for any subset S
of V with S 6= ∅ and S 6= V , we have

ω(G \ S) ≤ |S|.

(Recall that ω(G \ S) denotes the number of components of G \ S.)

Proof. Let n = |V | and let G1 , . . . , Gk be the components of G \ S. Let C =
v1 v2 . . . vn v1 be any Hamiltonian cycle in G, labelled such that v1 ∈ G1 .
Let i ∈ {1, . . . , k} and consider the component Gi . Since every vertex of G
appears in C, and at least one element of C is not in Gi (for instance an element
of S), we can define ui to be the last element of C that belongs to Gi . Let si
be the vertex after ui in C.
Then si 6∈ Gi , which implies si ∈ S (otherwise si ∈ G \ S, the edge ui si is
in G \ S, so si is connected to ui and thus belongs to Gi , a contradiction).
So each component Gi of G \ S defines an element si ∈ S, and si 6= sj if
i 6= j (if si = sj for i 6= j then ui = uj ∈ Gi ∩ Gj , impossible). The map
{1, . . . , k} → S, i 7→ si is thus injective, proving that k ≤ |S|.
Example 5.4. The Herschel graph:

is not Hamiltonian: If we take for S the set of blue vertices, then G \ S is

so ω(G \ S) = 6 > |S| = 5.
Exercise 5.5. Show that this graph is not Hamiltonian:

Theorem 5.6 (Bondy, Chvátal, 1972). Let G be a graph of order n and let
u, v be any non-adjacent vertices of G such that d(u) + d(v) ≥ n. Then G is
Hamiltonian if and only if G ∪ {uv} is Hamiltonian.
Proof. “⇒” Let C be a Hamilton cycle in G. Then C is also a Hamilton cycle
in G ∪ {uv}.
“⇐” Suppose that G is not Hamiltonian. Then any Hamilton cycle in G ∪
{uv} must include the edge uv (otherwise it would be a Hamilton cycle in G).
38 CHAPTER 5. HAMILTONIAN GRAPHS

Removing the edge uv, we get a path from u to v in G that contains every
vertex exactly once (a Hamiltonian path). Let

v1 v2 . . . vn−1 vn
|{z} |{z}
=u =v

be this path.
If v1 is adjacent to vi , then vn cannot be adjacent to vi−1 , because otherwise

v1 v2 . . . vi−1 vn vn−1 . . . vi+1 vi v1

would be a Hamilton cycle in G, a contradiction. So whenever v1 is adjacent to

vi , vn is not adjacent to vi−1 .
Therefore, if k = d(v1 ) there are k vertices to which v1 is adjacent and k
vertices to which vn is not adjacent. So d(vn ) ≤ n − 1 − k. But then

d(u) + d(v) = d(v1 ) + d(vn ) ≤ k + n − 1 − k = n − 1 < n,

contradicting the hypothesis.

Conclusion: Whenever we find two vertices u, v such that d(u)+d(v) ≥ n, we
can add the edge uv and the answer to the question “is the graph Hamiltonian?”
stays the same. We can keep doing this until we cannot add any new such edge:
Definition 5.7. Let G be a graph of order n. The closure of G is the graph
c(G) obtained by successively joining pairs of non-adjacent vertices u, v such
that d(u) + d(v) ≥ n (degree computed in the latest graph obtained), until it is
no longer possible to do so.
Example 5.8. 1.

2.

We must show that c(G) does not depend on the order in which the edges
are added to G (otherwise we could have several possible c(G) for a given graph
G).
Lemma 5.9. c(G) does not depend on the order in which we add the vertices.
 39

Proof. Suppose G1 , G2 are obtained from G as described in Definition 5.7. We

show that G1 = G2 . They have the same vertices, so we have to show that they
have the same edges.
Let e1 , . . . , er and f1 , . . . , fs be the sequences of edges added to G to obtain
G1 , respectively G2 . We show that all ei are edges of G2 and all fi are edges of
G1 :
Suppose that some edge in e1 , . . . , er is not in G2 and let ek1 = uv be the
first such edge. Let H = G ∪ {e1 , . . . , ek }. Since ek+1 = uv is added next, we
have dH (u) + dH (v) ≥ n (where dH is the degree computed in H). But H is a
subgraph of G2 since e1 , . . . , ek appear in G2 , so dG2 (u) + dG2 (v) ≥ n, and we
will thus join u and v at some point in the construction of G2 , contradiction.
Therefore e1 , . . . , er are all in G2 . Similarly f1 , . . . , fs are all in G1 .

Corollary 5.10. G is Hamiltonian if and only if c(G) is Hamiltonian.

(This is clear by Theorem 5.6.)

Corollary 5.11. Let G be a graph of order n ≥ 3 such that c(G) = Kn . Then

G is Hamiltonian.

Corollary 5.12 (Ore’s theorem, 1963). Let G be a graph of order n ≥ 3 such

that the sum of the degrees of every pair of non-adjacent vertices is at least n.
Then G is Hamiltonian.

Proof. In this case we have c(G) = Kn .

Corollary 5.13 (Dirac’s theorem, 1952). Let G be a graph of order n ≥ 3. If

the degree of every vertex is at least n/2 then G is Hamiltonian.

This leads to a more general sufficient condition for a graph to be Hamilto-

nian:

Theorem 5.14 (Chvátal, 1972). Let G = (V, E) be a connected graph of order

n ≥ 3 and degree sequence d1 ≤ d2 ≤ · · · ≤ dn such that for every k with
1 ≤ k < n/2 at least one of the follwing is true:

(i) dk > k (ii) dn−k ≥ n − k.

Then G is Hamiltonian.

Proof. We show that c(K) = Kn : Suppose that c(G) 6= Kn . if w is a vertex in

G, we denote by d0 (w) the degree of w in c(G). Let d01 ≤ d02 ≤ · · · ≤ d0n be the
degree sequence of c(G). Note that d(w) ≤ d0 (w) and di ≤ d0i .
Let u, v ∈ V be non-adjacent in c(G), and choose them such that

d0 (u) + d0 (v) is as large as possible. (5.1)

Choose the labels u, v such that d0 (u) ≤ d0 (v). Note that

d0 (u) + d0 (v) < n, (5.2)

otherwise u and v would be connected in c(G). Thus 2d0 (u) ≤ d0 (u) + d0 (v) < n
and d0 (u) < n/2.
40 CHAPTER 5. HAMILTONIAN GRAPHS

Let k = d0 (u). Since G is connected, k ≥ 1, so

1 ≤ k < n/2. (5.3)

We show that k does not satify conditions (i) and (ii), thus reaching a contra-
diction:
For any vertex x, let N (x) be the set of vertices different from x that are
not adjacent to x in c(G). Then

|N (x)| = n − d0 (x) − 1. (5.4)

Let w ∈ N (v). Then d0 (w) led0 (u) (otherwise d0 (w) + d0 (v) > d0 (u) + d0 (v),
contradicting (5.1)). Similarly, if x ∈ N (u) we have d0 (x) ≤ d0 (v), so for every
x ∈ N (u) ∪ {u} we have
d0 (x) ≤ d0 (v) (5.5)
(recall that d0 (u) ≤ d0 (v)).
By (5.2) we have d0 (u) < n − d0 (v), so d0 (u) ≤ n − d0 (v) − 1 = |N (v)| i.e.,
k ≤ |N (v)|, we have at least k vertices in N (v).
Consider now a vertex w ∈ N (v). We know that d0 (w) ≤ d0 (u) = k, so we
have at least k vertices in c(G) with degree at most k, and thus in the degree
sequence of c(G) at least d01 , . . . , d0k are at most k. In particular

dk ≤ d0k ≤ k. (5.6)

Using (5.3) with (5.6) we get dk < n/2, so condition (i) is not true.
With (5.2) we obtain d0 (v) < n − d0 (u) = n − k, and by (5.5) d0 (x) < n − k
for every x ∈ N (u) ∪ {u}.

|N (u) ∪ {u}| = |N (u)| + 1

= (n − 1 − d0 (u)) + 1 by (5.4)
0
= n − d (u) = n − k.

Therefore we have at least n − k vertices of degree less than n − k in c(G), so

at least d01 , d02 , . . . , d0n−k are less that n − k. In particular dn−k ≤ d0n−k < n − k,
so condition (ii) is also not satisfied.
Example 5.15. 1.

n = 5, degree sequence 2, 3, 3, 3, 3. Since n = 2 we need to consider

k = 1, 2.
d1 = 2 > 1, and d2 = 3 ≥ 2,
so this graph is Hamiltonian by Chvátal’s theorem.
In this case we could also use Ore’s theorem or simply check that c(G) =
K5 .
See exercise sheets for a graph where Chvátal’s theorem works, but not
Ore’s.
 41

2. It is possible for a graph to be Hamiltonian without satisfying Chvatal’s

condition:

G is clearly Hamiltonian, with degree sequence 2, 2, 2, 2, 2 and n = 5. So

1 ≤ k < n/2 means k = 1, 2. We have d1 = 2 > 1, but d2 = 2 > 6 2 and
d5−2 = d3 = 2 6≥ 3.
We have seen two notions of “traversability”: Edgewise (Eulerian graphs)
and vertexwise (Hamiltonian graphs). It is easy to check if a graph is Eulerian,
harder to check if it is Hamiltonian. And there is no obvious link between these
two notions:
42 CHAPTER 5. HAMILTONIAN GRAPHS
Chapter 6

Graph isomorphisms

We already used this concept without defining it formally. The graphs

are “the same”.

Definition 6.1. Let Gq = (V1 , E1 ) and G2 = (V2 , E2 ) be graphs. We say that
G1 is isomorphic to G2 if an d only if there is a bijection f : V1 → V2 such that,
for every u, v ∈ V1 :
uv ∈ E1 ⇔ f (u)f (v) ∈ E2 .
∼
We write G1 = G2 and say that f is an isomorphism from G1 to G2 (or between
G1 and G2 ).
In the example above, the map f could be:
5 7→ a, 6 7→ b, 4 7→ f, 3 7→ c, 2 7→ d, 1 7→ e
(there may be more than one such map f ).
Remark 6.2. In case of a multigraph (where there can be parallel edges) an
isomorphism f from G1 to G2 is given by two bijections: fv : V1 → V2 and
fe : E1 → E2 such that, for every u, v ∈ V1 and e ∈ E1 :
e is an edge between u and v ⇔ fe (e) is an edge between fv (u) and fv (v).
Remark 6.3. 1. Isomorphic graphs have:
-The same order;
-The same size;
-The same degree sequence (it follows from the definition that d(u) =
d(f (u)));
-etc.

43
44 CHAPTER 6. GRAPH ISOMORPHISMS

2. In fact, if G1 ∼
= G2 , every graph-theoretic property of G1 can be “trans-
lated” into the corresponding property of G2 , using f .
3. If f is an isomorphism from G1 to G2 , then f −1 is an isomorphism from
G2 to G1 .
Example 6.4. 1.

Here G1 ∼
= G2 . A possible isomorphim is

f (v1 ) = w1 , f (v2 ) = w3 , f (v3 ) = w5 , f (v4 ) = w2 , f (v5 ) = w4 .

2. The graphs

are not isomorphic: Suppose for the sake of contradiction that they are,
and let f be the isomorphism. Since d(u) = d(f (u)) we must have d(f (1)) =
d(1) = 3, d(f (2)) = d(2) = 2, d(f (3)) = 2, d(f (4)) = 3, d(f (5)) = 3,
d(f (6)) = 2, d(f (7)) = 1. Since 7 is the only vertex of degree 1 in G2 , we
must have f (7) = 7. 47 is an edge in G1 , so f (4)f (7) = f (4)7 is an edge
in G2 . So f (4) = 4.
5 is adjacent to 4, so f (5) is adjacent to f (4) = 4, so f (5) = 5 or f (5) = 3.
But dG1 (5) = 3 and dG2 (5) = 2, dG2 (3) = 2, so we cannot have f (5) = 5
or f (5) = 3. So G1 and G2 are not isomorphic.

3. In general, the question of checking if two graphs are isomorphic is very

difficult.
Chapter 7

Bipartite graphs

Definition 7.1. A graph G = (V, E) is bipartite if the following hold

1. V = X ∪ Y for some sets X, Y with X ∩ Y = ∅;
2. For every edge uv in E, one of u, v is in X and the other in Y .
The pair (X, Y ) is called a bipartition of G.
Example 7.2.

is bipartite with X = {1, 2, 3} and Y = {4, 5, 6}.

Definition 7.3. If X and Y are two disjoint sets such that X has r elements
and Y has s elements, the complete bipartite graph Kr,s is the graph with set of
vertices X ∪ Y and set of edges {uv | u ∈ X, v ∈ Y }.
Example 7.4.

Definition 7.5. A cycle C in a graph is called an odd cycle if C has an odd

number of edges.
Theorem 7.6. A graph is bipartite if and only if it contains no odd cycles.
To obtain a simple proof of this theorem, we require a little bit more knowl-
edge about trees.
Recall that if T is a tree and x, y are vertices in T , there is a unique path in
T from x to y. We denote this path by xT y.

45
46 CHAPTER 7. BIPARTITE GRAPHS

It is sometimes convenient to single out a vertex in a tree T . Such a vertex

is then called the root of T (it can be any vertex). A tree T with a fixed root r
is called a rooted tree.
Example 7.7.

(We can take any vertex as a root.)

Proof of Theorem 7.6. “⇒” If C = u1 . . . ur (with ur = u1 ) is an odd cycle,
then ur−1 and u1 must be both in X or both in Y , impossible.
“⇐” A graph is bipartite if and only if its components are bipartite, so we
can assume that G is connected. The result is clear if G has only 2 vertices, so
we will assume that G has at least 3 vertices.
Let T be a spanning tree of G, and pick a root r of T . For v ∈ V the path
rT v has odd or even length. We define

X = {v ∈ V | rT v has odd length},

Y = {v ∈ V | rT v has even length}.

We check that (X, Y ) is a bipartition of G: Let e = xy be an edge in G. We
consider two cases
1) e ∈ T : Observe that x ∈ rT y or y ∈ rT x (otherwise

and we obtain a cycle in T , contradiction).

We assume x ∈ rT y (the other case is similar).

Since e = xy is an edge in T , we must have rT y = rT xy (otherwise we get a

cycle in T ). So one of x, y is in X and the other in Y .
 47

2) e 6∈ T . Then xT y ∪ {e} is a cycle:

The edges in xT y are all in T so, by case 1, the vertices in xT y alternate between
X and Y . Since xT y∪{e} is even by hypothesis, we get that xT y has odd length,
and thus that x and y cannot be both in X or both in Y .
48 CHAPTER 7. BIPARTITE GRAPHS
Chapter 8

Planar graphs

Definition 8.1. A graph is called planar if it can be drawn in the plane so that
edges intersect only at vertices to which they are incident.
Example 8.2. Different representations of K4 :

Definition 8.3 (Continued). Such a representatiopn of G without edge cross-

ings is called a planar representation (or planar embedding) of G.
Definition 8.4. A planar representation of G divides the planed into regions
called faces:
Let x be a point in the plane. The face of G (more precisely: of this planar
representation of G) containing x is the set of points of the plane that can be
reached from x by a curve that does not contain a vertex or a point from an
edge.
Example 8.5.

This planar representation of K4 divides the plane into 4 faces: A, B, C and

D. The face containing x is D.
The faces depend on the particular plane representation, not only on the
graph.
Each plane representation partitions the plane into finitely many faces. Ex-
actly one is infinite in size, we call it the exterior face. The other faces are called
interior faces.
Do two different plane representations give the same number of faces? (Yes,
Euler, see theorem 8.13.

49
50 CHAPTER 8. PLANAR GRAPHS

We denote by F (G) the set of faces of a given planar representation of G

(we will make the slight abuse of notation of still calling it G).

Definition 8.6. Let G be a graph. An edge e of G is called a cut-edge if

ω(G \ {e}) > ω(G).
(Recall that ω(G) is the number of components of G.)

Proposition 8.7. An edge e of G is a cut edge if and only if e is not contained

in any cycles of G.

Sketch of the proof: Let K be the component of G containing e = uv.

“⇒” Then ω(K \ {e}) > 1. If e is in a cycle in K, then K \ {e} is still
connected, contradiction.
“⇐” If e is not a cut-edge ω(K \ {e}) = 1, so K \ {e} is connected. Let
uw1 . . . wk v be a path in K \ {e}. Then uw1 . . . wk vu is a cycle in K, contradic-
tion.

We record the following reformulation of Theorem 4.4 1. ⇔ 2.

Proposition 8.8. A connected graph is a tree if and only if every edge is a cut
edge.

Definition 8.9. Let G be a plane representation of a planar graph. An edge e

is called incident with a face f if e is part of the boundary of f .

Definition 8.10. The degree d(f ) of a face f is the number of edges incident
with f , where each edge entirely inside f (called a pendant edge) is counted
twice.

Why counted twice? Because we count the sides of the edge that are in contact
with f (see the proof of Proposition 8.12), in case of a pendant edge, both sides
of the edge in contact with f .
 51

Example 8.11.

d(f1 ) = 5, d(f2 ) = 3, d(f3 ) = 12, d(f4 ) = 3, d(f5 ) = 3.

Proposition 8.12. Let F be the set of faces of a planar graph G = (V, E).
Then X
d(f ) = 2|E|.
f ∈F

Proof. If an edge is between 2 faces, it is counted twice on the left-hand side

(once for each face).
If a face is entirely inside a face f , it is counted twice in d(f ) by definition.

Observe that we can have different planar representations of the same graph,
with different degree sequences of the face:

degree sequence of the faces: 5, 3, 6,

degree sequence of the faces: 5, 5, 4.

Theorem 8.13 (Euler’s formula). Let G = (V, E) be a connected planar graph,

and consider a planar representation of G with set of faces F . Then

|V | − |E| + |F | = 2.
52 CHAPTER 8. PLANAR GRAPHS

Example 8.14.

|V | − |E| + |F | = 4 − 6 + 4 = 2.
Proof of Theorem 8.13. By induction on |E|.
• If |E| = 0, then G is

and |V | − |E| + |F | = 1 + 1 = 2.
• If |E| = 1, then G is

and |V | − |E| + |F | = 2 − 1 + 1 = 2.
• If |E| > 1. We consider two cases.
Case 1: If G is a tree. Then |E| = |V | − 1 and |F | = 1 since a tree has only
one face (we admit this: a tree has only the exterior face since to have an
interior face it would need to have a cycle). So |V | − |E| + |F | = 2.
Case 2: If G is not a tree. Then (since G is connected) G contains a cycle
C. Let e be an edge in C. Since e is not a cut edge, G \ {e} is connected,
and has of course |E| − 1 edges.
Since e is on a cycle, it separates 2 faces (we admit this), so removing e
merges these two faces, and thus G \ {e} has |F | − 1 faces.
By induction on |E|, the result is true for the graph G \ {e} i.e., |V | −
(|E| − 1) + (|F | + 1) = 2 i.e., |V | − |E| + |F | = 2.

Corollary 8.15. Let G = (V, E) be a planar graph with |V | ≥ 3. Then |E| ≤

3|V | − 6.
(In other words: We cannot have “too many” edges compared to the number
of vertices.)
Proof. We consider two cases.
Case 1: G is connected. The result is true if |E| < 3 (since 3 ≤ 3 · 3 − 6), so
we assume |E| ≥ 3.
Let F be the set of faces of a planar embedding of G. For any f ∈ F ,
d(f ) ≥ 3 (if f is an interior face it has at least 3 edges in its boundary, since
parallel edges are not allowed; if f is the exterior face and d(f ) = 2 then G is

contradicting
P that |E| ≥ 3). P
So f ∈F d(f ) ≥ 3 · |F |. But we know that f ∈F = 2|E|, so 2|E| ≥ 3|F |
i.e., |F | ≤ 23 |E|. Using now Euler’s formula, we obtain
2 1
2 = |V | − |E| + |F | ≤ |V | − |E| + |E| = |V | − |E|.
3 3
 53

Therefore |E| ≤ 3|V | − 6.

Case 2: If G is not connected. Write G = G1 ∪ · · · ∪ Gk , where the Gi are
the components of G. Connect the components by adding k − 1 new edges while
still keeping the graph planar (for instance: arrange the components around a
circle, and connect G1 to G2 , G2 to G3 , etc). The resulting graph is connected
and has |E| + (k − 1) edges. By the previous case |E| + k − 1 ≤ 3|V | − 6 and
the result follows.

Corollary 8.16. Let G = (V, E) be a planar graph. Then some vertex of G has
degree at most 5.

Proof. Let n = |V |. If n = 1 or n = 2 the result is clear, so assume n ≥ 3. Let

d be the smallest degree of any vertex in G. We have E ≤ 3n − 6 and
X
nd ≤ d(V ) = 2|E| ≤ 2(3n − 6),
v∈V

12
i.e., nd ≤ 6n − 12 so d ≤ 6 − n and thus d ≤ 5.

Corollary 8.17. The graph K5 is not planar.

Recall that K5 is

Lemma 8.18. The graph K3,3 is not planar.

Recall that K3,3 is

Proof. Suppose it is and consider a planar representation of K3,3 . Since K3,3 is

bipartite, it contains no odd cycles, so there are no cycles of length less than 4
(since a cycle of length less than 4 has length P 3).
So d(f ) ≥ 4 for every face, and 2|E| = f ∈F d(f ) ≥ 4 · |F |. Therefore
|E| ≥ 2|F |. Since K3,3 has 9 edges we get 9 ≥ 2 · |F | i.e., |F | ≤ 4. But
|V | − |E| + |F | = 2 i.e., 6 − 9 + |F | = 2, so |F | = 5, contradiction.

Example 8.19. We want to provide gas, water and electricity to 3 houses. It

cannot be done without crossing some of the lines, because it corresponds to the
graph K3,3 :
54 CHAPTER 8. PLANAR GRAPHS

Definition 8.20. Let G = (V, E) be a graph, and let e = uv be an edge in G.

We say that we subdivide the edge e when we delete it and replace it by a path
uwv, where w is a new vertex (i.e., w 6∈ V ):

We say that e has been subdivided. A subdivision of G is a graph that can

be obtained from G by a sequence of subdivisions.
Example 8.21.

H is a subdivision of K4 .
The next two lemmas are obvious.
Lemma 8.22. Let G be a graph. G is planar if and only if every subdivision
of G is planar if and only if one of the subdivisions of G is planar.
Lemma 8.23. Let G be a graph. G is planar if and only if every subgraph of
G is planar.
(Recall that G is a subgraph of G.)

Definition 8.24. Any subdivision of K5 or of K3,3 is called a Kuratowski graph.

A K-subgraph is a subgraph that is a Kuratowski graph.
By Lemma 8.22, a Kuratowski graph is non-planar, and by Lemma 8.23, a
graph with a K-subgraph is non-planar. The converse is also true:

Theorem 8.25 (Kuratowski, 1930). A graph is planar if and only if it does not
contain a K-subgraph.
No proof (too long).
Chapter 9

Networks

Stuttgart 1968: A new road is built. Consequence: The traffic gets worse until
the road is closed.
New York 1990: 42nd street is closed. Consequence: The traffic improves.
(Braess paradox)
We are not quite going to look into this, because it is also caused by drivers
trying to maximise apparent immediate gain rather than thinking about longer-
term consequences, but it illustrates why looking at how “things” can move in
a network is interesting.

Definition 9.1. A directed pseudograph (DPG) is a triple (V, E, ψ), where

• V is a non-empty set of points, called vertices.

• E is a set, disjoint from V , whose elements are called arcs.

• ψ is a map, called the incidence function, that associates to each arc in E

an ordered pair of vertices of V (the vertices may be equal).

Example 9.2.

V = {1, 2, 3, 4}, E = {a, b, c, d, e, f, g, h}

ψ(a) = (1, 2), ψ(b) = (1, 4), ψ(c) = (4, 4), ψ(d) = (4, 4), ψ(e) = (3, 4),
ψ(f ) = (2, 3), ψ(g) = (3, 2), ψ(h) = (3, 2).
We cannot simply represent an arc by, for instance, (3, 2), because there can
be several such arcs. So we give them all a different name and use the incidence
function to tell us from where to where they go.

Definition 9.3. Let D = (V, E, ψ) be a DPG.

55
56 CHAPTER 9. NETWORKS

1. A directed walk W in D is a sequence W = (v0 , a1 , v1 , a2 , . . . , ak , vk ) with

vi ∈ V , ai ∈ E, and such that ψ(ai ) = (vi−1 , vi ) for i = 1, . . . , k.
We define similarly directed paths, cycles, etc.
2. A walk in D is a sequence W = (v0 , a1 , v1 , a2 , . . . , ak , vk ) with vi ∈ V , ai ∈
E, and such thatfor i = 1, . . . , k, ψ(ai ) = (vi−1 , vi ) or ψ(ai ) = (vi , vi−1 )
(in this later case we say that ai is a reverse arc of W ).
We define similarly paths, cycles, etc.
Example 9.4. Using the DPG from the previous example, (1, b, 4, c, 4, d, 4, c, 4)
is a directed path, and (1, b, 4, c, 4, e, 3) is a path which is not a directed path (e
is a reverse arc).
Definition 9.5. Let D = (V, E, ψ) be a DPG. For v ∈ V we define
d+ (v) = the in-degree of v
= the number of arcs that end at v

d− (v) = the out-degree of v

= the number of arcs starting at v
Example 9.6.

d+ (v1 ) = 0, d− (v1 ) = 3, d+ (v2 ) = 1, d− (v2 ) = 1, d+ (v3 ) = 3, d− (v3 ) = 0.

Proposition 9.7. Let D = (E, V, ψ) be a DPG. Then
X X
d+ (v) = d− (v) = |E|.
v∈V v∈V

Proof. Exercise, see Proposition 1.21.

Definition 9.8. A network is a DPG (V, E, ψ) together with two non-empty
subsets of V :
• S, called the source, such that d+ (v) = 0 for every v ∈ S;
• T , called the sink, such that d− (v) = 0 for every v ∈ T .
The remaining vertices are called intermediate vertices.
(In networks, vertices are often called nodes.)
Example 9.9. N = (E, V, ψ, S, T ) is a network:
 57

with S = {s1 , s2 }, T = {t} and intermediate vertices a, b, c.

Intuitively: S gives the entrance points, and T the exit points of the network.
Definition 9.10. Let D = (V, E, ψ) be a DPG. A capacity on D is a function
c : E → R+ = {x ∈ R | x > 0}.
Example 9.11.

Intuitively, the capacity represents how much can travel along an arc.
Definition 9.12. Let N = (V, E, ψ, S, T ) be a network and let c be a capacity
on N . A flow on N is a function f : E → R+ ∪ {0} such that
1. 0 ≤ f (e) ≤ c(e) for every e ∈ E.
2. For every intermediate vertex v, the in-flow:
def X
f+ (v) = f (e)
e∈E,ψ(e)=(u,v)

is equal to the out-flow:

def X
f− (v) = f (e)
e∈E,ψ(e)=(v,u)

(this is known as Kirchhof ’s rule).

Example 9.13. With the capacity given by the previous example, this is a flow
(where S = {v1 } and T = {v3 }:

We often write

to indicate both the capacity and the flow at the same time on the drawing. (So,
for instance, 2/5 is not a fraction. It just means that the arc has capacity 5 and
that the flow on it is 2.)
58 CHAPTER 9. NETWORKS

The flow represents what is actually circulating in the network.

A more complicated example:

Question: For a given network and capacity, what is the “largest” possible
flow, and how to find it?
Examples of applications: Electric circuits, pipelines, transportation sys-
tems, etc.

Lemma 9.14. Let f be a flow on a network N = (V, E, ψ, S, T ) with capacity

c. Then X X
f− (s) = f+ (t) .
s∈S t∈T
| {z } | {z }
out-flow from the source in-flow to the sink

Proof. We have
X X X X
(f+ (w) − f− (w)) = (f+ (w) − f− (w)) + f+ (t) − f− (s).
w∈V w∈I t∈T s∈S
| {z }
=0 by def of flow
P
So the result is true if we show that w∈V (f+ (w) − f− (w)) = 0.
Consider an arc e ∈ E:

P
In the sum w∈V (f+ (w) − f− (w)) the number f (e) appearsP twice: Once as
f (e) in f+ (v)−f− (v), once as −f (e) in f+ (u)−f− (u). Therefore w∈V (f+ (w)−
f− (w)) = 0.

Notation 9.15. We define, for A, B ⊆ V :

P
• f (A, B) = e∈E,e from A to B f (e).

• f− (A) = f (A, V \ A) (what “leaves” A).

• f+ (A) = f (V \ A, A) (what “enters” A).

(The previous lemma says f− (S) = f+ (T ).)

Lemma 9.16. For any A ⊆ V :

X
f− (v) − f+ (v) = f− (A) − f+ (A).
v∈A
 59

Proof. Exercise.
P P
Remark 9.17. In general, v∈A f− (v) 6= f− (A) and v∈A f+ (v) 6= f+ (A).
Try it for instance on

for some sets A and some simples capacity and flow.

Definition 9.18. The value of a flow f is

v(f ) = f− (S) = f+ (T ).

Can we construct a flow with maximal possible v(f )?

Definition 9.19. A cut in a network N = (V, E, ψ, S, T ) is a pair (VS , VT ) of

subsets of V such that

1. V = VS ∪ VT .

2. VS ∩ VT = ∅ (so VS = V \ VT and VT = V \ VS ).

3. S ⊆ VS .

4. T ⊆ VT .

Example 9.20.

The green (VS , VT ) and the red (VS , VT ) are both cuts.
60 CHAPTER 9. NETWORKS

It is called a cut because it cuts N into two parts: one that contains S and
the other that contains T .

Definition 9.21. The capacity of a cut (VS , VT ) is defined by

X
c(VS , VT ) = c(e).
e∈E,e from VS to VT

Example 9.22.

Here c(VS , VT ) = 2 + 2 + 3 = 7.

Lemma 9.23. For any flow f and any cut (VS , VT ) on N :

v(f ) = f− (VS ) − f+ (VS ).

Proof. If v ∈ VS \ S(= I ∩ VS ) we have f− (v) − f+ (v) = 0 by definition of flow.

So
X
f− (VS ) − f+ (VS ) = f− (v) − f+ (v) by Lemma 9.16
v∈VS
X

= f− (v) − f+ (v)
| {z }
v∈S
=0 since v∈S
= f− (S)
= v(f )

Notation 9.24. We say that an arc e ∈ E is

• f -zero if f (e) = 0;

• f -positive if f (e) > 0;

• f -saturated if f (e) = c(e);

• f -unsaturated if f (e) < c(e).

Theorem 9.25. For any flow f and any cut (VS , VT ) on N :

1. v(f ) ≤ c(VS , VT );

2. v(f ) = c(VS , VT ) if and only if each arc from VS to VT is f -saturated and

each arc from VT to VS is f -zero.
 61

Proof. 1. By Lemma 9.23 v(f ) = f− (VS ) − f+ (VS ) where

def
f− (VS ) = f (VS , V \ VS )
= f (VS , VT )
X
= f (e)
e∈E,e from VS to VT
X
≤ c(e)
e∈E,e from VS to VT

= c(VS , VT ).
Since f+ (VS ) ≥ 0 we obtain v(f ) ≤ c(VS , VT ).
2. To have v(f ) = c(VS , VT ) we must have
• f− (VS ) = c(VS , VT ), so every arc from VS to VT must be f -saturated.
• f+ (VS ) = 0, so every arc from VT to VS must be f -zero.

Definition 9.26. 1. A flow f on N is called a maximim flow if there is no

flow f 0 on N such that v(f 0 ) > v(f ).
2. A cut (VS , VT ) on N is called a minimum cut if there is no cut (VS0 , VT0 )
on N such that c(VS0 , VT0 ) < c(VS , VT ).
As a consequence of theorem 9.25, if f ∗ is a maximum flow and (VS∗ , VT∗ ) is
a minimum cut, then
v(f ∗ ) ≤ c(VS∗ , VT∗ ).
Corollary 9.27. Let f be a flow and (VS , VT ) be a cut such that v(f ) =
c(VS , VT ). Then f is a maximum flow and (VS , VT ) is a minimum cut.
Proof. Let f ∗ be a maximum flow and (VS∗ , VTT ) be a minimum cut. Then
v(f ) ≤ v(F ∗ ) ≤ c(VS∗ , VT∗ ) ≤ c(VS , VT ),
and v(f ) = c(VS , VT ) by hypothesis. Therefore
v(f ) = v(f ∗ ) and c(VS , VT ) = c(VS∗ , VT∗ ).

Let f be a flow in a network N with capacity c, and let P be a path in N .

For an arc a in P we define:
(
c(a) − f (a) if a is a forward arc in P
i(a) =
f (a) if a is a reverse arc in P
and
i(P ) = min i(a).
a∈P

Intuitively, the idea is that, in case i(P ) > 0, we might be able to add i(P ) to
f on the arcs in P , and thus get a new flow with higher value (cf. Theorem ii.).
We say that P is f -saturated if i(P ) = 0 and f -unsaturated if i(P ) > 0. An
f -incrementing path is an f -unsaturated path from some x ∈ S to some y ∈ T
that only contains x and y as elements of S ∪ T .
62 CHAPTER 9. NETWORKS

Lemma 9.28. Let P be an f -incrementing path and define


f (a) + i(P )
 if a is a forward arc of P
f˜ : E → R+ ∪ {0}, ˜
f (a) = f (a) − i(P ) if a is a reverse arc of P

f (a) otherwise


Then f˜ is a flow and v(f˜) = v(f ) + i(P ). The flow f˜ is called the revised flow
based on P .

Proof. (1) The condition 0 ≤ f˜(a) ≤ c(a) follows from the definition of i.
(2) The condition a∈E, ψ(a)=(u,v) f˜(a) = a∈E, ψ(a)=(v,u) f˜(a) (for v ∈ I):
P P

If v is not in P , this is the same as for f .

If v is in P : Since v ∈ I and P goes from S to T , P “traverses” v:

We consider several cases, depending on the “direction” of a, b:

• a and b are forward arcs of P :

Then a adds i(P ) to the left hand side and b adds i(P ) to the right hand
side. The equality is preseved.

• a is a forward are of P and b a reverse arc:

Then a adds i(P ) to the left hand side and b adds −i(P ) to the left hand
side. The equality is preserved.

• The other two cases are similar.

(3) v(f˜) = v(f ) + i(P ):

Since P is an f -incrementing path, only the first arc of P is between S and
I, so
X X
v(f˜) = f˜(e) = f (e)+ i(P ) = v(f )+i(P ).
...
|{z}
x∈S,e∈E s.t. ψ(e)=(x,u)
added by the first arc of P

Theorem 9.29. A flow f on N is a maximum flow if and only if N contains

no f -incrementing path.
 63

Proof. “⇒” If f is a maximum flow then N contains no f -incrementing path

by Lemma 9.28 (we would have v(f˜) > v(f )).
“⇐” Assume now that N contains no f -incrementing path. Define

VS = S ∪ {all the vertices u such that there is an element x ∈ S

and an f -incrementing path in N from x to u},

and
VT = V \ VS .
Since N has no f -incrementing path, no element of T is in VS , so T ⊆ VT and
(VS , VT ) is a cut in N .
Fact: (i) Each arc from VS to VT is f -saturated.
(ii) Each arc from VT to VS is f -zero.
Proof of (i): Let a be an arc from u ∈ VS to v ∈ VT . Since u ∈ VS there is an
f -unsaturated path from some x ∈ S to u. If a is f -unsaturated, then this path
can be extended by a and would give an f -unsaturated path from x to v. So
we would have v ∈ VS , contradiction.
Proof of (ii): Similar, left as an exercise.
Using the Fact and Theorem 9.25, we obtain v(f ) = c(VS , VT ), and by
Corollary 9.27 f is a maximum flow (and (VS , VT ) is a minimum cut).
Remark 9.30. (VS , V \ VS ) with VS as in the proof is a minimal cut.
This proof gives us the following: If we start with a maximum flow f , we
get a minimal cut (VS , VT ) such that v(f ) = c(VS , VT ). Therefore
Theorem 9.31 (Max-flow, min-cut, Ford-Fulkerson 1956). In any network, the
value of a maximum flow is equal to the capacity of a minimum cut.
The Ford-Fulkerson algorithm.
It is easier to state using the following definition.
Definition 9.32. Let N be a network and let f be a flow in N . The residual
network of f is the network with:
• Same vertices, source and sink as N ;
• Every arc e ∈ E is given the new capacity

cf (e) = c(e) − f (e);

• For every arc in E from u to v we add an edge from v to u with capacity

f (e);
• Remove every arc e with cf (e) = 0 (a capacity only takes positive values).
Example 9.33.
64 CHAPTER 9. NETWORKS

The residual network is

The algorithm:

1. Start with a flow f of value 0 (the zero flow).

2. Repear the following:

(a) Build the residual network Nf of f .

(b) Find a directed path P from some s ∈ S to some t ∈ T in Nf
containing no other point from S or T . Stop if there is no such path
(f is then a maximal flow).
(c) Take d = mine∈P cf (e).
(d) For every arc e of P , let eN be the arc in the original network between
the same vertices. We then add to the flow f at e:
d if e and eN go in the same direction,
−d is e and eN go in opposite directions.
(So we end up modifying the values of f along the path P .)

3. The final flow you obtained (before the residual network in which you
could not find a path) is a maximum flow.

4. If at the end you wish to find a minimum cut, proceed as follows (cf.
Remark 9.30): Working in the final residual network (the one where you
could not find a path), put in the set VS all the vertices of the source,
and all the vertices that you can reach from a path starting in the source.
Take the set of all remaining vertices for VT (since you could not find a
path from the source to the sink, VT contains at least the sink).
Then (VS , VT ) is a minimum cut (again, see Remark 9.30).

We carry out the algorithm on the network above:

(1)
 65

(2)(a)

(2)(b) Take P = sat (I do not give a name to the edges in P since there are
no parallel edges, so no choice).
(2)(c) d = 3.
(2)(d)

(new f )

(2)(a)

(2)(b) Take for instance P = sbt.

(2)(c) d = 3.
(2)(d)

(new f )
66 CHAPTER 9. NETWORKS

(2)(a) Nf :

There is no path P , so we stop and this f is a maximal flow, with value 6.

It is confirmed by a quick look at the original network: There is indeed a
cut with capacity 6 (which must be a minimum cut, as we saw, and its capacity
is equal to the value of a maximum flow).
Remark 9.34. This algorithm will stop after a finite number of steps if the
capacities of the network are rational numbers:
It is easy to see if they are integers, since the algorithm gives an increase of
the value of the flow by at least 1 at each step. It must stop in a finite number of
steps since the value of maximum flow is bounded by the capacity of any cut. To
get the same result for capacitites with rational values, just multiply everything
by a large enough integer to go back to the integer case, then divide the flow at
the end by the same large integer.
Surprisingly enough, the algorithm may not terminate if you allow the ca-
pacities to take values in the real numbers.