88 4.

Planar Graphs
In each of e and e∗ , the
(ii) |e∗ ∩ G| = |e̊∗ ∩e̊| = |e ∩ G∗ | = 1 for all e ∈ E; unique point of e̊∗ ∩ e̊
should be an inner point
(iii) v ∈ f ∗ (v) for all v ∈ V . of a straight line segment.
The existence of such bijections implies that both G and G∗ are con-
nected (exercise). Conversely, every connected plane multigraph G has
a plane dual G∗ : if we pick from each face f of G a point v ∗ (f ) as a
vertex for G∗ , we can always link these vertices up by independent arcs
as required by condition (ii), and there is always a bijection V → F ∗
satisfying (iii) (exercise).
If G∗1 and G∗2 are two plane duals of G, then clearly G∗1  G∗2 ; in fact,
one can show that the natural bijection v1∗ (f ) → v2∗ (f ) is a topological
isomorphism between G∗1 and G∗2 . In this sense, we may speak of the
plane dual G∗ of G.
Finally, G is in turn a plane dual of G∗ . Indeed, this is witnessed
by the inverse maps of the bijections from the definition of G∗ : setting
v ∗ (f ∗ (v)) := v and f ∗ (v ∗ (f )) := f for f ∗ (v) ∈ F ∗ and v ∗ (f ) ∈ V ∗ , we
see that conditions (i) and (iii) for G∗ transform into (iii) and (i) for G,
while condition (ii) is symmetrical in G and G∗ . Thus, the term ‘dual’
is also formally justified.
Plane duality is fascinating not least because it establishes a con-
nection between two natural but very different kinds of edge sets in a
multigraph, between cycles and cuts:

Proposition 4.6.1. For any connected plane multigraph G, an edge set

E ⊆ E(G) is the edge set of a cycle in G if and only if E ∗ := { e∗ | e ∈ E }
is a minimal cut in G∗ .
Proof . By conditions (i) and (ii) in the definition of G∗ , two vertices
v ∗ (f1 ) and v ∗ (f2 ) of G∗ lie in the same component
 of G∗ − E ∗ if and
only if f1 and f2 lie in the same region of R  E: 
2
every v ∗ (f1 )–v ∗ (f2 )
∗ ∗
path in G − E is an arc between f1 and f2 in R  E, and conversely
2

every such arc P (with P ∩ V (G) = ∅) defines a walk in G∗− E ∗ between

v ∗ (f1 ) and v ∗ (f2 ).
Now if C ⊆ G is a cycle and E = E(C) then, by the Jordan curve
theorem and the above correspondence, G∗ − E ∗ has exactly two com-
ponents, so E ∗ is a minimal cut in G∗ .
Conversely, if E ⊆ E(G) is such that E ∗ is a cut in G∗ , then, by
Proposition 4.2.3 and the above correspondence, E contains the edges
of a cycle C ⊆ G. If E ∗ is minimal as a cut, then E cannot contain any
further edges (by the implication shown before), so E = E(C).

Proposition 4.6.1 suggests the following generalization of plane du-

ality to a notion of duality for abstract multigraphs. Let us call a multi-
graph G∗ an abstract dual of a multigraph G if E(G∗ ) = E(G) and the
minimal cuts in G∗ are precisely the edge sets of cycles in G. Note that
any abstract dual of a multigraph is connected.
116 5. Colouring

Indeed, while the first equality is immediate from the perfection of G − U ,

the second is easy: ‘
’ is obvious, while χ(G − U ) < ω would imply
χ(G)
ω, so G would be perfect contrary to our assumption.
Let us apply (1) to a singleton U = { u } and consider an ω-colouring
of G − u. Let K be the vertex set of any K ω in G. Clearly,

if u ∈/ K then K meets every colour class of G − u; (2)

if u ∈ K then K meets all but exactly one colour class of G − u. (3)

Let A0 = { u1 , . . . , uα } be an independent set in G of size α.

Let A1 , . . . , Aω be the colour classes of an ω-colouring of G − u1 , let
Aω+1 , . . . , A2ω be the colour classes of an ω-colouring of G − u2 , and
so on; altogether, this gives us αω + 1 independent sets A0 , A1 , . . . , Aαω
in G. For each i = 0, . . . , αω, there exists by (1) a K ω ⊆ G − Ai ; we
denote its vertex set by Ki .
Note that if K is the vertex set of any K ω in G, then

K ∩ Ai = ∅ for exactly one i ∈ { 0, . . . , αω + 1 }. (4) i ∈ { 0, . . . , αω }

Indeed, if K ∩ A0 = ∅ then K ∩ Ai = ∅ for all i = 0, by definition of Ai

and (2). Similarly if K ∩ A0 = ∅, then |K ∩ A0 | = 1, so K ∩ Ai = ∅ for
exactly one i = 0: apply (3) to the unique vertex u ∈ K ∩ A0 , and (2)
to all the other vertices u ∈ A0 .
Let J be the real (αω + 1) × (αω + 1) matrix with zero entries in
the main diagonal and all other entries 1. Let A be the real (αω + 1) × n
matrix whose rows are the incidence vectors of the subsets Ai ⊆ V : if
ai1 , . . . , ain denote the entries of the ith row of A, then aij = 1 if vj ∈ Ai ,
and aij = 0 otherwise. Similarly, let B denote the real n × (αω + 1)
matrix whose columns are the incidence vectors of the subsets Ki ⊆ V .
Now while |Ki ∩ Ai | = 0 for all i by the choice of Ki , we have Ki ∩ Aj = ∅
and hence |Ki ∩ Aj | = 1 whenever i = j, by (4). Thus,

AB = J.

Since J is non-singular, this implies that A has rank αω + 1. In particu-

lar, n  αω + 1, which contradicts (∗) for H := G. 

By definition, every induced subgraph of a perfect graph is again

perfect. The property of perfection can therefore be characterized by
forbidden induced subgraphs: there exists a set H of imperfect graphs
such that any graph is perfect if and only if it has no induced subgraph
isomorphic to an element of H. (For example, we may choose as H the
set of all imperfect graphs with vertices in N.)
Naturally, it would be desirable to keep H as small as possible. In
fact, one of the best known conjectures in graph theory says that H
140 6. Flows

6.6 Tutte’s flow conjectures

How can we determine the flow number of a graph? Indeed, does every
(bridgeless) graph have a flow number, a k-flow for some k? Can flow
numbers, like chromatic numbers, become arbitrarily large? Can we
characterize the graphs admitting a k-flow, for given k?
Of these four questions, we shall answer the second and third in this
section: we prove that every bridgeless graph has a 6-flow. In particular,
a graph has a flow number if and only if it has no bridge. The ques-
tion asking for a characterization of the graphs with a k-flow remains
interesting for k = 3, 4, 5. Partial answers are suggested by the following
three conjectures of Tutte, who initiated algebraic flow theory.
The oldest and best known of the Tutte conjectures is his 5-flow
conjecture:

Five-Flow Conjecture. (Tutte 1954)

Every bridgeless multigraph has a 5-flow.

Which graphs have a 4-flow? By Proposition 6.4.4, the 4-edge-

connected graphs are among them. The Petersen graph (Fig. 6.6.1), on
the other hand, is an example of a bridgeless graph without a 4-flow: In the 2nd edition, this
since it is cubic but not 3-edge-colourable (Ex. 19, Ch. 5), it cannot have is no longer a formal
a 4-flow by Proposition 6.4.5 (ii). exercise.

Fig. 6.6.1. The Petersen graph

Tutte’s 4-flow conjecture states that the Petersen graph must be

present in every graph without a 4-flow:

Four-Flow Conjecture. (Tutte 1966)

Every bridgeless multigraph not containing the Petersen graph as a mi-
nor has a 4-flow.

By Proposition 1.7.2, we may replace the word ‘minor’ in the 4-flow

conjecture by ‘topological minor’.
8.1 Topological minors 175

Thus in either case we have found an integer m
k/2 and a graph

G1  G such that
|G1 |  4m (1)

and δ(G1 )
2m, so

ε(G1 )
m
k/2
3 . (2)

As 2δ(G1 )
4m
|G1 |, our graph G1 is already quite a good

candidate for the desired minor H of G. In order to jack up its value
of 2δ by another 16 k (as required for H), we shall reapply the above
contraction process to G1 , and a little more rigorously than before: step vigorously
by step, we shall contract edges as long as this results in a loss of no
more than 76 m edges per vertex. In other words, we permit a loss of edges
slightly greater than maintaining ε
m seems to allow. (Recall that,
when we contracted G to G0 , we put this threshold at ε(G) = k.) If this
second contraction process terminates with a non-empty graph H0 , then Replace ε(H0 ) by δ(H0 );
ε(H0 ) will be at least 76 m, higher than for G1 ! The 16 m thus gained will ‘higher’ after replacing m
suffice to give the graph H1 , obtained from H0 just as G1 was obtained with k, not in absolute
from G0 , the desired high minimum degree. terms.
But how can we be sure that this second contraction process will
indeed end with a non-empty graph? Paradoxical though it may seem,
the reason is that even a permitted loss of up to 76 m edges (and one
vertex) per contraction step cannot destroy the m |G1 | or more edges
of G1 in the |G1 | steps possible: the graphs with fewer than m vertices
towards the end of the process would simply be too small to be able to
shed their allowance of 76 m edges—and, by (1), these small graphs would
account for about a quarter of the process!
Formally, we shall control the graphs H in the contraction process
not by specifying an upper bound on the number of edges to be discarded
at each step, but by fixing a lower bound for Hinterms of |H|. This
bound grows linearly from a value of just above m 2 for |H| = m to a
value of less than 4m2 for |H| = 4m. By (1) and (2), H = G1 will satisfy
this bound, but clearly it cannot be satisfied by any H with |H| = m;
so the contraction process must stop somewhere earlier with |H| > m.
To implement this approach, let

f (n) := 16 m(n − m − 5)
and   
H := H  G1 : H
m |H| + f (|H|) − m
2 .

By (1),
m
f (|G1 |)  f (4m) = 12 m2 − 56 m < 2 ,

so G1 ∈ H by (2).
12.5 The graph minor theorem 275

Theorem 12.5.2. (Graph Minor Theorem; Robertson & Seymour)

The finite graphs are well-quasi-ordered by the minor relation
.

So every HP is finite, i.e. every hereditary graph property can be

represented by finitely many forbidden minors:

Corollary 12.5.3. Every graph property that is closed under taking

minors can be expressed as Forb
(H) with finite H. 

As a special case of Corollary 12.5.3 we have, at least in principle,

a Kuratowski-type theorem for every surface:

Corollary 12.5.4. For every surface S there exists a finite set of graphs
H1 , . . . , Hn such that Forb
(H1 , . . . , Hn ) contains precisely the graphs
not embeddable in S. delete ‘not’

The minimal set of forbidden minors has been determined explicitly

for only one surface other than the sphere: for the projective plane it
is known to consist of 35 forbidden minors. It is not difficult to show
that the number of forbidden minors grows rapidly with the genus of the
surface (Exercise 34).
The complete proof of the graph minor theorem would fill a book
or two. For all its complexity in detail, however, its basic idea is easy to
grasp. We have to show that every infinite sequence

G 0 , G1 , G2 , . . .

of finite graphs contains a good pair: two graphs Gi
Gj with i < j.

We may assume that G0

Gi for all i  1, since G0 forms a good pair
with any graph Gi of which it is a minor. Thus all the graphs G1 , G2 , . . .
lie in Forb
(G0 ), and we may use the structure common to these graphs
in our search for a good pair.
We have already seen how this works when G0 is planar: then the
graphs in Forb
(G0 ) have bounded tree-width (Theorem 12.4.3) and are
therefore well-quasi-ordered by Theorem 12.3.7. In general, we need only
consider the cases of G0 = K n : since G0
K n for n := |G0 |, we may
assume that K n

Gi for all i  1.
The proof now follows the same lines as above: again the graphs in
Forb
(K n ) can be characterized by their tree-decompositions, and again
their tree structure helps, as in Kruskal’s theorem, with the proof that
they are well-quasi-ordered. The parts in these tree-decompositions are
no longer restricted in terms of order now, but they are constrained in
more subtle structural terms. Roughly speaking, for every n there exists
a finite set S of closed surfaces such that every graph without a K n minor
has a simplicial tree-decomposition into parts each ‘nearly’ embedding in
 Symbol Index

Unfortunately, the entire

symbol index printed
The entries in this index are divided into two groups. Entries involving in the second edition is
old. This page and the
only mathematical symbols (i.e. no letters except variables) are listed on
next show the corrected
the first page, grouped loosely by logical function. The entry ‘[ ]’, for version.
example, refers to the definition of induced subgraphs H [ U ] on page 4
as well as to the definition of face boundaries G [ f ] on page 72.
Entries involving fixed letters as constituent parts are listed on the
second page, in typographical groups ordered alphabetically by those
letters. Letters standing as variables are ignored in the ordering.

∅ 2 h , i 20
= 3 / 16, 17, 25
' 3 C⊥, F ⊥, . . . 21
⊆ 3
0, 1, 2, . . . 1
6 253
(n)k , . . . 234
4 17
E(v), E 0 (w), . . . 2
+ 4, 20, 128 E(X, Y ), E 0 (U, W ), . . . 2
− 4, 70, 128 (e, x, y), . . . 124
→ → →
∈ 2 E, F , C , . . . 124, 136, 138
r 70 ←
← ←
e, E , F , . . . 124
∪ 3
f (X, Y ), g(U, W ), . . . 124
∩ 3
∗ 4 G∗ , F ∗ , → e ∗, . . . 87, 136
G2 , H 3 , . . . 218
bc 1 G, X, G, . . . 4, 124, 263
de 1 (S, S), . . . 126
| | 2, 126 xy, x1 . . . xk , . . . 2, 7
k k 2, 153 xP, P x, xP y, xP yQz, . . . 7
[ ] 3, 72 P̊ , x̊Q, . . . 7, 68
[ ]k , [ ]<ω 1, 252 xT y, . . . 13
312 Symbol Index The page numbers
on this page are
F2 20 col(G) 98 shown as they should
N 1 d(G) 5 be, not as they are in
Zn 1 d(v) 5 the printed edition.
d+ (v) 108
CG 34 d(x, y) 8
C(G) 21
d(X, Y ) 153
C ∗ (G) 22
diam(G) 8
E(G) 20
ex(n, H) 149
G(n, p) 230
f ∗ (v) 87
PH 243
g(G) 7
Pi,j 238
V(G) 20 i 1
init(e) 25
log, ln 1
Ck 7
pw(G) 279
E(G) 2
q(G) 34
E(X) 233
rad(G) 9
F (G) 70
tr−1 (n) 149
Forb4 (X ) 263
ter(e) 25
G(H1 , H2 ) 198
tw(G) 257
Kn 3
ve , vxy , vU 16, 17
Kn1 ,...,nr 15
Ksr 15 v ∗ (f ) 87
L(G) 4
MX 16 ∆(G) 5
N (v), N (U ) 4, 5
N + (v) 108 α(G) 110
P 231 δ(G) 5
Pk 6 ε(G) 5
PG 118 κ(G) 10
R(H) 193 κG (H) 57
R(H1 , H2 ) 193 λ(G) 11
R(k, c, r) 193 λG (H) 57
R(r) 191 µ 242
Rs 161 π : S 2 r { (0, 0, 1) } → R2 69
Sn 69 σk : Z → Zk 131
TX 17 σ2 242
T r−1 (n) 149 ϕ(G) 131
V (G) 2 χ(G) 95
χ0 (G) 96
ch(G) 105 χ00 (G) 119
ch0 (G) 105 ω(G) 110