FJKL

Graph Theory Exercises
https://www.ime.usp.br/~pf/graph-exercises/
Paulo Feofiloff
Department of Computer Science
Institute of Mathematics and Statistics
University of São Paulo
translated into English by

Murilo Santos de Lima
School of Computer Science
Reykjavík University
March 14, 2019

original last revised by the author in February 2013
FEOFILOFF 2
Contents
1 Basic concepts 7
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Neighborhoods and vertex degrees . . . . . . . . . . . . . . . . . . . . . 17
1.4 Paths and circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5 Union and intersection of graphs . . . . . . . . . . . . . . . . . . . . . . 22
1.6 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.7 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8 Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.9 Paths and circuits in graphs . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.10 Connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.11 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.12 Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.13 Edge-biconnected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.14 Articulations and biconnected graphs . . . . . . . . . . . . . . . . . . . 43
1.15 Trees and forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.16 Graph minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.17 Plane maps and their faces . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1.18 Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2 Isomorphism 59
3 Graph design with given degrees 65
4 Bicolorable graphs 67
5 Stable sets 71
6 Cliques 77
7 Vertex covers 81
3
FEOFILOFF 4
8 Vertex coloring 83
9 Matchings 95
10 Matchings in bipartite graphs 101
11 Matchings in arbitrary graphs 107
12 Edge coloring 111
13 Connectors and acyclic sets 117
14 Minimum paths and circuits 121
15 Flows 125
16 Internally disjoint flow 129
17 Hamiltonian circuits and paths 133
18 Circuit covers 139
19 Characterization of planarity 145
A Hints for some of the exercises 149
B The Greek alphabet 155
Bibliography 157
Index 159
Preface
Graph theory studies combinatorial objects called graphs. These objects are
a good model for many problems in mathematics, computer science, and
engineering. Graph theory is not really a theory, but a collection of problems.
Many of those problems have important practical applications and present
intriguing intellectual challenges.
The present text is a collection of exercises in graph theory. Most exercises
have been extracted from the books by Bondy and Murty [BM08, BM76],
Wilson [Wil79], Diestel [Die00, Die05], Bollobás [Bol98], Lovász [Lov93], Mel-
nikov et alii [MST+ 98], Lucchesi [Luc79] and Lovász and Plummer [LP86].
Some are byproducts of research projects. Others were born from conversa-
tions with teachers (especially my supervisor Dan Younger), colleagues and
students.
The text has many hyperlinks, which take you from one part of the text
to another and point to supplementary material. To take advantage of those
links, you should read the text on your computer screen (rather than printed
on paper).
The website www.ime.usp.br/~pf/graph-exercises/ has an up-to-date version
of the text.
Organization. Chapter 1 deals with basic concepts. Each of the other

chapters deals with some classical problem. Many of the problems have a
computational character: they ask for an efficient algorithm that will extract
some information from a given graph. Some problems are easy, others are
hard; some have already been solved, while others are still open.1
In what order should the chapters be read? After studying the first sec-
tion of chapter 1, I guess the reader should move immediately to chapters 2
and following, returning to chapter 1 only when that becomes necessary.
There is a good index to help find the definitions of technical terms and
concepts.
1
For many of these problems, a fast algorithm is not (yet?) known; the only known al-
gorithms are not much better than patiently checking a very long list of would-be solutions.
In technical terms, such a problem is NP-complete or NP-hard. See the books by Garey–
Johnson [GJ79], Harel [Har92], and Sipser [Sip97].
5
FEOFILOFF 6
Classification of the exercises. Most exercises have a generic prefix E. Some

have more specific prefixes:
◦E ... particularly easy drill

!E ... hard
!! E ... very hard
?E ... important
?! E ... important and hard
?◦ E ... important but easy
.E ... useful as a technical tool
E♥ ... particularly good
D ... challenge, open problem
But this classification is not very reliable and was not made in a very system-
atic way.
Acknowledgments. I am thankful to Rogério Brito for solving various ty-

pographical issues.
IME–USP, São Paulo, January 2013

P. F.
I am thankful to Murilo Santos de Lima for the excellent translation of

the text into English. (All the errors in English usage are due to my meddling
with the text after Murilo finished his work.)
IME–USP, São Paulo, March 2019

P. F.
Chapter 1
Basic concepts
This chapter formalizes the notion of a graph and introduces some basic con-
cepts, such as vertex degree, cut, subgraph, connection, component, bridge,
articulation, union, intersection, complement, minor, etc. The chapter also
introduces some important types of graphs, such as
paths,
circuits,
trees,
bipartite graphs,
edge-biconnected graphs,
biconnected graphs,
planar graphs,
interval graphs,
random graphs, etc.
Various examples of graphs that are found in nature are also presented. That
is the case of
grids,
cubes,
Petersen’s graph,
graphs for various chess pieces,
graphs of chemical compounds, etc.
These examples will be useful in the other chapters of the text.
After studying the first section of this chapter the reader may move to
the following chapters (beginning with chapter 2, which deals with isomor-
phism). She/he can return to chapter 1 and study the other sections when
this becomes necessary. The index may be useful in this process.
7
FEOFILOFF Graphs 8
1.1 Graphs
A graph1 is a structure made up of two types of objects: vertices and edges.
Each edge is an unordered pair of vertices, i.e., a set with exactly two ver-
vw tices.2 An edge like {v, w} will simply be denoted by vw or wv; we will say
that the edge is incident to v and to w; we will also say that v and w are
the endpoints of the edge; we will say, moreover, that vertices v and w are
neighbors, or adjacent.
E XAMPLE : the vertices of the graph are t, u, v, w, x, y, z and

the edges are vw, uv, xw, xu, xy and yz. The picture below is a
graphical representation of this graph.
u
t
x
v y z
w
According to our definition, a graph cannot have two different edges

with the same pair of endpoints (i.e., cannot have “parallel” edges). More-
over, the two endpoints of any edge are distinct (i.e., there are no “loops”).
Some books like to emphasize this aspect of the definition by saying that the
simple graph is “simple”; we will not use this adjective.
(V, E) A graph with vertex set V and edge set E is denoted by (V, E). It is often
convenient to name the graph as a whole. If the name of the graph is G, its
VG , EG vertex set is denoted by VG and its edge set by EG . The number of vertices
n(G), m(G) of G is denoted by n(G) and the number of edges by m(G); hence,
n(G) := |VG | and m(G) := |EG | .
V (2) The complement of a graph (V, E) is the graph (V, V (2) r E), where V (2)
is the set of all unordered pairs3 of elements of V . The complement of G is
G usually denoted by G.
(2)
Kn A graph G is complete if EG = VG . The expression “G is a Kn ” is an
abbreviation for “G is a complete graph on n vertices.” A graph G is empty
Kn if EG = ∅. The expression “G is a Kn ” is an abbreviation for “G is an empty
graph on n vertices.”
1
The term was used for the first time (in the sense that concerns us here) by James Joseph
Sylvester ( − ). (See Wikipedia article.)
2
We will assume that the vertex and edge sets of a graph are finite and mutually disjoint.
We will also assume that the vertex set is not empty.
3
Diestel [Die05] writes “[V ]2 .” Other authors write “ V2 .”

FEOFILOFF Graphs 9
Exercises
E 1.1 List all graphs that have {a, b, c} as their vertex set.4 Organize the list
so that each graph appears besides its complement.
E 1.2 Draw a figure of a K5 and another of a K5 . How many edges does a Kn

have? What about a Kn ?
E 1.3 The adjacency matrix of a graph G is the matrix A defined as follows: adjacency
for any two vertices u and v, matrix
1 if uv ∈ EG ,
A[u, v] =
0 otherwise.
Clearly, the matrix is indexed by VG × VG . (The adjacency matrix is a kind
of “figure” of the graph. It has some advantages over the points-and-lines
figure we used above.)
Write the adjacency matrix of the graph defined in the example that ap-
pears on page 8. Write the adjacency matrix of a K4 . What is the relationship
between the adjacency matrix of a graph and the adjacency matrix of its
complement?
E 1.4 The incidence matrix of a graph G is the matrix M defined as follows: incidence
for every vertex u and every edge e, matrix
1 if u is one of the endpoints of e ,

M [u, e] =
0 otherwise.
Clearly, the matrix is indexed by VG × EG . (The incidence matrix is a kind
of “figure” of the graph. It has some advantages over the points-and-lines
figure we used above.)
Write the incidence matrix of the graph defined in the example that
appears on page 8. Write the incidence matrix of a K4 . What is the value
of the sum of all elements of the incidence matrix of a graph? What is
the relationship between the incidence matrix of a graph and the incidence
matrix of its complement?
E 1.5 The hydrocarbons known as alkanes have chemical formula Cp H2p+2 , alkanes
where C and H represent atoms of carbon and hydrogen, respectively.
Alkane molecules can be represented by graphs such as those in figure 1.1.
Draw a figure of a methane C1 H4 molecule. How many “different” C3 H8
molecules are there?
4
In a set, the order in which the elements are presented is irrelevant. Thus, {a, b, c} =
{b, c, a} = {c, b, a}.
FEOFILOFF Graphs 10
Figure 1.1: Ethane (C2 H6 ), butane (C4 H10 ) and isobutane (C4 H10 ). The
vertices with only one incident edge represent hydrogen (H) atoms; the
others represent carbon (C) atoms. (See exercise 1.5.)
E 1.6 Let V be the Cartesian product {1, 2, . . . , p} × {1, 2, . . . , q}, i.e., the set of
all ordered pairs5 (i, j) with i in {1, . . . , p} and j in {1, . . . , q}. Let us say that
two elements (i, j) and (i0 , j 0 ) of V are adjacent if
i = i0 and |j − j 0 | = 1 or j = j 0 and |i − i0 | = 1 .
This adjacency relation defines a graph over the set V of vertices. The graph
grid is known as the p-by-q grid.
How many edges does the p-by-q grid have? Write the adjacency and
incidence matrices of a 4-by-5 grid.
Figure 1.2: A 3-by-4 grid (see exercise 1.6).
E 1.7 Given integer numbers p and q, let V be the set {1, 2, 3, . . . , pq −2, pq −1,
pq}. Let us say that two elements k and k 0 of V , with k < k 0 , are adjacent if
k 0 = k + q or6
k mod q 6= 0 and k 0 = k + 1.
This adjacency relation defines a graph with vertex set V .
Draw a figure of the graph with parameters p = 3 and q = 4. Draw a
figure of the graph with parameters p = 4 and q = 3. What is the relationship
between these graphs and the grid defined in exercise 1.6?
queen E 1.8 The graph of the queen’s moves, or simply the queen graph, is defined
like this: the vertices of the graph are the squares of a chess board with t rows
and t columns (the usual board has t = 8) and two vertices are adjacent if a
queen in the game of chess can jump from one of them to the other in a single
5
An ordered pair is a sequence of length 2. In a sequence, the order of the elements is
essential. Thus, (1, 2) 6= (2, 1) and (1, 2, 1) 6= (1, 1, 2).
6
The expression “k mod q” denotes the remainder of the division of k by q, i.e., k/q −
bk/qc.
FEOFILOFF Graphs 11
move. To make explicit the number of rows and columns, we may say that
this is t-by-t queen graph. (See figure 1.3.)
Draw a figure of the 4-by-4 queen graph. Write the adjacency and inci-
dence matrices of the 4-by-4 queen graph. How many edges does the 8-by-8
queen graph have? How many edges does the t-by-t queen graph have?
E 1.9 The t-by-t knight graph is defined like this: the vertices of the graph knight
are the squares of a chess board with t rows and t columns; two vertices are
adjacent if a knight in the game of chess can jump from one of them to the
other in a single move. (See figure 1.3.)
Draw a figure of the 3-by-3 knight. Write the adjacency and incidence
matrices of the 3-by-3 knight graph. How many edges does the 8-by-8 knight
graph have? How many edges does the t-by-t knight graph have?
Figure 1.3: 8-by-8 chess boards. The figure on the left indicates all the
neighbors of vertex • in the queen graph (see exercise 1.8). The one on
the right indicates all the neighbors of vertex • in the knight graph (see
exercise 1.9).
E 1.10 The t-by-t bishop graph is defined as follows: the vertices of the graph bishop
adjacent if a bishop in the game of chess can jump from one of them to the
other in a single move.
Draw a figure of the 4-by-4 bishop graph. Write the adjacency and
incidence matrices of the 4-by-4 bishop graph. How many edges does the
8-by-8 bishop graph have? How many edges does the t-by-t bishop graph
have?
E 1.11 The t-by-t rook graph is defined as follows: the vertices of the graph rook
adjacent if a rook in the game of chess can jump from one of them to the other
in a single move.
Draw a figure of the 4-by-4 rook graph. Write the adjacency and inci-
dence matrices of the 4-by-4 rook graph. How many edges does the 8-by-8
rook graph have? How many edges does the t-by-t rook graph have?
FEOFILOFF Graphs 12
E 1.12 The t-by-t king graph is defined like this: the vertices of the graph king
adjacent if a king in the game of chess can jump from one of them to the other
in a single move.
Draw a figure of the 4-by-4 king graph. Write the adjacency and inci-
dence matrices of the 4-by-4 king graph. How many edges does the 8-by-8
king graph have? How many edges does the t-by-t king graph have?
words E 1.13 The words graph is defined like this: each vertex is a word in the
English language and two words are adjacent if they differ in exactly one po-
sition. (This graph is adapted from ladders in Stanford GraphBase [Knu93].)
For example, cords and corps are adjacent, while corps and crops are not.
Draw a figure of the part of the graph defined by the following words:
words cords corps coops crops drops drips grips gripe
grape graph
Write the adjacency and incidence matrices of this graph.
cube E 1.14 For any positive integer k, a k-dimensional cube (or k-cube) is the
graph defined as follows: the vertices of the graph are all the sequences7
b1 b2 · · · bk of bits8 ; two vertices are adjacent if and only if they differ in exactly
one position. For example, the vertices of the 3-dimensional cube are 000,
001, 010, 011, 100, 101, 110, 111; vertex 000 is adjacent to vertices 001, 010, 100
Qk and to no other; and so on. The k-dimensional cube will be denoted by Qk .
Draw figures of the cubes Q1 , Q2 and Q3 . Write the adjacency and
incidence matrices of Q3 . How many vertices does Qk have? How many
edges?
E 1.15 Let X be the set {1, 2, 3, 4, 5} and V the set X (2) (therefore, V is the set
of all subsets of X that have exactly 2 elements). Let us say that two elements
v and w of V are adjacent if v ∩ w = ∅. This adjacency relation on V defines
Petersen the Petersen graph.9 Draw a figure of the graph. Write the adjacency and
incidence matrices of the graph. How many vertices and how many edges
does the graph have?
E 1.16 Let V be the set of all subsets of {1, 2, . . . , n} that have exactly k ele-
ments, with k ≤ n/2. Let us say that two elements v and w of V are adjacent
Kneser if v ∩ w = ∅. This adjacency relation on V defines the Kneser graph K(n, k).10
7
The expression “b1 b2 · · · bk ” is an abbreviation for “(b1 , b2 , . . . , bk ).”
8
Therefore, each bi belongs to the set {0, 1}.
9
Reference to Julius Petersen (Denmark,  − ). (See article on Wikipedia.)
10
Lásló Lovász used this graph in 1978 to prove a conjecture proposed by M. Kneser
in 1955.
FEOFILOFF Graphs 13
In particular, K(5, 2) is the Petersen graph. Draw figures for K(n, 1), K(n, n),
K(n, n−1), K(4, 2), K(5, 3), K(6, 2) and K(6, 3).
E 1.17 The graph of Europe is defined like this: each vertex is one of the countries
countries of Europe; two countries are adjacent if they have a common bor-
der. Draw a figure of the graph. How many vertices does the graph have?
How many edges?
E 1.18 Consider the large cities and the major roads in a country. Let us say
that a city is large if it has at least 300 thousand inhabitants. Let us say the a
road is a major road if it is a divided highway. Let us say that two large cities
are adjacent if a major road or a concatenation of major roads connects those
two cities directly (i.e., without passing through a third large city). Draw a cities
figure of the graph of the large cities defined by the adjacency relation we
have just described.
E 1.19 Let V be a set of points in the plane. Let us say that two of these
points are adjacent if the distance between them is smaller than 2. This
adjacency relation defines the graph of poins in the plane (on the set V ). points in
Draw a figure of the graph defined by the following points. the plane
(0, 2) (1, 2) (2, 2)

(0, 1) (1, 1) (2, 1)
(0, 0) (1, 0) (2, 0)
Write the adjacency and incidence matrices of the graph.
E 1.20 Given a set V , let E be the set defined in the following manner: for
each unordered pair of elements of V , flip a coin; if the result is heads, add
the pair to E. The graph (V, E) so defined is random. random
Take your favorite coin and draw a figure of a random graph with
vertices 1, . . . , 6. Now repeat the exercise with a biased coin which produces
heads with probability 1/3 and tails with probability 2/3.
E 1.21 Let S be a square matrix of integer numbers. Suppose that the rows of
S are indexed by a set V and that the columns are indexed by the same set V .
The graph of matrix S is defined as follows: the set of vertices of the graph is
V and two vertices i and j are adjacent if S[i, j] 6= 0.
Is the graph of S well-defined? Which conditions must be imposed on
the matrix to make the graph well-defined?
E 1.22 Consider k intervals of finite length, I1 , I2 , . . . , Ik , on the real line. Let

us say that two intervals Ii and Ij are adjacent if Ii ∩ Ij 6= ∅. This adjacency
relation defines a graph with vertex set {I1 , I2 , . . . , Ik }. This is an interval interval
FEOFILOFF Graphs 14
graph.
Draw a figure of the graph defined by the intervals [0, 2], [1, 4], [3, 6], [5, 6]
and [1, 6]. Write the adjacency and incidence matrices of the graph.
E 1.23 Let be a partial order relation on a finite set V . Therefore, the

relation is transitive (if x y and y z, then x z), antisymmetric (if
x y and y x, then x = y) and reflexive (x x for every x). Let us say that
two distinct elements x and y of V are adjacent if they are comparable, i.e., if
compa- x y or y x. This adjacency relation defines the comparability graph of
rability the relation .
Draw a figure of the comparability graph of the usual inclusion rela-
tion ⊆ over the subsets of {1, 2, 3}.
E 1.24 Two edges of a graph G are adjacent if they have a common endpoint.
line This adjacency relation defines the line graph of G. More formally, the line
graph of a graph G is the graph (EG , A) in which A is the set of all pairs
L(G) of adjacent edges of G. The line graph of G will be denoted by L(G). (See
figure 1.4.)
Draw a figure of L(K3 ). Draw a figure of L(K4 ). Write the adjacency
and incidence matrices of L(K4 ). How many vertices and edges does L(Kn )
have? Draw a figure of the graph L(P ), where P is the Petersen graph (see
exercise 1.15).
u
t vu ux
x xy
v y z yz
w vw wx
Figure 1.4: A graph (left) and its line graph (right).

FEOFILOFF Bipartite graphs 15
1.2 Bipartite graphs

A graph G is bipartite if there is a bipartition11 {U, W } of VG such that every
edge of G has one endpoint in U and the other in W . To make the partition
explicit, we can say that the graph is {U, W }-bipartite.
If G is a {U, W }-bipartite graph, we can say, informally, that the elements
of U are the white vertices and that those of W are the black vertices of the
graph.
A {U, W }-bipartite graph is complete if every white vertex is adjacent to
every black vertex. A Kp,q is a complete bipartite graph with p white and q Kp,q
black vertices.
A star is a K1,q . If q ≥ 2, the center of the star is the only vertex which is star
incident to two or more edges. (If q < 2, the star has no center.)
Figure 1.5: A complete bipartite graph.
Exercises
◦ E 1.25 A small factory has five machines — 1, 2, 3, 4 and 5 — and six
workers — A, B, C, D, E and F . The table specifies which machines each
worker is allowed to operate:
A 2, 3 B 1, 2, 3, 4, 5
C 3 D
E 2, 4, 5 F 2, 5
Draw a figure of the bipartite graph which represents the relationship be-
tween workers and machines.
◦ E 1.26 How many edges can a {U, W }-bipartite graph have?

11
A bipartition of a set V if a pair {U, W } of non-empty sets such that U ∪ W = V
and U ∩ W = ∅. More generally, a partition of a set V is a collection {X1 , X2 , . . . , Xk } of
pairwise disjoint (i.e., Xi ∩ Xj = ∅ for every i 6= j) non-empty sets whose union is V (i.e.,
X1 ∪ X2 ∪ · · · ∪ Xk = V ). It makes no sense to say “X1 is one of the partitions of V ”; this
is equivalent to mistake herd for cow or choir for singer. You should say “X1 is one of the
elements of the partition” or “X1 is one of the parts of the partition.”
FEOFILOFF Bipartite graphs 16
◦ E 1.27 How many edges does a Kp,q have? How many edges does a Kp,q
have?
E 1.28 Draw a figure of a K3,4 . Write the adjacency and incidence matrices of
a K3,4 . Draw a figure of a star with 6 vertices.
E 1.29 Is it true that the t-by-t knight graph is bipartite?
E 1.30 What is the shape of the adjacency matrix of a bipartite graph?
E 1.31 The bipartition matrix of a {U, W }-bipartite graph is defined like this:
each row of the matrix is an element of U , each column of the matrix is an
element of W , and at the intersection of line u and column w we have a 1 if
uw is an edge, and a 0 otherwise.
Write the bipartition matrix of the graph from exercise 1.25. Adopt the
obvious bipartition: U = {A, . . . , F } and W = {1, . . . , 5}.
FEOFILOFF Neighborhoods and vertex degrees 17
1.3 Neighborhoods and vertex degrees

The neighborhood of a vertex v in a graph G is the set of all neighbors of v.
This set will be denoted by
NG (v)
or simply by N(v).12 The degree of a vertex v in a graph G is the number of N(v)
edges that are incident to v. The degree of v will be denoted by
dG (v)
or simply d(v). Clearly, d(v) = |N(v)| for every vertex v. A vertex v is isolated d(v)
if d(v) = 0.
The minimum degree and the maximum degree of the vertices of a
graph13 G are the numbers δ(G)
∆(G)
δ(G) := min dG (v) and ∆(G) := max dG (v)
v∈VG v∈VG
1
P
respectively. The average of the degrees of G, i.e., |V | v∈V d(v), will be
denoted by µ(G).14 As we will see in exercise 1.43, µ(G)
µ(G) = 2m(G)/n(G) .
A graph is regular if all its vertices have the same degree, i.e., if δ = ∆. A
graph is r-regular if d(v) = r for every vertex v. A cubic graph is the same as
a 3-regular graph.
Exercises
◦ E 1.32 What are the degrees of the vertices of a star (see section 1.2)?
◦ E 1.33 If G is a Kn , what are the values of δ(G) and ∆(G)? What are the
values of the parameters δ and ∆ for a Kp,q (see section 1.2)?
◦ E 1.34 For r = 1, 2, 3, draw a figure of an r-regular graph with 12 vertices.
E 1.35 What are the degrees of the vertices of an alcane molecule (see exer-
cise 1.5)?
E 1.36 Calculate the values of the parameters δ, ∆ and µ for the k-cube (see
exercise 1.14) and for the Petersen graph (see exercise 1.15 or figure 1.6).
Figure 1.6: Petersen graph. See exercises 1.15 and 1.36.
E 1.37 Calculate the values of the parameters δ and ∆ for the graph of Euro-
pean countries (see exercise 1.17).
E 1.38 Calculate the values of the parameters δ, ∆ and µ for the queen graph
(see exercise 1.8) and for the knight graph (see exercise 1.9).
E 1.39 Let A be the adjacency matrix (see exercise 1.3) and M be the incidence
matrix (see exercise 1.4) of a graph G. What is the sum of the elements in row
v of A? What is the sum of the elements in row v of M ?
. E 1.40 Let G be a {U, W }-bipartite graph. Suppose G is r-regular, with

r > 0. Show that |U | = |W |.
E 1.41 Is it true that every graph with at least two vertices has two vertices
with the same number of neighbors? In other words, if a graph has more
than one vertex, is it true that it has two distinct vertices v and w such that
|N(v)| = |N(w)|? (An informal way to say this: is it true that every town
with at least two inhabitants has two people with exactly the same number
of friends in the town?)
? E 1.42 Show15 that, in every graph, the sum of the degrees of the vertices
is equal to twice the number of edges. I.e., every graph (V, E) satisfies the
identity P
v∈V d(v) = 2|E| . (1.1)
◦ E 1.43 Show that µ(G) = 2m(G)/n(G) for every graph G.
12
Some authors write “Adj (v)” instead of “N(v).” Others write “Γ(v).”
13
The expression “minimum degree of a graph” is not very grammatical, since “degree
of a graph” makes no sense.
14
Unlike δ and ∆, the notation µ is not universal. Diestel [Die05] and Bondy and
Murty [BM08], for example, write d instead of my µ.
15
Show = prove.
◦ E 1.44 Show that every graph G has a vertex v such that d(v) ≤
2m(G)/n(G), and a vertex w such that d(w) ≥ 2m(G)/n(G). Is it true
that every graph G has a vertex x such that d(x) < 2m(G)/n(G)?
E 1.45 Show that every graph has δ ≤ 2m/n ≤ ∆.
E 1.46 Show that every graph with n vertices has at most n(n − 1)/2 edges.
. E 1.47 Show that, in any graph, the number of vertices with odd degree is
necessarily even.
E 1.48 How many edges does the 8-by-8 queen graph have (see exercise 1.8)?
How many edges does the t-by-t queen graph have?
E 1.49 How many edges does the 4-by-4 knight graph have (see exercise 1.9)?
How many edges does the t-by-t knight graph have?
E 1.50 How many edges does a r-regular graph with n vertices have?
E 1.51 How many edges does the k-dimensional cube have?
E 1.52 How many edges does the line graph (see exercise 1.24) of a graph G
have?
E 1.53 Let G be the complement of graph G. Calculate δ(G) and ∆(G) as a

function of δ(G) and ∆(G).
E 1.54 Let G be a graph such that m(G) > n(G). Show that ∆(G) ≥ 3.
E 1.55 Suppose that a graph G has less edges than vertices, i.e., that m(G) <
n(G). Show that G has (at least) one vertex of degree 0 or (at least) two
vertices of degree 1.
! E 1.56 Pick two natural numbers n and k and consider the following game
for two players, A and B. Each iteration of the game begins with a graph G
on n vertices. At the beginning of the first iteration, we have that EG is empty.
In every odd iteration (first, third, etc.), player A picks two non-adjacent
vertices u and v and adds uv to the edge set of the graph. In every even
iteration (second, fourth, etc.), player B does an analogous move: picks two
non-adjacent vertices u and v and adds uv to the edge set of the graph. The
first player to yield a graph G such that δ(G) ≥ k loses the game. Problem:
determine a winning strategy for A and a winning strategy for B.
FEOFILOFF Paths and circuits 20
1.4 Paths and circuits

This section introduces two simple but very important types of graphs: paths
and circuits.16
A graph G is a path if VG admits a permutation17 (v1 , v2 , . . . , vn ) such that
EG = {vi vi+1 : 1 ≤ i < n} .
The vertices v1 and vn are the endpoints of the path; the other vertices are
internal.18 We will say that this path connects v1 to vn .
v1 v2 · · · vn The path we have just described can be denoted simply by v1 v2 · · · vn .
For example, if we say “the path xywz”, we are referring to the graph whose
vertices are x, y, w, z and whose edges are xy, yw and wz.
A graph G is a circuit (= polygon)19 if VG has 3 or more elements and
admits a permutation (v1 , v2 , . . . , vn ) such that
EG = {vi vi+1 : 1 ≤ i < n} ∪ {vn v1 } .
This circuit can be denoted simply by v1 v2 · · · vn v1 . Thus, if we say “the
v1 v2 · · · vn v1 circuit xywzx”, we are referring to the graph whose vertices are x, y, w, z
and whose edges are xy, yw, wz and zx.
Figure 1.7: A path and a circuit.
The length of a path20 or circuit G is the number m(G). Of course, a path

of length m has m + 1 vertices and a circuit of length m has m vertices.
A triangle, square, pentagon and hexagon is the same as a circuit of
length 3, 4, 5 and 6 respectively.
Exercises
◦ E 1.57 Draw a figure of a path of length 0, of a path of length 1 and of a path
of length 2. Draw a figure of a circuit of length 3 and of a circuit of length 4.
Why does the definition of a circuit require “n ≥ 3”?
16
It should be stressed that, for us, paths and circuits are graphs. In some books, paths
and circuits are treated as sequences of vertices and edges rather than as graphs.
17
A permutation of a set X is a sequence in which each element of X appears once and
only once.
18
Some authors [Per09] say that a path is only a path if it has 2 or more vertices. For us,
however, the graph ({v}, ∅) is a path. This detail is not as irrelevant as it may seem.
19
Some authors say “cycle” instead of “circuit.”
20
The expression “size of a path” is ambiguous: one cannot tell if we are talking about
the number of vertices or the number of edges in the path.
FEOFILOFF Paths and circuits 21
◦ E 1.58 Let V be the set {a, b, c, d, e} and E be the set {de, bc, ca, be}.
Verify that the graph (V, E) is a path. Now suppose that F is the set
{bc, bd, ea, ed, ac} and verify that the graph (V, F ) is a circuit.
◦ E 1.59 Draw a figure of the path 1 2 4 3 5. Draw a figure of the path 1 3 2 4 3 5.

Draw a figure of the circuit 1 2 4 3 5 1.
◦ E 1.60 Verify that the path u v w x y z can also be denoted by z y x w v u.

Verify that those two expressions represent the same path.
◦ E 1.61 Consider the circuit u v w x y z u. Show that z y x w v u z is also a cir-

cuit. Show that any cyclic permutation — such as w x y z u v w, for example —
is also a circuit. Show that all those expressions represent the same circuit.
◦ E 1.62 Give the adjacency and incidence matrices of a path of length 4. Give
the adjacency and incidence matrices of a circuit of length 5.
◦ E 1.63 Is it true that the 3-by-3 knight graph is a circuit?
◦ E 1.64 Verify that the 1-by-n grid is a path of length n − 1. Which grids are
circuits?
◦ E 1.65 Suppose that P is a path of length n − 1 and O is a circuit of length n.

What is the value of δ(P ), ∆(P ), δ(O) and ∆(O)?
◦ E 1.66 Draw a figure of the complement of a path of length 3. Draw a figure

of the complement of a path of length 4. Draw a figure of the complement of
a circuit of length 5. Draw a figure of the complement of a circuit of length 6.
E 1.67 How many different paths with vertex set {1, 2, 3} are there? How
many different circuits with vertex set {1, 2, 3} are there? How many different
circuits with vertex set {1, 2, 3, 4} are there?
E 1.68 Is it true that every 2-regular graph is a circuit?
E 1.69 Let G be a graph with n(G) ≥ 3, ∆(G) = 2 and δ(G) = 1. If G has

exactly two vertices of degree 1, is it true that G is a path?
FEOFILOFF Union and intersection of graphs 22
1.5 Union and intersection of graphs

The union of two graphs G and H is the graph (VG ∪ VH , EG ∪ EH ). It is
G∪H natural to denote this graph by G ∪ H.
The intersection of two graphs G and H is the graph (VG ∩VH , EG ∩EH ). It
G ∩ H is natural to denote this graph by G∩H. We will only consider the intersection
G ∩ H if VG ∩ VH is not empty.
Two graphs G and H are disjoint if the sets VG and VH are disjoint, i.e., if
VG ∩ VH = ∅. It is evident that EG and EH are also disjoint in that case.
Exercises
◦ E 1.70 Let G be a complete graph with vertex set {1, 2, 3, 4, 5} and H be a
complete graph with vertex set {4, 5, 6, 7, 8}. Draw figures of the graphs G∪H
and G ∩ H.
E 1.71 Let G be the bishop graph and H be the rook graph (see exercises 1.10
and 1.11). Show that G ∪ H is the queen graph.
◦ E 1.72 Let G be the circuit 1 2 3 4 5 6 1 and H be the path 4 7 8 5. Draw figures

of the graphs G ∪ H and G ∩ H.
E 1.73 Let P be a set with endpoints u and v and Q be a path with endpoints v
and w. Show that if VP ∩ VQ = {v} then the graph P ∪ Q is a path.
E 1.74 Suppose that paths P and Q have the same endpoints, say u and v.
Suppose also that VP ∩ VQ = {u, v}. Under which conditions is the graph
P ∪ Q a circuit?
E 1.75 Let A, B and C be the sets {1, 2, 3, 4}, {5, 6, 7} and {9, 10, 11}. Let G be
the complete {A, B}-bipartite graph. Let H be the complete {B, C}-bipartite
graph. Draw figures of the graphs G ∪ H and G ∩ H.
E 1.76 A wheel is any graph in the form G ∪ H, where G is a circuit and H is

a star (see section 1.2) with center v such that VH r {v} = VG . Draw figures of
the wheels with 4, 5 and 6 vertices. What is the value of the parameters m, δ
and ∆ for a wheel with n vertices?
FEOFILOFF Planar graphs 23
1.6 Planar graphs

A graph is planar if it can be drawn in the plane in such a way that the
lines representing edges do not cross. This definition is not precise, but it is
sufficient for now. We will give a better definition in section 1.17.
Exercises
◦ E 1.77 Check that every path is planar. Check that every circuit is planar.
◦ E 1.78 Show that every grid (see exercise 1.6) is planar.
E 1.79 Show that the graph of European countries (see exercise 1.17) is pla-
nar.
E 1.80 Is the graph of points in the plane described in exercise 1.19 planar?
E 1.81 Show that every K4 is planar. Is it true that every K5 is planar?
E 1.82 Show that every K2,3 is planar. Is it true that every K3,3 is planar?
E 1.83 Show that the graph Q3 (see exercise 1.14) is planar. Is the graph Q4
planar as well? Is the graph Q5 planar?
E 1.84 Is the t-by-t bishop graph (see exercise 1.10) planar?
E 1.85 Is the t-by-t queen graph (see exercise 1.8) planar? Is the t-by-t knight
graph (see exercise 1.9) planar?
E 1.86 Show that the complement of a circuit of length 6 is planar.

FEOFILOFF Subgraphs 24
1.7 Subgraphs
A subgraph of a graph G is any graph H such that VH ⊆ VG and EH ⊆ EG . It
H⊆G is natural to write “H ⊆ G” to say that H is a subgraph of G.
A subgraph H of G is spanning if VH = VG . A subgraph H of G is proper
H ⊂ G if VH 6= VG or EH 6= EG . Sometimes it is convenient to write “H ⊂ G” to say
that H is a proper subgraph of G.21
The subgraph of G induced by a subset X of VG is the graph (X, F ),
G[X] where F is the set EG ∩ X (2) . This subgraph is denoted by
G[X] .
G−X For any subset X of VG , we will denote by G − X the subgraph G[VG r X].
In particular, for any vertex v,
G−v
is an abbreviation for G − {v}. For any edge e of G,
G−e
G−A is the graph (VG , EG r {e}). More generally, if A is a subset of EG , then G − A

is the graph (VG , EG r A). Of course G − A is a spanning subgraph of G.
Exercises
◦ E 1.87 Let H be a subgraph of G. If VH = VG , is it true that H = G? If
EH = EG , is it true that H = G?
◦ E 1.88 Let G be a graph, V 0 be a subset of VG and E 0 be a subset of EG . Is it

true that (V 0 , E 0 ) is a subgraph of G?
E 1.89 Repeat exercise 1.42: Use induction22 on the number of edges of the
graph to prove that every graph (V, E) satisfies the identity
P
v∈V d(v) = 2|E| .
◦ E 1.90 Let v be a vertex and e be an edge of a circuit O. Show that the graph
O − v is a path. Show that the graph O − e is a path.
E 1.91 Show that every subgraph of a planar graph is planar. In other words,
show that if G has a non-planar subgraph then G is not planar.
21
We write “X ⊂ Y ” or “Y ⊃ X” to say that the set X is a proper subset of Y , i.e., that
X ⊆ Y but X 6= Y .
22
Induction is the art of reducing a problem to a smaller version of itself.
E 1.92 Let v and w be two vertices of a graph G. Suppose that d(v) = δ(G)
and d(w) = ∆(G). Is it true that δ(G−v) = δ(G)−1? Is it true that ∆(G−w) =
∆(G) − 1?
◦ E 1.93 Verify that the t-by-t bishop graph is a subgraph of the t-by-t queen
graph. Verify that the t-by-t rook graph is a subgraph of the t-by-t queen
graph.
E 1.94 Is the graph Q3 a subgraph of Q4 ?
◦ E 1.95 Let G be a {U, W }-bipartite graph. Show that the induced subgraphs
G[U ] and G[W ] are empty.
◦ E 1.96 Show that every induced subgraph of a complete graph is complete.

Is it true that every induced subgraph of a path is a path? Is it true that every
induced subgraph of a circuit is a circuit?
◦ E 1.97 Let G be the graph represented in figure 1.8 and X be the set {a, b, f,
e, g, l}. Draw a figure of G[X].
a b c d
e f g h
i j k l
Figure 1.8: See exercises 1.97, 1.116 and 1.117.
E 1.98 ♥ Let H be the line graph (see exercise 1.24) of a graph G (whence
H = L(G)). Show that H does not contain K1,3 as an induced subgraph, i.e.,
show that there is no subset X of VH such that H[X] is a K1,3 . Show that the
converse is not true.
E 1.99 Let H be the line graph (see exercise 1.24) of a graph G (whence H =
L(G)). Let H 0 be an induced subgraph of H. Show that H 0 is the line graph
of some graph G0 .
E 1.100 Given a graph G and an integer k, find a maximum subset X of VG

such that δ(G[X]) ≥ k. (I.e., among all subsets X of VG that have the property
δ(G[X]) ≥ k, find one with maximum cardinality.)
E 1.101 Let G be a graph such that n(G) > 1 and δ(G) ≤ 12 µ(G). Show that G
has a vertex x such that
µ(G − x) ≥ µ(G) .
In other words, show that it is possible to remove a vertex without reducing
the average of the degrees in the graph.
E 1.102 Show that every graph G with at least one edge has a subgraph H
such that
δ(H) > µ(H)/2 but µ(H) ≥ µ(G) .
FEOFILOFF Cuts 27
1.8 Cuts
Let X be a set of vertices of a graph G. The cut induced by X (or the fringe
of X) is the set of all the edges with an endpoint in X and another in VG r X.
The cut induced by X will be denoted by ∂(X)
∂G (X)
or simply by ∂(X).23 (Some authors prefer to write, δ(X) or even ∇(X).)

We say that the cuts ∂(∅) and ∂(VG ) are trivial. Trivial cuts are, of course,
empty.
Clearly, |∂({v})| = d(v) for every vertex v. For every set X of vertices,
we will say that |∂(X)| is the degree of X, and we will denote this number
by d(X): d(X)
d(X) := |∂(X)| .
A cut or coboundary in a graph G is any set in the form ∂(X), where X is
a subset of VG . (A cut is, therefore, a set of edges rather than a set of vertices.)
Exercises
◦ E 1.103 Let X be a set of vertices of a graph G. Show that (VG , ∂(X)) is a
bipartite spanning subgraph of G.
E 1.104 Let G be the graph represented in figure 1.8. Is it true that the set
{ae, ef, f j, jk, cd, dh} is a cut?
a b c d
e f g h
i j k l
Figure 1.9: See exercise 1.104.
E 1.105 Find the smallest non-trivial cut you can in the 8-by-8 queen graph.
Find the largest non-trivial cut you can in the queen graph.
E 1.106 Find the smallest non-trivial cut you can in the t-by-t bishop graph.
23
Do not confuse ∂ with the Greek letter δ.
FEOFILOFF Cuts 28
E 1.107 Find the smallest cut you can in the Petersen graph. Find the largest
cut you can in the Petersen graph.
N(X) ◦ E 1.108 For any set X of vertices, we denote by N(X), the set of vertices in
VG r X that have one or more neighbors in X. Is it true that d(X) = |N(X)|
for every X?
It is clear that N(X) ⊆ x∈X N(x).24 Is it true that both sets are equal?
S
? E 1.109 Show that, for any graph G and any subset X of VG , we have that
P
x∈X dG (x) = 2m(G[X]) + dG (X) . (1.2)
(This is a generalization of exercise 1.42.)
E 1.110 Suppose that all the vertices of a graph G have even degree. Is it true
that d(X) is even for every subset X of VG ?
Suppose that all the vertices of a graph G have odd degree. Is it true that
d(X) is odd for every proper non-empty subset X of VG ?
E 1.111 (L ARGE CUT) Show that every graph has a cut containing at least
half the edges of the graph. In other words, show that every graph G has a
set X of vertices such that d(X) ≥ 12 m(G).
E 1.112 Show that every graph G has a bipartite spanning subgraph H that
satisfies the condition dH (v) ≥ dG (v)/2 for every vertex v.
Operations on cuts
E 1.113 (S YMMETRIC DIFFERENCE) Show that ∂(X ⊕ Y ) = ∂(X) ⊕ ∂(Y ) for
A⊕B any sets X and Y of vertices of a graph. Here, A ⊕ B denotes the symmetric
difference25 of sets A and B.
E 1.114 (S UBMODULARITY) Show that, in any graph G, for any subsets X

and Y of VG ,
d(X ∪ Y ) + d(X ∩ Y ) ≤ d(X) + d(Y ) .
24
S
If X = {x1 , x2 , . . . , xk }, then x∈X N(x) is the set N(x1 ) ∪ N(x2 ) ∪ · · · ∪ N(xk ), where
N(xi ) is the set of neighbors of xi , as defined in section 1.3.
25
The symmetric difference of two sets A and B is the set (A r B) ∪ (B r A). It is easy to
check that A ⊕ B = (A ∪ B) r (A ∩ B).
FEOFILOFF Cuts 29
E 1.115 (Consequence of 1.114) Let v and w be two vertices of a graph G.

An isolator 26 is any subset of VG that contains v but does not contain w. An
isolator X is minimum if d(X) ≤ d(X 0 ) for every isolator X 0 . Show that,
if X and Y are minimum isolators, then X ∪ Y and X ∩ Y are also minimum
isolators.
26
The term isolator is not standard. We use it here (and in chapter 15) for lack of a better
word.
FEOFILOFF Paths and circuits in graphs 30
1.9 Paths and circuits in graphs

If a path v1 · · · vp is a subgraph of G, then we may simply say that v1 · · · vp
is a path in G, or that G contains the path v1 · · · vp . For example, if we say
that u v w z is a path in G, we must understand that ({u, v, w, z}, {uv, vw, wz})
is a subgraph of G. An analogous convention holds for circuits which are
subgraphs of G.27
If v and w are the two endpoints of a path in G, then it is convenient to
say that the path goes from v to w, or that it begins at v and ends in w. But
those expressions must be used with caution, because paths are static and
have no orientation.
maximum A path P in a graph G is maximum if G does not contain a path of length
maximal greater than that of P . A path P in G is maximal if there is no path P 0 in G
such that P ⊂ P 0 .
Exercises
◦ E 1.116 Let G be the graph represented in figure 1.8. Is it true that e a b f g k
is a path in G? Is it true that e a b f c d is a path in G? Is it true that e a b f g k j i e
is a circuit in G?
E 1.117 Let G be the graph in figure 1.8. Is it true that G contains a circuit of
length 6? Is it true that G contains an induced circuit of length 6? (I.e., is it
true that there exists a subset X of VG such that G[X] is a circuit of length 6?)
Show an induced path of length 3 in G. (I.e., show a set X of vertices such
that G[X] is a path of length 3.) Show a path of length 3 in G which is not
induced.
. E 1.118 Let P be a path with endpoints x and x0 , and let Q be a path with
endpoints y and y 0 . Suppose that VP ∩ VQ 6= ∅. Show that there exists a path
with endpoints x and y in the graph P ∪ Q (see section 1.5).
Additional question: If z is a vertex in VP ∩ VQ , is it true that there exists,
in the graph P ∪ Q, a path from x to y that passes through z?
E 1.119 Find a circuit of minimum length in the Petersen graph (see exer-
cise 1.15 or figure 1.6). Find a circuit of maximum length in the Petersen
graph. Find a path of maximum length in the Petersen graph.
◦ E 1.120 Verify that the 3-by-3 knight graph contains a circuit. Find the
longest circuit you can in the 4-by-4 knight graph.
27
I would like to say “subpath of G” and “subcircuit of G”, but these expressions are not
used in the literature.
E 1.121 Find the longest path you can in the queen graph. Find the longest
circuit you can in the queen graph.
E 1.122 The Heawood28 graph has vertex set {0, 1, 2, . . . , 13}. Each vertex i
is a neighbor of (i + 1) mod 14 and of (i + 13) mod 14.29 Furthermore, each i
is a neighbor of a third vertex, which depends on the parity of i: if i is even,
then it is neighbor of (i + 5) mod 14, and if i is odd, then it is neighbor of
(i + 9) mod 14. Draw a figure of the graph. Find a circuit of minimum length
in the Headwood graph.
E 1.123 Suppose that a graph G has an odd circuit. Show that G also has
an induced odd circuit, i.e., show that there exists a set X of vertices such
that G[X] is an odd circuit. Does something analogous hold for even circuits?
E 1.124 Give an example of a graph G and a path in G that is maximal but

not maximum.
. E 1.125 ♥ Suppose that d(v) ≥ k for every vertex v of a graph. Show that
the graph has a path of length at least k. (Hint: take a maximal path.)30
The problem could be formulated like this: show that every graph G
contains a circuit with at least δ(G) + 1 vertices.
. E 1.126 Let G be a graph such that δ(G) ≥ 2. Prove that G has a circuit.
E 1.127 Let G be a graph such that δ(G) ≥ 3. Prove that G has a circuit of
even length.
E 1.128 Let k be a natural number greater than 1. Suppose that d(v) ≥ k for
every vertex v of a graph G. Show that G has a circuit of length at least k + 1.
In other words, show that G has a circuit with at least δ(G) + 1 vertices, as
long as δ(G) > 1. (See exercise 1.125.)
. E 1.129 Let P be a maximal path in a graph G. Let u and w be the endpoints

of P and suppose that d(u)+d(w) ≥ |VP | ≥ 3. Show that G has a circuit whose
vertex set is VP .
E 1.130 Let G be a graph with n > 1 vertices and at least 2n edges. Show
that G has a circuit of length ≤ 2 log2 n.
28
Percy John Heawood ( − ). (See article in Wikipedia.)
29
The expression “i mod j” denotes the remainder of the division of i by j.
30
Chapter 17 discusses the important but difficult problem of finding a path of maximum
length in a graph.
E 1.131 Let G be a graph without circuits of length smaller than 5. Show that
n(G) ≥ δ(G)2 + 1.
E 1.132 Show that every graph G with at least k n(G) edges contains a path
of length k. (Combine exercises 1.102 and 1.125.)
Paths and circuits versus cuts

We say that a cut ∂(X) separates a vertex x from a vertex y if X contains x
but not y. If ∂(X) separates x from y then, of course, X separates y from x.
E 1.133 Let P be a path in a graph G. Let X be a set of vertices that contains

one and only one of the endpoints of P . Show that EP ∩ ∂(X) 6= ∅.
? E 1.134 Prove that, for any pair (x, y) of vertices of a graph, one and only
one of the following statements is true: (1) a path connects x to y or (2) an
empty cut separates x from y. (Another formulation of the same exercise:
prove there exists a path from x to y if and only if no empty cut separates x
from y.)
E 1.135 (A LGORITHM) Write an efficient algorithm that will receive vertices

v and w of a graph G and find a path from v to w or show that no such path
exists.
Walks, trails and cycles

A walk in a graph is any finite sequence (v0 , v1 , v2 , . . . , vk−1 , vk ) of vertices
such that vi is adjacent to vi−1 for every i between 1 and k. (The vertices in
the walk may not be pairwise distinct.) We say that vertex v0 is the origin of
the walk and that vk is the terminus of the walk. We also say that the walk
goes from v0 to vk and that the walk connects v0 to vk .
The edges of the walk are v0 v1 , v1 v2 , . . . , vk−1 vk . (These edges may not be
pairwise distinct.) The length of the walk is the number k.
A trail is a walk without repeated edges, i.e., a walk whose edges are
pairwise distinct. It is clear that the length of a trail is equal to the cardinality
of its edge set.
A walk is simple if its vertices are pairwise distinct, i.e., if it has no
repeated vertices. Every simple walk is, of course, a trail.
A walk (v0 , . . . , vk ) is closed if its origin coincides with its terminus, i.e., if
v0 = vk . A cycle is a closed trail, i.e., a closed walk without repeated edges.31
. E 1.136 Let (v0 , v1 , v2 , . . . , vk ) be a walk with origin r and terminus s in a

graph G. Show that G has a path with endpoints r and s. More specif-
ically, show that there is a path with endpoints r and s in the subgraph
({v0 , v1 , v2 , . . . , vk } , {v0 v1 , v1 v2 , . . . , vk−1 vk }) of G.
E 1.137 Suppose that (v0 , . . . , vk ) is a closed walk in a graph G. Is it true

that G has a circuit?
. E 1.138 Let (v0 , v1 , v2 , . . . , vk ) be a cycle in a graph G. Show that there exists

a circuit in the subgraph ({v1 , v2 , . . . , vk }, {v0 v1 , v1 v2 , . . . , vk−1 vk }) of G.
◦ E 1.139 Let v0 , . . . , v5 be some vertices (not necessarily pairwise distinct) of

a graph G. Which of the following statements are true: (1) if v0 v1 v2 v3 v4 v5 is a
path in G, then (v0 , v1 , v2 , v3 , v4 , v5 ) is a simple walk; (2) if v0 v1 v2 v3 v4 v5 v0 is a
circuit in G, then (v0 , v1 , v2 , v3 , v4 , v5 , v0 ) is a cycle; (3) if (v0 , v1 , v2 , v3 , v4 , v5 ) is
a trail, then v0 v1 v2 v3 v4 v5 is a path; (4) if (v0 , v1 , v2 , v3 , v4 , v5 , v0 ) is a cycle, then
v0 v1 v2 v3 v4 v5 v0 is a circuit.
31
According to this definition, a cycle may have length 0. On the other hand, every circuit
has length at least 3.
FEOFILOFF Connected graphs 34
1.10 Connected graphs

In any graph G, we say that a vertex v is connected to a vertex w if G contains
a path with endpoints v and w. The relation is, of course, symmetric: if v is
connected to w, then w is connected to v.
A graph is connected if its vertices are pairwise connected. In other
words, a graph is connected if v is connected to w for each pair (v, w) of its
vertices.
A graph G is connected if and only if ∂(X) 6= ∅ for every proper non-
empty subset X of VG . (See exercise 1.148.)
Exercises
E 1.140 Is the 3-by-3 knight graph connected? Is the t-by-t bishop graph
connected?
E 1.141 Show that the graph Qk is connected (whatever the value of k).
E 1.142 Show that every path is a connected graph. Show that every circuit
is a connected graph.
. E 1.143 Let P and Q be two paths such that VP ∩ VQ 6= ∅. Show that the
graph P ∪ Q (see section 1.5) is connected.
. E 1.144 Let G and H be two connected graphs such that VG ∩ VH 6= ∅. Show

that the graph G ∪ H (see section 1.5) is connected.
◦ E 1.145 Let G and H be two graphs. Which of the following statements are
true? 1. If VG ∩ VH = ∅ then G ∪ H is not connected. 2. If G ∪ H is connected
then VG ∩ VH 6= ∅. 3. If G ∪ H is not connected then VG ∩ VH = ∅.
. E 1.146 ♥ Suppose that some vertex x of a graph G is connected to each of

the other vertices. Show that G is connected.
◦ E 1.147 Suppose that a spanning subgraph H of a graph G is connected.

Show that G is connected.
? E 1.148 Show that a graph G is connected if and only if ∂(X) 6= ∅ for

every X such that ∅ ⊂ X ⊂ VG .
◦ E 1.149 Let G be a graph and X be a proper non-empty subset of VG (i.e.,

∅ ⊂ X ⊂ VG ). Show that the graph G − ∂(X) is not connected.
◦ E 1.150 Which of the following statements are true for any graph G? 1. If G
is connected, then ∂(X) 6= ∅ for every X such that ∅ ⊂ X ⊂ VG . 2. If G is
connected, then ∂(X) 6= ∅ for some X such that ∅ ⊂ X ⊂ VG . 3. If ∂(X) 6= ∅
for every X such that ∅ ⊂ X ⊂ VG , then G is connected. 4. If ∂(X) 6= ∅ for
some X such that ∅ ⊂ X ⊂ VG , then G is connected.
E 1.151 Prove that if a graph G is not connected then its complement G is

connected.
E 1.152 (A LGORITHM) Devise an efficient algorithm to decide whether a

graph is connected. What does your algorithm return (i.e., what is the
“output” of the algorithm)?
E 1.153 Let x, y and z be three vertices of a connected graph G. Is it true

that G has a path that contains x, y and z?
◦ E 1.154 Let X be a set of vertices from a connected graph G. Is it true

that G[X] is connected?
?◦ E 1.155 Let e be an edge and v be a vertex in a circuit O. Show that the

graph O − e is connected. Show that O − v is connected.
◦ E 1.156 Let e be an edge and v be a vertex in a path P . Under what

conditions is P − e connected? Under what conditions is P − v connected?
. E 1.157 Let O be a circuit in a connected graph G. Show that G − e is

connected for every edge e of O.
E 1.158 Let v be a vertex of degree 1 in a connected graph G. Show that the

graph G − v is connected.
E 1.159 Suppose that G is a connected graph with at least one edge. Is it true
that there exists an edge a such that G − a is connected?
◦ E 1.160 Let G be a connected graph and let v be one of the endpoints of a

maximal path (see page 30) in G. Is it true that G[N(v)] is connected?
E 1.161 ♥ Show that every connected graph G with two or more vertices has
a vertex v such that G − v is connected.
? E 1.162 Prove that every connected graph on n vertices has at least n − 1

edges. In other words, show that in every connected graph G we have that
m(G) ≥ n(G) − 1 .
E 1.163 Let k be a natural non-null number and G a {U, W }-bipartite graph.

Suppose that |U | ≤ k and |W | ≤ k. Show that if δ(G) > k/2 then G is
connected.
E 1.164 Let G be a graph such that δ(G) ≥ n(G)/2. Show that G is connected.
E 1.165 Let G be a graph such that δ(G) ≥ bn(G)/2c.32 Show that G is

connected. (Show that the result is the best possible in the following sense:
there are disconnected graphs with d(v) ≥ bn/2c − 1 for every vertex v.)
◦ E 1.166 Suppose that d(v) + d(w) ≥ n − 1 for every pair (v, w) of non-
adjacent vertices of a graph G. Show that G is connected.
E 1.167 Show that every graph with n vertices and more than 21 (n − 1)(n − 2)
edges is connected.
◦ E 1.168 Let G be a graph and k be a natural number. Show that d(X) ≥ k

for every X such that ∅ ⊂ X ⊂ VG if and only if G − F is connected for every
subset F of EG such that |F | < k.
E 1.169 Let G be a connected graph. Prove that the line graph L(G) is also
connected.
E 1.170 (M AXIMUM PATHS ARE NOT DISJOINT) Let P ∗ and Q∗ be two paths
of maximum length in a connected graph G. Show that P ∗ and Q∗ have a
common vertex.
32
By definition, bxc is the only integer i such that i ≤ x < i + 1.
FEOFILOFF Components 37
1.11 Components
A connected subgraph H of a graph G is maximal (with regard to the prop-
erty of being connected) if it is not part of a greater connected subgraph, i.e.,
if there is no connected graph H 0 such that H ⊂ H 0 ⊆ G.
A component of a graph G is any maximal connected subgraph of G. The
number of components in a graph G will be denoted by c(G)
c(G) .
Clearly a graph G is connected if and only if c(G) = 1.
The number of components of any graph G is at least n(G) − m(G). (See
exercise 1.192.)
Exercises
E 1.171 How many components does the 3-by-3 knight graph have? How
many components does the t-by-t bishop graph have?
E 1.172 Let a be an edge and v be a vertex of a path P . Show that P − a has

exactly two components. Show that P − v has one or two components.
E 1.173 Let a be an edge and v be a vertex of a circuit O. Show that O − a has

only one component. Show that O − v has only one component.
E 1.174 Let P be a path and S be a proper subset of VP . Show that c(P − S) ≤

|S| + 1.
E 1.175 Let O be a circuit and S be a subset of VO such that 0 < |S| < n(O).
Prove that c(O − S) ≤ |S|.
E 1.176 Suppose that exactly two vertices, say u and v, of a graph G have odd
degree. Show that there exists a path in G whose endpoints are u and v.
. E 1.177 Let G be a graph such that ∆(G) ≤ 2. Describe the components

of G.
E 1.178 Let G be a 2-regular graph. Show that each component of G is a

circuit.
◦ E 1.179 Show that, in any graph, every vertex belongs to one and only one
component. In other words, show that the sets of vertices of all components
form a partition of VG .
◦ E 1.180 Let H be a component of a graph G. Show that ∂G (VH ) = ∅.
◦ E 1.181 Let X be a set of vertices of a graph G. Prove or disprove the

following claim: If ∅ ⊂ X ⊂ VG and ∂G (X) = ∅ , then G[X] is a component
of G.
E 1.182 Let X be a non-empty set of vertices of a graph G. Show that G[X] is

a component of G if and only if G[X] is connected and ∂G (X) = ∅.
? E 1.183 Let x be a vertex of a graph G. Let X be the set of all vertices that
are connected to x. Show that G[X] is a component of G.
E 1.184 (A LGORITHM) Devise an efficient algorithm that receives a vertex x

of a graph G and calculates the set of vertices of the component of G that
contains x.
E 1.185 (A LGORITHM) Devise an efficient algorithm to calculate the number

of components in any given graph.
E 1.186 Let H be a spanning subgraph of a graph G. Show that c(H) ≥ c(G).
E 1.187 Let e be an edge of a graph G. Show that c(G) ≤ c(G − e) ≤ c(G) + 1

for every edge e of G.
◦ E 1.188 Let X be a set of vertices of a graph G. Suppose that c(G − X) >

|X| + 1. Is it true that G is not connected?
E 1.189 Let v be a vertex of a connected graph G. Show that the number of

components of G − v is not greater than d(v).
E 1.190 Let G be a connected graph and suppose that d(v) is even for every
vertex v of G. Show that, for every vertex v, the number of components of
G − v is not greater than 21 d(v).
E 1.191 (A LGORITHM) Devise an efficient algorithm for the following prob-

lem: Given a graph G and a natural number k, find a set X with no more
than k vertices which maximizes the number of components of G − X.
? E 1.192 Show that for every graph G we have that

m(G) ≥ n(G) − c(G) .
E 1.193 Let n, m and c be the numbers of vertices, edges and components,

respectively, of a graph G. Show that
m ≤ 21 (n − c)(n − c + 1) .
FEOFILOFF Bridges 40
1.12 Bridges
A bridge (or isthmus, or cut edge) in a graph G is any edge e such that
c(G − e) > c(G), i.e., such that G − e has more components than G.
An edge e is a bridge if and only if the set {e} is a cut in the graph. (See
exercise 1.197.)
There is an interesting dichotomy between bridges and circuits: in any
graph, every edge is either a bridge or belongs to a circuit. (See exer-
cise 1.199.)
Exercises
◦ E 1.194 Does the t-by-t bishop graph have bridges?
E 1.195 Suppose that a graph G has a bridge uv. What does the adjacency
matrix of G look like? What does the incidence matrix of G look like?
◦ E 1.196 Let uv be an edge of a graph G. Show that uv is a bridge if and only

if u v is the only path in G with endpoints u and v.
◦ E 1.197 Let e be an edge of a graph G. Show that e is a bridge if and

only if {e} is a cut, i.e., {e} = ∂(X) for some set X of vertices. (See also
exercise 1.187.)
◦ E 1.198 Let G be the graph with vertices a, b, . . . , g and edges ab, bc, cd, de,
ec, bf , gb, ag. Which edges belong to circuits? Which edges are bridges?
? E 1.199 (B RIDGES / CIRCUITS DICHOTOMY) Prove that, in any graph, every

edge is of one and only one of two types: either it belongs to a circuit or it is
a bridge.
E 1.200 What is the shape of a graph all of whose edges are bridges? What
is the shape of a graph all of whose edges belong to circuits?
E 1.201 Suppose that all the vertices of a graph G have even degree. Show
that G has no bridges.
E 1.202 Let r be a natural number greater than 1 and let G be a r-regular

bipartite graph. Show that G has no bridges.
E 1.203 Let G be a connected graph and X a subset of VG such that d(X) = 1.

Show that the induced subgraphs G[X] and G[X] are both connected.
FEOFILOFF Bridges 41
E 1.204 (A LGORITHM) Devise an efficient algorithm to find all bridges of a

given graph.
FEOFILOFF Edge-biconnected graphs 42
1.13 Edge-biconnected graphs

A graph is edge-biconnected if it is connected, has three or more vertices,
and has no bridges.33
A graph with three or more vertices is edge-biconnected if and only
if each pair of its vertices is connected by two paths that have no com-
mon edges. (See exercise 1.208.) This property explains the name “edge-
biconnected.”
Exercises
◦ E 1.205 Show that every circuit is edge-biconnected. Show that paths are
not edge-biconnected.
E 1.206 Show that one of the two components of the 3-by-3 bishop graph is
edge-biconnected.
◦ E 1.207 Let G be an edge-biconnected graph. Show that d(X) ≥ 2 for every

non-empty proper subset X of VG .
? E 1.208 (T WO PATHS WITHOUT COMMON EDGES ) Let G be a graph with

at least three vertices that has the following property: every pair of vertices
of G is connected by two paths that have no common edges. In other words,
suppose that, for every pair (r, s) of vertices of G, there are paths P and Q,
both with endpoints r and s, such that EP ∩ EQ = ∅. Show that G is edge-
biconnected.
Let G be an edge-biconnected graph. Show that every pair of vertices
of G is connected by two paths that have no common edges.34 (Compare to
exercise 1.134.)
E 1.209 Show that m(G) ≥ n(G) for every edge-biconnected graph G.
33
In some branches of Computer Science, we say that such a graph is “fault tolerant.”
34
See a generalization in chapter 15, exercise 15.7.
FEOFILOFF Articulations and biconnected graphs 43
1.14 Articulations and biconnected graphs

An articulation or cut vertex in a graph G is a vertex v such that c(G − v) >
c(G), i.e., such that G − v has more components than G.
A graph is biconnected if it is connected, has no articulations, and has
three or more vertices.35
A graph with three or more vertices is biconnected if and only if each
pair of its vertices is connected by two internally disjoint paths (i.e., two
paths without common internal vertices). (See exercise 1.218.) This property
explains the name “biconnected.”
From this, it follows that a graph is biconnected if and only if each pair
of its vertices belongs to a circuit. (See exercise 1.219.)
Exercises
E 1.210 Let v be a vertex in a graph G. Show that v is an articulation if and
only if there are two vertices x and y in VG r {v} such that (1) some path in G
connects x to y and (2) every path between x and y contains v.
E 1.211 Let v be an articulation of a graph G. What is the shape of the

adjacency matrix of G? What is the shape of the incidence matrix of G?
◦ E 1.212 Is it true that every graph without articulations has no bridges? Is

it true that every graph without bridges has no articulations?
◦ E 1.213 Let T be a tree and v be a vertex of T such that d(v) ≥ 2. Is it true

that v is an articulation?
E 1.214 (A LGORITHM) Write an algorithm that finds all the articulations of

a graph.
E 1.215 Show that every circuit is biconnected.
E 1.216 The 3-by-3 bishop graph has two components. Show that only one
of them is biconnected.
◦ E 1.217 Show that not all edge-biconnected graphs are biconnected. Show
that every biconnected graph is edge-biconnected.
35
In some branches of Computer Science, we may say that such a graph is “fault tolerant.”
FEOFILOFF Articulations and biconnected graphs 44
? E 1.218 (T WO INTERNALLY DISJOINT PATHS) Let G be a graph with at least

three vertices that has the following property: every pair of vertices of G is
connected by two internally disjoint paths. In other words, suppose that, for
each pair (r, s) of vertices of G, there are paths P and Q, both with endpoints
r and s, such that VP ∩ VQ = {r, s}. Show that G is biconnected.
Let G be a biconnected graph. Show that every pair of vertices of G is
connected by two internally disjoint paths.36
E 1.219 (A RTICULATIONS VERSUS CIRCUITS) Suppose that every pair of ver-

tices of a graph G belongs to some circuit. Show that G has no articulations.
Let G be a biconnected graph. Show that every pair of vertices of G
belongs to some circuit. (See exercise 1.218.)
E 1.220 Show a graph that satisfies the following property: every two ver-
tices of the graph belong to a common circuit, but there are three vertices
that do not belong to a common circuit.
E 1.221 Let G be a connected graph with no articulations. Assuming that

δ(G) ≥ 3, show that G has a vertex v such that G − v is connected and has no
articulations. (Compare to exercise 1.161 in section 1.10.)
36
See a generalization in chapter 16, exercise 16.8.
FEOFILOFF Trees and forests 45
1.15 Trees and forests

This section deals with two important kinds of graphs: the forests and the
trees. Trees are a generalization of paths (see exercises 1.224 and 1.225) and
forests generalize trees.
A forest, or acyclic graph, is a graph with no circuits. This definition can
be restated as follows: a graph is a forest if each of its edges is a bridge (see
exercise 1.223). A tree is a connected forest. Clearly every component of a
forest is a tree.37 A leaf of a forest is any vertex of degree 1.
A graph G is a forest if and only if m(G) = n(G) − c(G). (See exer-
cise 1.231.)
Any two of the following properties imply the third: “G is a forest”,
“G is connected” and “m(G) = n(G) − 1.” (See exercises 1.228, 1.229
and 1.230.)
Exercises
◦ E 1.222 Show that every path is a tree. Show that every star (see section 1.2)
is a tree.
? E 1.223 Show that a graph is a forest if and only if each of its edges is a
bridge. (See exercise 1.199.)
E 1.224 Let (v1 , v2 , v3 , . . . , vn ) be a sequence of pairwise distinct objects. For

each j, let i(j) be an element of {1, . . . , j−1}. Show that the graph {v1 , v2 ,
v3 , . . . , vn } , {v2 vi(2) , v3 vi(3) , . . . , vn vi(n) } is a tree. (Compare this construction
to the definition of a path in section 1.4.) (Compare to exercise 1.225.)
E 1.225 Let T be a tree. Show that there exists a permutation (v1 , v2 , . . . , vn )

of VT with the following property: for j = 2, . . . , n, vertex vj is adjacent to ex-
actly one of the vertices of the set {v1 , . . . , vj−1 }. (Compare to exercise 1.224.)
? E 1.226 Show that a graph is a forest if and only if it has the following
property: for every pair (x, y) of its vertices, there exists at most one path
with endpoints x and y in the graph.
37
In Computer Science, the word “tree” brings to mind the ideas of parent and child. In
the present context, however, the expressions “parent of a vertex” and “child of a vertex” do
not make sense. (They only acquire meaning if one of the vertices in the tree is chosen to
play the role of a “root.” If r is the root of the tree, then the parent of any other vertex v is the
vertex adjacent to v in the only path (see exercise 1.226) that connects v to r. Every neighbor
of v which is not its parent is a child of v.)

given graph is a tree.
? E 1.228 Prove that m(T ) = n(T ) − 1 for every tree T . (Compare to

exercise 1.162.)
? E 1.229 Let G be a connected graph such that m(G) = n(G) − 1. Prove that
G is a tree.
E 1.230 Let F be a forest such that m(F ) = n(F ) − 1. Prove that F is a tree.
? E 1.231 Show that a graph G is a forest if and only if m(G) = n(G) − c(G).
(Compare to exercise 1.192.)
. E 1.232 Show that every tree with at least one edge has at least two leaves.
E 1.233 Show that every forest F has at least ∆(F ) leaves.
E 1.234 Let T be a tree with two or more vertices. LetPX be the set of vertices
whose degree is greater than 2. Show that T has 2 + x∈X (d(x) − 2) leaves.
E 1.235 Let T be a tree with vertices 1, . . . , n. Suppose that the degrees of the
vertices 1, 2, 3, 4, 5, 6 are 7, 6, 5, 4, 3, 2 respectively, and that vertices 7, . . . , n
are leaves. Determine n (and therefore the number of leaves of the tree).
E 1.236 Let T be a tree with p + q vertices. Suppose that p of the vertices have
degree 4 and q are leaves. Show that q = 2p + 2.38
E 1.237 Let T be a tree with at least three vertices. Is it true that the comple-
ment T of T is connected unless T is a star?
E 1.238 Let T be a tree and U be a subset of VT . Assuming that |U | is even,

show that there exists a subset X of ET such that dT −X (u) is odd for every u
in U , and dT −X (v) is even for every v in VT r U .
E 1.239 (H ELLY PROPERTY39 ) Let P, Q, R be three paths in a tree T . Suppose

that VP ∩ VQ 6= ∅, VQ ∩ VR 6= ∅ and VP ∩ VR 6= ∅. Prove that VP ∩ VQ ∩ VR 6= ∅.
38
Imagine that the vertices of degree 4 are carbon atoms and those of degree 1 are
hydrogen atoms. The graph represents then a molecule of the hydrocarbon Cp Hq . See
exercise 1.5.
39
Reference to mathematician Eduard Helly ( − ).
E 1.240 Prove that every forest is planar.

FEOFILOFF Graph minors 48
1.16 Graph minors

This section introduces the concept of minor, which can be seen as a gen-
eralization of the idea of subgraph. We can say that a minor describes the
“gross” structure of the graph, while a subgraph describes the “fine” struc-
ture. Minors have an important role in the study of planarity (chapter 19),
vertex coloring (chapter 8) and many other problems.
A graph H is a minor, or subcontraction, of a graph G if VH is a subpar-
tition40 {V1 , . . . , Vp } of VG such that
• every subgraph G[Vi ] is connected and
• if Vi is adjacent to Vj in H then there exists an edge from Vi to Vj in G
(but there may exist an edge from Vi to Vj in G even if Vi is not adjacent to Vj
in H). The expression “H is a minor of G” is also used, in a broader sense, to
say that H is isomorphic to a minor of G.
In a very informal way, we can say that H is a minor of G if H can be
obtained from a subgraph of G by successive “edge contraction” operations.
(The “contraction” of an edge uv makes vertices u and v coincide.)
Figure 1.10: The graph on the right, H, is a minor of the graph on the
left, G. (This is a very special minor, since V1 ∪ · · · ∪ Vp = VG .)
A graph H is a topological minor of a graph G if VH ⊆ VG and there

exists a function P that maps each edge in H to a path in G in such a way
that
• for every edge xy of H, the path P (xy) has endpoints x and y and has
no internal vertices in VH , and
• if xy and uv are two distinct edges in H, then P (xy) and P (uv) have
no common internal vertices.
The expression “H is a topological minor of G” is also used, in a broader
sense, to say that H is isomorphic to some topological minor of G.
40
A subpartition of a set V is a collection {V1 , . . . , Vp } of non-empty subsets of V such
that Vi ∩ Vj = ∅ whenever i 6= j.
A topological minor is a special type of minor, although this is not imme-

diately apparent. (See exercise 1.250.)
If H is a topological minor of G, we also say that G contains a subdi-
vision of H, because it is possible to obtain a subgraph of G from H by
successive “edge subdivision” operations. (Each “subdivision” of an edge
creates a new vertex of degree two in the “interior” of the edge.)
Exercises
◦ E 1.241 Let H be a subgraph of a graph G. Show that H is a topological
minor of G.
◦ E 1.242 Let H be a subgraph of a graph G. Show that H is isomorphic to a

minor of G.
E 1.243 Show that a graph G has a topological minor which is isomorphic

to K3 if and only if G contains a circuit.
E 1.244 Show that a graph G has a minor isomorphic to K3 if and only if G

contains a circuit.
E 1.245 Let G be the 4-by-4 king graph. Let u be the vertex with coordinates
(2, 2), and v be the vertex with coordinates (3, 3). Show that G + uv does not
have a subgraph isomorphic to K4 but has a topological minor isomorphic
to K4 .
E 1.246 Let G be the 5-by-5 king graph. Let u be the vertex with coordinates
(2, 2) and v be the vertex with coordinates (4, 4). Show that G + uv has no
subgraph isomorphic to K4 but has a minor isomorphic to K4 .
Let x be the vertex with coordinates (2, 4) and y be the vertex with
coordinates (4, 2). Show that G + uv + xy has a minor isomorphic to K4 .
E 1.247 Show that the Petersen graph has a minor isomorphic to K5 (but
has neither a subgraph isomorphic to K5 nor a topological minor isomorphic
to K5 ).
E 1.248 Show that the Petersen graph has a topological minor isomorphic
to K3,3 . Show that the Petersen graph has a minor isomorphic to K3,3 .
E 1.249 Show that K3,3 is isomorphic to a topological minor of the cube Q4 .

Show that K5 is a topological minor of Q4 .
? E 1.250 Show that if H is a topological minor of G then H is isomorphic to

a minor of G. Show that the converse is not true.
? E 1.251 Let H be a minor of a graph G. Suppose that ∆(H) ≤ 3. Prove

that H is isomorphic to a topological minor of G. Give a good example to
show that the condition “∆(H) ≤ 3” is essential.
HG E 1.252 If H is (isomorphic to) a minor of G, we write H G. Show that is

an order relation. More precisely, show that
1. G G,
2. if H G and G H, then H ∼= G,
3. if H G and G F , then H F .
Show also that the is-a-topological-minor-of relation is an order relation.
FEOFILOFF Plane maps and their faces 51
1.17 Plane maps and their faces

We have said in section 1.6 that, roughly speaking, a graph is planar if it can
be drawn in the plane41 in such a way that edges do not cross. The exact
definition involves the concepts of polygonal arc and plane map, which we
discuss next.
A polygonal arc is any finite union of line segments in the plane R2 that
is topologically homeomorphic to the closed interval [0, 1] of the line R. In
other words, a finite union c of line segments is a polygonal arc if there is
a topologically continuous bijection of the interval [0, 1] into c. The images
of 0 and 1 under this continuous bijection are the endpoints of the polygonal
arc.42
A plane map43 is a pair (V, E) of finite sets, where V is a set of points in V
the plane R2 , and E is a set of polygonal arcs such that E
• the endpoints of each polygonal arc are elements of V,
• the interior of each polygonal arc is disjoint from V,
• the interior of each polygonal arc is disjoint from every other polygo-
nal arc,
• two different polygonal arcs have at most one endpoint in common.
The elements of V are the points44 of the map, and the elements of E are the points
lines45 of the map. lines
Figure 1.11: The map on the left is not plane. The plane
map on the right represents a K4 .
The graph of a plane map (V, E) is defined in the obvious way: the vertex graph of
set of the graph is V, and two vertices v and w are adjacent in the graph if a a map
line on the map has endpoints v and w. (We must be careful with the notation,
since the letter ”V” is being used to name both the set of points of a plane map
and the set of vertices of the corresponding graph. Similarly, the letter “E” is
41
From a technical point of view, it would be more convenient to use the surface of the
sphere instead of the plane. But the results are equivalent.
42
By definition, the two endpoints are distinct.
43
Some authors say “plane graph.” Do not mistake this expression with “planar graph.”
44
I prefer not to say “vertices” to avoid confusion with the vertices of a graph.
45
I prefer not to say “edges” to avoid confusion with the edges of a graph.
being use to name both the set of lines of a plane map and the set of edges of
the corresponding graph.)
map We say that a plane map M represents a graph G if the graph of M is
represents isomorphic (see chapter 2) to G. Generally, a graph can be represented by
graph many different plane maps.
A graph G is planar if it is representable by a plane map, i.e., if there is a
plane map whose graph is isomorphic to G. This is the precise version of the
vague definition we gave in section 1.6.
Exercises
E 1.253 See the “planarity game” in www.planarity.net.
E 1.254 Is the Petersen graph (see figure 1.6) planar?
E 1.255 Let G be a K5 (i.e., a complete graph with 5 vertices). Show that G − e

is planar for every edge e of G. Repeat the exercise for K3,3 (see figure 19.1)
in place of K5 .
◦ E 1.256 Show that a graph is planar if and only if each of its components is
planar.
E 1.257 Let e be a bridge of a graph G. Show that G is planar if and only if

G − e is planar.
Let v be an articulation of G. Show that G is planar if and only if G − v is
planar.
Faces and planar duality

S
The support of plane map (V, E) is the set V ∪ E (this is, obviously, a
subset of R2 ).46 In other words, the support of the map is the set of all the
points of R2 that are points of the map or belong to lines of the map.
A face of a plane map (V, E) is any region of the complement of the sup-
port of a map, i.e., anySconnected component — in the topological sense47 —
of the set R2 r V ∪ E). The boundary of each face is formed by lines of
the map; the number of lines in the boundary of a face F is the degree of F .
46
S
If X = {X1 , X2 , . . . , Xk }, then X denotes the set X1 ∪ X2 ∪ · · · ∪ Xk .
47
The topological concept of connection is formally analogous to the concept of connec-
tion in graph theory: a subset X of the plane is connected if, for any points x and x0 in X,
there is a polygonal arc with endpoints x and x0 whose points are all in X.
Let G be the graph of a plane map M with 3 or more points. If G

is edge-biconnected, then the faces of M are “well-behaved”: each face is
topologically homeomorphic to a disk, and each line belongs to the boundary
of two different faces. If G is biconnected, then the faces of M are even more
“well-behaved”: the boundary of each face corresponds to a circuit of G.
The graph of the faces, or dual graph, of a plane map M is defined as
follows: the vertices of the graph are the faces of the map, and two faces
are adjacent if their boundaries share at least one line.48 (Note that the dual
graph is defined for a map rather than for the graph of the map. A planar
graph can be represented by many different plane maps,49 and each of these
maps has its dual graph.)
An example: the graph of countries of Europe we examined in exer-
cise 1.17 is the dual graph of the map (in the ordinary, geographic, sense)
of Europe.
Exercises
E 1.258 Let M be a plane map, and suppose that the graph of the map is a
path. Show that M has only one face.
Let M be a plane map, and suppose that the graph of the map is a
circuit. Show that M has exactly two faces (and the two faces have the same
boundary).
E 1.259 Show that a plane map has exactly one face if and only if the graph
of the map is a forest.
E 1.260 Consider a plane map that represents the p-by-q grid. How many
faces does the map have?
E 1.261 Let M be a plane map that represents the 3-by-4 grid. Draw a figure
of the graph of the faces (i.e., of the dual graph) of M.
E 1.262 How many faces does a plane map representing the cube Q3 have?
E 1.263 Draw a figure of the graphs of the faces of each of the plane maps in
figures 1.12 and 1.13.
48
The study of the planar duality is “cleaner” if the definition of a graph is relaxed to
allow “parallel edges” (i.e., two or more different edges with the same pair of endpoints)
and “loops” (i.e., an edge with two equal endpoints). Of course the definition of plane map
should be relaxed accordingly. I prefer not to adopt such a relaxation in the present text. To
make up for that, it will be often necessary to avoid graphs with articulations or vertices of
degree 2.
49
But see exercise 1.282.
Figure 1.12: Draw a figure of the dual graph of each of

the plane maps in the figure.
Figure 1.13: Draw a figure of the dual graph of each of

the plane maps in the figure.
E 1.264 Let G be a K5 , and e be an edge of G. Let M be a plane map that

represents G − e. Let G∗ be the graph of the faces (i.e., the dual graph) of M.
Draw a figure of G∗ . Check that G∗ is planar. Show a plane representation,
say M∗ , of G∗ . Draw a figure of the graph of the faces of M∗ .
E 1.265 Give an example of a connected planar graph that can be represented

by two plane maps with different numbers of faces.
? E 1.266 (E ULER ’ S FORMULA50 ) Let (V, E) be a plane map whose graph is

connected. Show that
|V| − |E| + |F| = 2 , (1.3)
where F is the set of faces of the map. (Check that the formula is false for
maps whose graphs are not connected.) (Compare to exercise 1.228.)
E 1.267 Let G be an edge-biconnected planar graph. Let (V, E) be a plane

map P that represents G, and let F be the set of faces of the map. Show
that F ∈F d(F ) = 2|E|, where d(F ) is the degree of face F . (Compare to
exercise 1.42.)
50
Leonhard Euler ( − ). See article on Wikipedia.
? E 1.268 Let G be a connected planar graph with three or more vertices.

Show that
m(G) ≤ 3n(G) − 6 . (1.4)
(Hint: Make an induction on the number of bridges.) Deduce from this that
the inequality holds for any planar graph with three or more vertices. What
do the faces of a plane map with n points and exactly 3n − 6 lines look like?
◦ E 1.269 Is it true that every graph G with m(G) ≤ 3n(G) − 6 is planar?
E 1.270 Deduce from inequality (1.4) that K5 is not planar.
E 1.271 Let G be an edge-biconnected planar graph. Suppose that the girth

(see chapter 14) of G is at least 4. Show that m(G) ≤ 2n(G) − 4. (Compare to
exercise 1.268.) Deduce from this inequality that K3,3 is not planar. Deduce
from this inequality that Q4 is not planar.
E 1.272 Let G be a bipartite graph with three or more vertices. Assuming G

is planar, show that m(G) ≤ 2n(G) − 4. (See exercise 1.271.)
E 1.273 Let G be a {U, W }-bipartite graph. Assuming G is planar, show that

m(G) ≤ 2|U | + 2|W | − 4.
E 1.274 Let G be a graph and k be a natural number not less than 3. Suppose
that G has at least 21 (k + 2) vertices and girth at least k. Assuming G is planar,
show that m(G) ≤ (n(G) − 2)k/(k − 2). (Compare to exercise 1.271.)
? E 1.275 Show that every planar graph has at least one vertex with degree
at most 5. In other words, show that δ(G) ≤ 5 for every planar graph G.
Give an example of a planar graph that has no vertices of degree smaller
than 5.
E 1.276 Let G be a bipartite planar graph. Show that δ(G) ≤ 3.
◦ E 1.277 A plane map “of type (n, m, d, g)” is a plane map with n points and
m lines whose points have degree d and whose faces have degree g. Show a
plane map of type (4, 6, 3, 3). Show a plane map of type (6, 12, 4, 3). Show a
plane map of type (8, 12, 3, 4).
◦ E 1.278 Let G be a biconnected cubic graph with 10 vertices. Show that

G cannot be represented by a plane map all of whose faces have the same
degree.
E 1.279 Let G be a graph with 11 or more vertices. Show that G and its
complement G cannot be both planar.
E 1.280 A plane map is self-dual if its graph is isomorphic to its dual graph.
Show that 2|V| = |E| + 2 if (V, E) is self-dual. Show that not every plane map
(V, E) such that 2|V| = |E| + 2 is self-dual.
? E 1.281 Let G be the graph of a plane map M. Suppose that G is bicon-

nected and has no vertices of degree 2 (i.e., δ(G) ≥ 3). Let G∗ be the graph of
the faces (i.e., the dual graph) of the map M. Show that G∗ is planar.
Let M∗ be a plane map that represents G∗ . Let G∗∗ be the graph of the
faces of M∗ . Show that G∗∗ ∼ = G, i.e., that G∗∗ is isomorphic to G.
! E 1.282 (W HITNEY ’ S THEOREM) Every 3-connected planar graph (see

page 131) has essentially a unique plane map. Here “essentially” means that
all the plane maps are equivalent. Two maps of a same graph are equivalent
if the set of edges of the corresponding face boundaries are equal.
E 1.283 (O UTERPLANAR) A plane map M is outerplane if all its points are

on the boundary of the same face. A graph G is outerplanar if it is repre-
sentable by an outerplane map.
Show that K4 is not outerplanar. Show that K2,3 is not outerplanar.
E 1.284 Show that the dual graph of an outerplane map (see exercise 1.283)
may not be planar.
E 1.285 Let M be an outerplane map (see exercise 1.283). Let F be the face
whose boundary contains all the points of M. Let G∗ be the graph of the faces
(i.e., the dual graph) of M. Show that G∗ − F is a tree.
E 1.286 Let e be an edge of an outerplanar graph G (see exercise 1.283). Is

it true that there is an outerplane map of G in which the representation of e
belongs to the boundary of the face that contains all the vertices?
FEOFILOFF Random graphs 57
1.18 Random graphs

Let V be the set {1, . . . , n} and let G(n) be the collection51 of all the graphs V
with vertex set V . It is obvious that G(n)
|G(n)| = 2N , com N := n2 .

Any graph property (like, for example, the property of being connected)52 N
defines a subcollection of G(n). Thus, we do not distinguish the concepts of
“property” and “subcollection” of G(n). We will say that almost every graph
has a given property P(n) if
|P(n)|
lim = 1.
n→∞ |G(n)|
One way to study the set G(n) is based on the introduction of a probabil-
ity measure in this set. Let p be a number in the interval (0, 1), and choose
each element of V (2) , independently, with probability p. (See exercise 1.20.)
If A is the set of chosen pairs, then (V, A) is a random graph in G(n). The
probability that a graph (V, A) built in this way is identical to a given element
of G(n) with m edges is
pm (1 − p)N −m .
If p = 21 , then all the 2N graphs in G(n) are equiprobable: the probability of
obtaining any one of them is 1/2N .
Exercises
◦ E 1.287 Show that almost every graph in G(n) has more than 10000 edges.
E 1.288 Show that almost every graph G in G(n) is connected. (See sec-
tion 1.18.)
51
“Collection” is the same as “set.”
52
Naturally, we are only interested in properties that are invariant under isomorphism
(see chapter 2).
FEOFILOFF Random graphs 58
Chapter 2
Isomorphism
Two graphs are isomorphic if they have the same “structure.” The exact
definition of the concept is a bit laborious, as we will see next.
An isomorphism between two graphs G and H is a bijection1 f from VG
to VH such that, for every pair (v, w) of elements of VG , v and w are adjacent
in G if and only if f (v) and f (w) are adjacent in H.
Two graphs G and H are isomorphic if there exists an isomorphism
between them. In other words, two graphs are isomorphic if it is possible
to change the names of the vertices in one of them in such a way that the two
graphs become equal. The expression “G ∼ = H” is an abbreviation for “G is ∼
=
isomorphic to H.”
I SOMORPHISM P ROBLEM: Decide whether two given graphs are iso-

morphic.
Exercises
E 2.1 A graph G has vertex set {a, b, c, d} and edge set {ab, bc, cd, da}. A
graph H has vertex set {a, b, c, d} and edge set {ab, bd, dc, ca}. Are graphs G
and H equal?
E 2.2 Are the graphs G and H described below isomorphic?
VG = {a, b, c, d, e, f, g} EG = {ab, bc, cd, cf, f e, gf, ga, gb}

VH = {h, i, j, k, l, m, n} EH = {hk, nj, jk, lk, lm, li, ij, in}
What if we replace hk with hn in EH ?

1
A bijection is a function f from a set A to a set B such that (1) f (a) 6= f (a0 ) whenever
a 6= a0 , and (2) for every b in B there exists a in A such that b = f (a).
59
FEOFILOFF Isomorphism 60
E 2.3 Are the graphs in figure 2.1 isomorphic?
Figure 2.1: Are these graphs isomorphic?
E 2.4 Show that two paths are isomorphic if and only if they have the same
length. Show that two circuits are isomorphic if and only if they have the
same length.
E 2.5 List all the graphs with vertex set {1, 2, 3, 4} that are pairwise non-
isomorphic. (In other words, make the list in such a way that every graph
with 4 vertices is isomorphic to one and only one of the graphs in the list.)
E 2.6 For n = 1, 2, 3, . . . , make a list of all the trees with vertex set {1, 2,
3, . . . , n} that are pairwise non-isomorphic.
E 2.7 Are the graphs in figure 2.2 pairwise isomorphic?
Figure 2.2: Are these graphs pairwise isomorphic?
E 2.8 Are the graphs in figure 2.3 isomorphic? Justify your answer.

. .
E 2.9 Are the graphs in figure 2.4 isomorphic? Justify your answer.
E 2.10 Let G be the 3-by-4 grid and H be the 4-by-3 grid (see exercise 1.6).
Are graphs G and H equal? are they isomorphic?
E 2.11 Show that the p-by-q grid and the graph defined in exercise 1.7 are
isomorphic.
E 2.12 Show that the cube Q3 is isomorphic to some subgraph of Q4 .
E 2.13 Show that the cube Q4 has a subgraph isomorphic to the 4-by-4 grid.
E 2.14 For which values of t are the two components of the t-by-t bishop
graph isomorphic?
D 2.15 Characterize the graphs that are isomorphic to a subgraph of Qk .
E 2.16 Suppose that graphs G and H are isomorphic. Show that n(G) = n(H)
and m(G) = m(H). Show that, for any isomorphism f from G to H, we have
dG (v) = dH (f (v)) for every v in VG . Assuming G has a circuit of length k,
show that H also has a circuit of length k.
E 2.17 (A LGORITHM) The following algorithm is supposed to decide

whether graphs G and H are isomorphic:
examine all bijections from VG to VH ;
if one of them is an isomorphism, then G is isomorphic to H;
otherwise, G and H are not isomorphic.
Discuss the algorithm.
E 2.18 (A LGORITHM) The following algorithm is supposed to decide

whether graphs G and H are isomorphic:
if n(G) 6= n(H) then G and H are not isomorphic;
if m(G) 6= m(H) then G and H are not isomorphic;
if |{ v ∈ VG : dG (v) = i }| =
6 |{ v ∈ VH : dH (v) = i }| for some i
then G and H are not isomorphic;

otherwise G and H are isomorphic.
Discuss the algorithm.
E 2.19 Let G and H be two graphs and f be a bijection from VG to VH such

that dG (v) = dH (f (v)) for every v in VG . Is it true that G ∼
= H?
◦ E 2.20 True or false? To show that two graphs G and H with the same
number of vertices are not isomorphic, it suffices to exhibit a bijection f
from VG to VH and a pair of vertices u and v in VG such that (1) uv ∈ EG
but f (u)f (v) ∈
/ EH or (2) uv ∈
/ EG but f (u)f (v) ∈ EH .
E 2.21 Let A be the set of all graphs that represent the alkanes that have
formula C4 H10 . (See exercise 1.5.) Each of these alkanes has 4 vertices of
degree 4 and 10 vertices of degree 1. How many pairwise non-isomorphic
graphs are there in A?
E 2.22 Show that the line graph (see exercise 1.24) of a K5 is isomorphic to
the complement of the Petersen graph.
E 2.23 Is it true that every graph is isomorphic to the line graph (see exer-
cise 1.24) of some other graph?
E 2.24 Let X be a set of vertices in a graph G. Suppose that the induced

subgraph G[X] is a star (see section 1.2) with 4 vertices. Show that G is not
isomorphic to the line graph (see exercise 1.24) of another graph, i.e., that
there is no graph H such that G ∼
= L(H).
E 2.25 Let G be the Petersen graph. Given any two vertices u and v in G,
show that there exists an isomorphism from G to G (isomorphisms of this
kind are known as automorphisms) which maps u to v. Given any two
edges uv and xy of G, show that there exists an isomorphism from G to G
that maps uv to xy (i.e., maps u to x and v to y, or maps u to y and v to x).
E 2.26 A graph is self-complementary if it is isomorphic to its complement.

Assuming G is a self-complementary graph, show that n(G) = 0 (mod 4) or
n(G) = 1 (mod 4).2
2
The expression “x = i (mod 4)” means that the remainder of the division of x by 4 and
the remainder of the division of i by 4 are equal, i.e., that x mod 4 = i mod 4. In other words,
x − i is divisible by 4.
D 2.27 Find an efficient characterization of non-isomorphic graphs. In other

words, find a property X which is easy to verify and makes the following
statement true: “Two graphs G and H are not isomorphic if and only if X .”
D 2.28 (A LGORITHM) Sketch a fast algorithm to solve the isomorphism

problem (i.e., to decide whether two given graphs are isomorphic).
Chapter 3
Graph design with given degrees
A graph G realizes a sequence (g1 , g2 , . . . , gn ) of natural numbers1 if the

vertices of the graph are 1, 2, . . . , n and d(i) = gi for every i.
A sequence (g1 , g2 , . . . , gn ) of natural numbers is graphic if some graph graphic
realizes it. sequence
G RAPH D ESIGN P ROBLEM: Given a sequence of natural numbers,

decide if it is a graphic or not.
Exercises
E 3.1 Consider the sequences (2, 2, 0), (1, 1, 2, 2), (0, 3, 1, 0), (0, 1, 2, 2, 3),
(3, 3, 2, 2, 1), (6, 6, 5, 4, 3, 3, 1) and (7, 6, 5, 4, 3, 3, 2). Which of these sequences
are graphic?
P1 , g2 , . . . , gn ) is a graphic sequence. Show that gi ≤ n − 1

E 3.2 Suppose that (g
for every i and that gi is even. Formulate the converse; is it true?
E 3.3 Show that (g1 , g2 , . . . , gn ) is a graphic sequence if and only if (n−g1 −1,
n−g2 −1, . . . , n−gn −1) is a graphic sequence. (This fact can be used as a basis
for an algorithm to recognize graphic sequences.)
E 3.4 Prove that, for each n ≥ 5, there is a 4-regular graph with n vertices.
E 3.5 Is it true that, for every number r, there is a r-regular graph? Is it true
that, for every pair (r, n) of numbers such that r < n, there is a r-regular
graph with n vertices?
1
The set of the natural numbers is {0, 1, 2, . . .}.
65
FEOFILOFF Graph design with given degrees 66
E 3.6 Suppose that (g1 , g2 , . . . , gn ) is a graphic sequence and that k is a natural

number ≤ n. Show that
(k, g1 +1, g2 +1, . . . , gk +1, gk+1 , . . . , gn )
is also a graphic sequence. Formulate the converse statement; is it true?
? E 3.7 (T HEOREM H AVEL AND H AKIMI2 ) Let (k, g1 , g2 , . . . , gn ) be a se-

OF
quence of natural numbers such that k ≥ g1 ≥ g2 ≥ . . . ≥ gn . Suppose that
the sequence
(g1 − 1, g2 − 1, . . . , gk − 1, gk+1 , . . . , gn )
is graphic. Show that the first sequence is also graphic.
? E 3.8 (T HEOREM OF E RD ŐS3 AND G ALLAI4 ) ShowP that a sequence (g1 ,

g2 , . . . , gn ) of natural numbers is graphic if and only if i gi is even and
k
X n
X
gi ≤ k(k − 1) + min (k, gi )
i=1 i=k+1
for each k such that 1 ≤ k ≤ n.
E 3.9 (A LGORITHM) Sketch an efficient algorithm to solve the graph design

problem stated above, i.e., to decide whether a given sequence of natural
numbers is graphic. Seek for inspiration in exercises 3.6 and 3.7, or in
exercise 3.8.
E 3.10 Let g1 , . . . , gn be positive integer numbers. Suppose that ni=1 gi =

P
2(n − 1). Show that there is a tree (see section 1.15) T with vertices 1, . . . , n
such that d(i) = gi for each i.
2
Published in 1955 by Václav Havel, and in 1962 by S. Louis Hakimi.
3
Paul Erdős ( − ). (See article on Wikipedia.)
4
Tibor Gallai ( − ).
Chapter 4
Bicolorable graphs
A bicoloring of a graph G is a bipartition1 {U, W } of VG such that every edge

of G has an endpoint in U and another in W . (You can imagine that all the
vertices in U are red and all the vertices in W are blue.) For example, every
bipartite graph (see section 1.2) has an obvious bicoloring.
B ICOLORING P ROBLEM: Find a bicoloring of a given graph.
Deciding whether the problem has a solution at all — i.e., whether the
graph admits2 a bicoloring — is part of the problem.3 We will say that a
graph is bicolorable if it admits a bicoloring. Therefore, a bicolorable graph
is the same as a bipartite graph.4
As we will see later (exercise 4.15), a graph is bicolorable if and only if it
does not contain an odd circuit. We say that a circuit is odd if its length is an
odd number.
Exercises
? E 4.1 Show that a graph G is bicolorable if and only if EG is a cut.
E 4.2 Show that the t-by-t knight graph is bicolorable.

1
A bipartition of a set V is a pair {U, W } of non-empty subsets of V such that U ∪W = V
and U ∩ W = ∅. The bipartition is the pair {U, W }; it makes no sense to say “U is one of the
bipartitions of V .” Instead, say “U is one of the elements of the bipartition.”
2
The expression “admits a bicoloring” means the same as “has a bicoloring.”
3
Many problems in graph theory are of the kind “show that this graph does not have
property X.” In the present case, the question is “show that this graph does not admit a
bicoloring.” The answer “try all possible bipartitions of VG ” is not satisfactory, because the
number of bipartitions is huge: a set of size n has 2n−1 different bipartitions.
4
Actually, there is a subtle distinction between the two concepts: a bicolorable graph
only becomes bipartite after one of its bicolorings is explicitly given.
67
FEOFILOFF Bicolorable graphs 68
E 4.3 Is it true that the t-by-t bishop graph is bicolorable?
E 4.4 Show that every cube Qk is bicolorable.
E 4.5 Show that every grid is bicolorable.
◦ E 4.6 Show that every path is bicolorable. Show that every even-length
circuit is bicolorable.
E 4.7 Show that a graph may have two or more different bicolorings. Show
that connected graphs have at most one bicoloring.
. E 4.8 Show that every forest is bicolorable.
E 4.9 Let {U, W } be a bicoloring of a forest such that |U | = |W |. Show that

the forest has at least one leaf in U and one in W .
◦ E 4.10 Suppose that a graph G is bicolorable. Is it true that every subgraph

of G is bicolorable? Is it true that every induced subgraph of G is bicolorable?
E 4.11 Are the graphs in figure 4.1 bicolorable?
Figure 4.1: Exercise 4.11. Are these graphs bicolorable?
E 4.12 ♥ How many edges can a bicolorable graph with n vertices have?
◦ E 4.13 Suppose that a graph G has an odd circuit. Show that G is not
bicolorable.
? E 4.14 Show that every graph without odd circuits is bicolorable.5
? E 4.15 (S OLVING THE BICOLORING PROBLEM) Deduce from 4.13 and 4.14
that a graph is bicolorable if and only if it has no odd circuits.
5
Therefore, an odd circuit is a certificate of inexistence of a bicoloring of the graph.
Conversely, a bicoloring of the graph is a certificate of absence of odd circuits.
E 4.16 We say that a graph G has an induced circuit if there exists X ⊆ VG

such that G[X] is a circuit. Show that a graph is bicolorable if and only if it
has no induced odd circuits.

given graph is bicolorable. The algorithm must return a bicoloring of the
graph or an odd circuit.
E 4.18 (E VEN / ODD PATH) Let G be a biconnected graph. Let r and s be two
vertices of G. There is an even-length path from r to s and an odd-length
path from r to s (the two paths are not necessarily disjoint) if and only if G is
not bicolorable.
E 4.19 (O DD CIRCUIT) Let G be a biconnected graph and suppose that G has

an odd-length circuit. Show that every vertex of G belongs to an odd-length
circuit.
Characterization of cuts
E 4.20 Characterize the sets of edges of a graph that are cuts, i.e., give condi-
tions under which a set of edges of a graph is a cut.
E 4.21 (A LGORITHM) Sketch an efficient algorithm for the following task:

Given a graph G and a subset C of EG , the algorithm must decide whether
C is a cut. In the “yes” case, the algorithm should return a set X of vertices
such that ∂(X) = C. What should your algorithm return in the “no” case?
E 4.22 Let D be a cut and O a circuit in a graph. Show that |D ∩ EO | is even.
E 4.23 (Converse of 4.22.) Let D be a set of edges of a graph G. Suppose

|D ∩ EO | is even for every circuit O in G. Show that D is a cut.
E 4.24 Let D be a cut and P a path in a graph G. What can you say about the
parity of |D ∩ EP |?
E 4.25 A signed graph is a triple (G, P, N ) in which G is a graph and (P, N ) is a

partition of the set EG . The edges in P are positive and the others are negative.
A signed graph (G, P, N ) is balanced if every circuit in G has an even number
of negative edges. Prove that a signed graph (G, P, N ) is balanced if and only
if there is a bipartition {U, W } of VG such that ∂(U ) = N .
Chapter 5
Stable sets
A set X of vertices of a graph is stable, or independent, if its elements are

pairwise non-adjacent. In other words, X is stable if no edge of the graph has
both endpoints in X, i.e., if the induced graph G[X] is empty. For example, if
{U, W } is a bicoloring of the graph, then sets U and W are stable.
A stable set X ∗ is maximum if there is not stable set X such that maximum
|X| > |X ∗ |. In other words, X ∗ is maximum if |X ∗ | ≥ |X| for every stable
set X.
M AXIMUM S TABLE S ET P ROBLEM: Find a maximum stable set in a

given graph.
It is important not to confuse maximum and maximal. A stable set X 0 is

maximal if it is not part of a bigger stable set, i.e., if there is no stable set X maximal
such that X ⊃ X 0 .1
A variant of the problem is the following: Given a graph and a natural
number k, find a stable set with k or more vertices. (Clearly this variant does
not always have a solution.)
The size of a maximum stable set in a graph G is known as stability
number, or independence number, of G and is denoted by
α(G) .
Exercises
E 5.1 Show that the stability number is invariant under isomorphism. In
other words, if G and H are isomorphic graphs, then α(G) = α(H).
◦ E 5.2 Find a maximum stable set in a Kn . Find a maximum stable set in
1
The expression “A ⊃ B” means “B is a proper subset of A”, i.e., B ⊆ A but B 6= A.
71
FEOFILOFF Stable sets 72
a Kn .
E 5.3 In the graph of figure 5.1, show a maximal stable set which is not
maximum.
Figure 5.1: See exercise 5.3.
◦ E 5.4 Suppose that X and Y are maximal stable sets of a graph. Is it true
that X and Y are disjoint (i.e., that X ∩ Y = ∅)?
◦ E 5.5 Calculate a maximum stable set in a path. Calculate a maximum

stable set in a circuit.
E 5.6 Find a maximum stable set in the p-by-q grid.
E 5.7 Show a maximum stable set in the cube Qk .
E 5.8 Find a maximum stable set in the knight graph.
E 5.9 Find a maximum stable set in the bishop graph.
E 5.10 Find a maximum stable set in the queen graph. (In other words,
arrange the greatest possible number of queens on the board so that they
do not attack each other.)
E 5.11 Find a maximum stable set in the Petersen graph.
E 5.12 Find a maximum stable set in the Kneser graph K(n, k) (see exer-
cise 1.16).
E 5.13 Find a maximum stable set in the graph of Europe (see exercise 1.17).
? E 5.14 Let G be a bicolorable graph with a bicoloring {U, W }, and suppose

that |U | ≥ |W |. Is it true that U is a maximum stable set?
E 5.15 Suppose that a graph G admits a bicoloring. Is it true that every

maximal stable set of G is maximum? What if G is a tree?
◦ E 5.16 Let H be a subgraph of a graph G. What is the relationship between

α(H) and α(G)?
◦ E 5.17 Let G and H be two graphs such that VG ∩ VH = ∅. Show that

α(G ∪ H) = α(G) + α(H).
◦ E 5.18 Let A be the adjacency matrix of a graph G (see exercise 1.3). Let X
be a stable set of G. What does the restriction of A to X × X look like?
E 5.19 (A LGORITHM) Discuss the following algorithm for the maximum sta-
ble set problem:
given a graph G, examine each of the subsets of VG ;
discard the non-stable subsets;
find a largest among the remaining.
D 5.20 (A LGORITHM) Devise a fast algorithm to solve the maximum stable

set probem. Devise, at least, an algorithm that yields a large stable set.2
◦ E 5.21 (A LGORITHM) Devise an algorithm that finds a maximal stable set

in any given graph. (Hint: use a “greedy” strategy: in each iteration, pick
any reasonable vertex.3 )
E 5.22 (A LGORITHM) The following greedy algorithm receives a graph G

and returns a stable set X:
X←∅
H←G
while VH 6= ∅ do
pick v in VH such that |NH (v)| is minimum
X ← X ∪ {v}
Z ← {v} ∪ NH (v)
H ←H −Z
return X
Is it true that this algorithm returns a maximum stable set for any given
graph G? What if G is bipartite? What if G is a tree?
E 5.23 ♥ Prove that every maximal stable set of any graph G has at least
l n(G) m
∆(G) + 1
2
A fast algorithm to find a maximum stable set in any graph is not (yet?) known. In
technical terms, this problem is NP-hard. See observation in page 5.
3
Greedy algorithms grab the object that seems best in the current iteration, without
regard for the consequences of this choice in the long term.
n(G)
vertices.4 From this, deduce that α(G) ≥ ∆(G)+1
for every graph G.
E 5.24 ♥ Prove that every graph G satisfies the inequality

X 1
α(G) ≥ .
v∈VG
d(v) + 1
1
P
I.e., prove that G has a stable set with d(v)+1
vertices.
E 5.25 Let Gt be the t-by-t queen graph. Use exercise 5.24 to estimate α(Gt ).
E 5.26 Let X be P
the stable set produced by the algorithm in exercise 5.22.
Show that |X| ≥ v∈VG 1/(d(v) + 1).
E 5.27 Prove that every graph G satisfies the inequality

n
α(G) ≥ ,
µ+1
where n is the number of vertices, m is the number of edges, and µ is the
average degree of the vertices of G.
E 5.28 Let us say that a path cover of a graph G is a collection {P1 , . . . , Pk } of

paths in G such that VP1 ∪ · · · ∪ VPk = VG . Suppose that every path cover of
a graph G has at least k paths. Show that α(G) ≥ k. In other words, show
that G has a stable set with at least k vertices.
E 5.29 (A LGORITHM) Sketch an efficient algorithm that receives a bipartite

graph and returns a maximum stable set.5
α≤ E 5.30 Let G be a graph without isolated vertices. Show that

α(G) ≤ m(G)/δ(G) .
In other words, show that G has no stable set with more than bm(G)/δ(G)c
vertices.6
E 5.31 Let n and a be two positive integers. Let k = bn/ac and r = n − ka.
Let H be the graph resulting from the union of r copies of Kk+1 and a − r
copies of Kk (the vertex sets of the copies are pairwise disjoint). Observe that
n(H) = n, m(H) = r k+1 + (a − r) k2 and α(H) = a .

2
4
By definition, dxe is the only integer number j such that j − 1 < x ≤ j.
5
We will discuss this algorithm in detail in chapter 10.
6
By definition, bxc is the only integer i such that i ≤ x < i + 1.
Show that α(G) > α(H) for any graph G such that n(G) = n and m(G) <
m(H).7
Random graphs
E 5.32 Show that the stability number of most graphs is not much more than
2 log2 n(G). More precisely, show that, for any positive real number ε, one has
α(G) < (2 + ε) log2 n
for almost every graph G in G(n). (See section 1.18.)
7
It can be shown that H is the only graph (up to isomorphism) with n vertices, m(H)
edges and stability number a. This fact is a known theorem by Paul Turán ( − ).
(See article on Wikipedia.) The complement of H is known as the Turán graph.
Chapter 6
Cliques
A clique in a graph is any set of pairwise adjacent vertices. In other words,

X is a clique if the induced graph G[X] is complete.
M AXIMUM C LIQUE P ROBLEM: Find a maximum clique in a given

graph.
Here is a variant of the problem: given a graph and a natural number k,

find a clique with k or more vertices.
The size of a maximum clique of a graph G is known as the clique
number of G and denoted by
ω(G) .
Exercises
◦ E 6.1 Find a maximum clique in a Kn . Find a maximum clique in a Kn .
◦ E 6.2 Find a maximum clique in a path. Find a maximum clique in a circuit.
E 6.3 Let G be a circuit of length 6. Find a maximum clique in G.
E 6.4 Show a graph and a clique that is maximal but not maximum.
E 6.5 Find a maximum clique in the knight graph.
E 6.6 Show a maximum clique in the cube Qk .
◦ E 6.7 Suppose that G is a bipartite graph. How many vertices does a

maximum clique in G have?
77
FEOFILOFF Cliques 78
E 6.8 Find a maximum clique in the bishop graph.
E 6.9 Find a maximum clique in the queen graph.
E 6.10 Show that every maximal clique of the Kneser graph K(n, k) (see
exercise 1.16) has bn/kc vertices. Show a maximum clique in K(n, k).
E 6.11 What is the relationship between the maximum clique problem and
the maximum stable set problem (see chapter 5)? How is it possible to use an
algorithm that solves one of these problems to solve the other?
◦ E 6.12 Prove that ω(G) ≤ ∆(G) + 1 for every graph G.
E 6.13 Show that the following relation is valid for any set X of vertices of a
graph G: X is a clique in G if and only if X is a stable set in G. Deduce that
ω(G) = α(G).
E 6.14 Suppose that a graph G has the following property: for each vertex v,
the set N(v) is a clique. Show that each component of G is a clique.
E 6.15 Show that ω(G) ≥ 3 for every graph G with more than n(G)2 /4 edges.
(See exercise 4.12.)
E 6.16 Suppose that ω(G) ≤ k. What is the maximum number of edges (in
relation to the number of vertices) that G can have?
E 6.17 Is it true that every maximal clique in a tree is maximum?
◦ E 6.18 (A LGORITHM) Devise an algorithm that finds a maximal clique in

any given graph.
D 6.19 (A LGORITHM) Devise a fast algorithm to solve the maximum clique

problem. Devise, at least, an algorithm to find a large clique in any given
graph.1
E 6.20 Let L(G) be the line graph (see exercise 1.24) of a graph G. Show that,
for each vertex v of G, the set ∂G (v) is a clique in L(G). Show that the edge set
of any triangle in G is a clique in L(G). Show that any clique in L(G) whose
size is not 3 is a subset of some set of the form ∂G (v).
1
A fast algorithm for the maximum clique problem is not (yet?) known. In technical
terms, this problem is NP-hard. See observation in page 5.
E 6.21 Given a graph G, compute a maximum clique in the line graph L(G).
E 6.22 Show that a graph H is isomorphic to the line graph (see exercise 1.24)
of some other graph G if and only if there is a collection of cliques of H such
that each edge of H has both endpoints in one and only one of the cliques,
and every vertex of H belongs to at most two of the cliques.
E 6.23 Let G be a planar graph (see section 1.6). Show that ω(G) ≤ 4.
Chapter 7
Vertex covers
A vertex cover1 , or simply cover, of a graph is any set of vertices that contains
at least one of the endpoints of each edge. In other words, a set X of vertices
is a cover if every edge has at least one of its endpoints in X.
M INIMUM C OVER P ROBLEM: Find a minimum cover in a given graph.
The cardinality of a minimum cover of a graph G is denoted by β(G).

There a simple and intimate relation between vertex covers and stable
sets (see exercise 7.6). This relation makes the minimum cover problem
equivalent to the maximum stable set problem.
Exercises
E 7.1 An art gallery consists of a large number of straight corridors that
interconnect small halls. A guard standing in a hall can watch over all the
corridors that radiate from the hall. What is the smallest number of guards
needed to watch over the whole gallery?
E 7.2 Find a minimum cover in the knight graph. Find a minimum cover in
the bishop graph.
E 7.3 Find a minimum cover in the cube Qk .
◦ E 7.4 Show that a graph G is bicolorable if and only if VG has a subset U

which is, at the same time, an independent set and a cover.
◦ E 7.5 What is a minimal cover? Use the graph in figure 5.1 to give an
1
Maybe it would be better to say “cover of edges by vertices.”
81
FEOFILOFF Vertex covers 82
example of a minimal cover. Is it true that every minimum cover is minimal?

Is it true that every minimal cover is minimum?
? E 7.6 Prove the following relationship between covers and stable sets: in
any graph G, a set X of vertices is a cover if and only if VG r X is stable.
Deduce that β(G) = n(G) − α(G).
E 7.7 Show that the minimum cover problem is equivalent to the maximum
stable set problem. (In other words, show that any algorithm for one of the
problems can be converted into an algorithm for the other.)
E 7.8 Suppose that T is a tree. Is it true that every minimal cover of T is

minimum?
◦ E 7.9 Let {U, W } be a bicoloring of a graph G. Let {X, X 0 } be a partition

of U and {Y, Y 0 } be a partition of W . Suppose that N(X) ⊆ Y . (See the
definition of N(X) in exercise 1.108.) Show that Y ∪ X 0 is a cover.
?◦ E 7.10 (A PPROXIMATED SOLUTION ) Specify an algorithm that will give

an approximate solution to the minimum cover problem: given a graph G,
the algorithm must return a cover X such that |X| ≤ 2β(G).
E 7.11 Consider the equivalence discussed in exercise 7.7, and the approx-
imate solution discussed in exercise 7.10. Is it possible to obtain a similar
approximation for the maximum stable set problem (see chapter 5)?
Chapter 8
Vertex coloring
A vertex coloring, or a covering by stable sets, of a graph is a collection of

stable sets that covers the set of vertices of the graph. More precisely, a vertex
coloring of a graph G is a collection {X1 , X2 , . . . , Xk } of stable sets such that
X1 ∪ X2 ∪ · · · ∪ Xk = V G .
Although not essential, it is convenient to assume that sets X1 , . . . , Xk are
pairwise disjoint. We can thus say that a vertex coloring of G is a partition of
VG into stable sets. Each vertex of the graph will be in one and only one of
those sets. (Clearly the concept of vertex coloring is a generalization of the
concept of bicoloring, discussed in chapter 4.)
If we imagine that each stable set Xi corresponds to a color, we can say
that a vertex coloring is an assignment of colors to the vertices such that
adjacent vertices get different colors.
We say that a coloring {X1 , X2 , . . . , Xk } uses k colors.1 We also say that
this is a k-coloring. If a graph has a k-coloring, then it also has a k 0 -coloring
for all k 0 > k.
A vertex coloring is minimum if it uses the smallest possible number of
colors, i.e., if no other coloring uses fewer colors.
V ERTEX C OLORING P ROBLEM: Find a minimum vertex coloring of a

given graph.
The chromatic number of a graph G is the number of colors in a mini-

mum vertex coloring of G. This number is denoted by
χ(G) .
A graph G is k-colorable if χ(G) ≤ k. In particular, “2-colorable” is the same

as “bicolorable”, according to chapter 4.
1
Even if some Xi is empty.
83
FEOFILOFF Vertex coloring 84
See the WWW site Graph Coloring Page by Joseph Culberson at the Uni-
versity of Alberta, Canada.
A clique cover of G is any partition {X1 , . . . , Xk } of VG such that each Xi

is a clique. Clearly a clique cover of G is the same as a vertex cover of G.
The corresponding CLIQUE COVER PROBLEM consists of finding the smallest
clique cover of VG .
Exercises
E 8.1 A factory must store a set of chemicals. For safety reasons, certain pairs
of chemicals should be kept in separate compartments of the warehouse.
How many compartments, at least, should the warehouse have?
◦ E 8.2 Show that the chromatic number is invariant under isomorphism. In

other words, if G and H are isomorphic graphs, then χ(G) = χ(H).
◦ E 8.3 Let {X1 , . . . , Xk } be a vertex coloring of a graph G. Show that there is

a coloring {Y1 , . . . , Yk } such that sets Y1 , . . . , Yk are pairwise disjoint.
◦ E 8.4 Find a minimum vertex coloring of a path. Repeat with a circuit in

place of the path. Repeat with a grid in place of the path.
E 8.5 Let Rt be the t-by-t rook graph. Find a minimum vertex coloring of Rt .
E 8.6 Let Bt be the t-by-t bishop graph. Find a minimum vertex coloring
of Bt .
E 8.7 Let Bt be the t-by-t bishop graph. Find a minimum clique cover of the
graph Bt .
E 8.8 Let Kt be the t-by-t knight graph. Find a minimum vertex coloring
of Kt . Find a minimum clique cover of Kt . (Start with the cases t = 2, . . . , 6.)
E 8.9 Let Qt be the t-by-t queen graph. Find a minimum vertex coloring
of Qt . (Consider first the cases t = 2, . . . , 6.)
E 8.10 Let Kt be the t-by-t king graph. Find a minimum vertex coloring of Kt .
E 8.11 Find a minimum vertex coloring of the graph of Europe (see exer-
cise 1.17).
E 8.12 Find a minimum vertex coloring of the cube Qk . Find a minimum

clique cover of the cube Qk .
E 8.13 Find a minimum vertex coloring of the Petersen graph.
E 8.14 Find a minimum vertex coloring of the graph G defined in the follow-
ing manner: begin with five mutually disjoint copies, say B1 , . . . , B5 , of a
complete graph on 3 vertices; for each i, add edges connecting all vertices of
Bi to all vertices of Bi+1 ; finally, add edges connecting all vertices of B5 to
all vertices of B1 . (This graph was used by Catlin2 as a counterexample for
Hajós’ conjecture. See exercise 8.71.)
E 8.15 We are given machines 1, . . . , n and time intervals I1 , . . . , In . For each i,

a worker must operate machine i during the interval Ii . If Ii ∩ Ij 6= ∅, the
same worker cannot operate both i and j. How many workers are necessary
and suficient to operate all the machines? (See exercise 1.22.)
◦ E 8.16 Show a graph with two different minimum vertex colorings.
◦ E 8.17 Suppose that a graph G has a vertex coloring with k colors. Is it true
that G has a coloring {X1 , . . . , Xk } such that X1 is a maximum independent
set?
◦ E 8.18 Let G be a graph with at least one edge. Prove that there is a partition
{A, B} of VG such that χ(G[A]) + χ(G[B]) = χ(G).
◦ E 8.19 Let G and H be two graphs such that VG ∩ VH = ∅. Show that

χ(G ∪ H) = max{χ(G), χ(H)}.
◦ E 8.20 Let H be a subgraph of a graph G. What is the relationship between

χ(H) and χ(G)?
E 8.21 Let e be a bridge of a graph G with two or more edges. Show that
χ(G − e) = χ(G).
E 8.22 Let v be an articulation of a graph G. Is it true that χ(G) = χ(G − v)?
E 8.23 Let v be a vertex of a graph G. Suppose that d(v) < χ(G) − 1. Show
that χ(G) = χ(G − v).
E 8.24 Show that, for every graph G, every vertex coloring of G uses at least
dn(G)/α(G)e colors. In other words, show that χ(G) ≥ n(G)/α(G). χ≥
E 8.25 (G ENERALIZATION OF 8.24) For each vertex v of a graph G, let αv be

the cardinality
P of a maximum stable set among those that contain v. Show
χ≥ that χ(G) ≥ v 1/αv .
E 8.26 Show that every graph with n vertices and chromatic number k has at
χ≥ most 21 (n2 −n2 /k) edges. Deduce that χ(G) ≥ n2 /(n2 −2m) for every graph G
with n vertices and m edges.3 Deduce that χ(G) ≥ n/(n − r) if G is r-regular.4
q
1 1
E 8.27 Show that χ(G) ≤ 2
+ 2m(G) + 4
for every graph G.
E 8.28 (A LGORITHM) Does the following algorithm solve the vertex color-
ing problem? For an input graph G, the algorithm does the following:
Picks a maximum stable set, say X1 , in G. Then, picks a maximum stable
set X2 in G − X1 . Then, picks a maximum stable set X3 in (G − X1 ) − X2 .
And so on, until there are no more vertices to pick.
E 8.29 (A LGORITHM) The following greedy algorithm receives a graph G

and returns a vertex coloring X1 , . . . , Xk . Each iteration begins with a
collection X1 , . . . , Xk of stable sets; the first iteration may begin with the
empty collection, i.e., with k = 0. Each iteration consists of the following:
C ASE 1: X1 ∪ . . . ∪ Xk = VG .
Return X1 , . . . , Xk and stop.
C ASE 2: X1 ∪ . . . ∪ Xk 6= VG .
Pick a vertex v in VG r (X1 ∪ . . . ∪ Xk ).
If Xi ∪ {v} is stable for some i between 1 and k,
then start a new iteration with Xi ∪ {v} replacing Xi .
Otherwise, make Xk+1 = {v} and
start a new iteration with k + 1 replacing k.
Does this algorithm solve the vertex coloring problem?
E 8.30 ♥ Prove that every graph G has a vertex coloring with only ∆(G) + 1
colors. In other words, prove that χ(G) ≤ ∆(G) + 1 for every graph G.
◦ E 8.31 Is it true that χ(G) ≥ ∆(G) for every graph G? In other words, is it
true that every vertex coloring of G uses at least ∆(G) colors?
2
P. A. Catlin, 1979.
3
Some examples: if m > 0 thenχ > 1; if m > n2 /4 then χ > 2; if m > 4n2 /9 then χ > 9.
4
Examples: if r > 0 then χ > 0; if r > n/2 then χ > 2; if r > 2n/3 then χ > 3.
E 8.32 Prove that every graph G admits a clique cover of size at most n(G) −
δ(G). In other words, show that χ(G) ≤ n(G) − δ(G).
E 8.33 ♥ Let G be a non-regular connected graph. Show that χ(G) ≤ ∆(G).

E 8.34 (B ROOKS ’ T HEOREM5 ) Let G be a connected graph which is not com-

plete and different from an odd circuit. Show that χ(G) ≤ ∆(G). (Compare
to exercise 8.33.)
E 8.35 Show that the difference ∆(G) − χ(G) may be arbitrarily large. Show
that the quotient ∆(G)/χ(G) may be arbitrarily large. (Compare to exer-
cise 8.30.)
E 8.36 (G ENERALIZATION OF 8.30) Let v1 , v2 , . . . , vn be the vertices of a

graph G and suppose that d(v1 ) ≥ d(v2 ) ≥ · · · ≥ d(vn ). Show that
χ(G) ≤ maxni=1 min{i, d(vi ) + 1}. (Hint: the right side of the inequality is
equal to max { i : d(vi ) + 1 ≥ i }.)
E 8.37 Let G be a graph with the following property: every pair of odd
circuits has (at least) one vertex in common. Prove that G has a 5-coloring.
? E 8.38 Suppose a graph G has a clique with k vertices. Show that every
vertex coloring of G uses at least k colors. In other words, show that χ≥
χ(G) ≥ ω(G)
for every graph G. (See exercises 6.8 and 6.9.)
E 8.39 Suppose a graph G has a clique with k vertices and a vertex coloring
that uses k colors. Prove that the clique is maximum and that the coloring is
minimum.6
E 8.40 Prove that χ(G) = ω(G) for every bipartite graph G.
? E 8.41 (A LGORITHM7 ) Let v1 , v2 , . . . , vn be the vertices of a graph G. Sup-

pose that, for i = 2, . . . , n, the set
{v1 , . . . , vi−1 } ∩ N(vi )

5
Published by R. L. Brooks in 1941.
6
Such a clique can be used as a minimality certificate for the coloring. Conversely, such
coloring can be used as a maximality certificate for the clique.
7
Perfect Elimination Scheme.
is a clique. Show that χ(G) = ω(G). (Hint: Write an algorithm to calculate a

minimum vertex coloring and a maximum clique.)
E 8.42 Show that, for every k, there is a graph without cliques of size k that
does not admit a coloring with k (or less) colors. In other words, show that
there are graphs G such that χ(G) > ω(G). Show that for every k there is a
graph G such that χ(G) = k and ω(G) = 2.
E 8.43 Suppose a graph G has a stable set with k vertices. Show that every
clique cover of VG uses at least k cliques. Deduce that χ(G) ≥ α(G).
E 8.44 Suppose a graph G has no induced subgraph isomorphic to a path on

4 vertices. Show that χ(G) = ω(G).
E 8.45 Suppose a graph G has no induced subgraph isomorphic to either K1,3

or K4 − e. Show that χ(G) ≤ ω(G) + 1.
E 8.46 Let G be a graph (not necessarily bicolorable), and let {R, S} be a

partition of VG . Suppose that d(R) < k (i.e., there are less than k edges
with an endpoint in R and another in S). Suppose also that graphs G[R]
and G[S] admit vertex colorings with only k colors. Show that G admits a
vertex coloring with k colors.
E 8.47 Let P be a maximum-length path in a graph G. Show that χ(G) ≤

n(P ). (In other words, if a graph has no path with more than k vertices, then
it can be colored with only k colors.)
E 8.48 (G ALLAI –R OY T HEOREM8 ) For any acyclic orientation9 D of a

graph G, let l(D) be the length of a maximum directed path10 in D. Then
χ(G) = 1 + min l(D) .

D
D 8.49 (A LGORITHM) Devise a fast algorithm to solve the vertex coloring

problem.11
8
Published in 1966 by Tibor Gallai and in 1967, independently, by Bernard Roy.
9
An orientation of a graph consists of the substitution of each edge vw by the ordered
pair (v, w) or by the ordered pair (w, v). Such ordered pair is called an arc. The result is
a directed graph. A directed graph D is acyclic if it has no directed circuits. A circuit is
directed if all its arcs are oriented in the same direction.
10
A path is directed if all its arcs are oriented in the same direction.
11
A fast algorithm for the problem is not (yet?) known. In technical terms, this problem
is NP-hard. See observation in page 5.
Coloring with a given number of colors

If the number of available colors is fixed, we have the following variant of
the coloring problem:
C OLORING P ROBLEM WITH G IVEN N UMBER OF C OLORS: Given a
natural number k and a graph G, find a k-coloring of G.
(Clearly, the problem does not always have a solution.) The 2-coloring prob-
lem, for example, is equivalent to the problem of deciding whether a given
graph is bicolorable (see exercise 4.15).
E 8.50 The following algorithm receives a graph G and promises to return a

bicoloring of G. Each iteration begins with a pair (X1 , X2 ) of stable sets; the
first iteration may begin with X1 = X2 = ∅. Each iteration consists of the
following:
C ASE 1: X1 ∪ X2 = VG .
Return X1 , X2 and stop.
C ASE 2: X1 ∪ X2 6= VG .
Pick a vertex v in VG r (X1 ∪ X2 ).
Pick i in {1, 2} such that Xi ∪ {v} is stable.
Start a new iteration with Xi ∪ {v} in the role of Xi .
Does this algorithm deliver on its promise (i.e., does it produce a 2-coloring
of the graph)?
E 8.51 The following greedy algorithm receives a graph G and promises to

return a 3-coloring of G. Each iteration begins with stable sets X1 , X2 and X3 ;
the first iteration may begin with X1 = X2 = X3 = ∅. Each iteration consists
of the following:
C ASE 1: X1 ∪ X2 ∪ X3 = VG .
Return X1 , X2 , X3 and stop.
C ASE 2: X1 ∪ X2 ∪ X3 6= VG .
Pick a vertex v in VG r (X1 ∪ X2 ∪ X3 ).
Pick i in {1, 2, 3} such that Xi ∪ {v} is stable.
Start a new iteration with Xi ∪ {v} in place of Xi .
Does the algorithm deliver on its promise?
E 8.52 The following greedy algorithm receives a graph G and promises to

return a 3-coloring of G:
W ← VG
while W 6= ∅ do
pick w in W
i←1
while N(w) ∩ Xi 6= ∅ do i ← i + 1
Xi ← Xi ∪ {w}
W ← W r Xi
return X1 , X2 , X3
Does the algorithm keep its promise?
E 8.53 What is the maximum number of edges in a graph with n vertices that
admits a 3-coloring?
E 8.54 Imagine a grid in which all the vertices except for one are colored.
Each colored vertex has one of 3 possible colors. Devise a “color swapping
heuristic in bicolored components” (compare to exercise 12.22) to obtain,
from the given partial coloring, a coloring of all the vertices with only 3
colors.
E 8.55 Let I and J be stable sets in a graph G and suppose I ∩ J = ∅. Let X

be the set of vertices in one component of the bipartite graph G[I ∪ J]. Show
that the set I ⊕ X is stable in graph G.
E 8.56 (A LGORITHM) Describe an heuristic12 for vertex coloring based on

exercise 8.55. (At the beginning of each iteration, we have a partial vertex
coloring; each iteration picks a uncolored vertex and tries to assign to it one
of the previously used colors.)
D 8.57 As we know, 2-colorable graphs are characterized by the absence of

odd circuits. Devise a good characterization of 3-colorable graphs. Devise a
good characterization of k-colorable graphs.
D 8.58 (A LGORITHM) Devise a fast algorithm to solve the 3-coloring prob-

lem.13
D 8.59 (A LGORITHM) Let k be a natural number greater than 3. Devise a

fast algorithm to solve the k-coloring problem.
Coloring planar graphs

Planar graphs can be colored with few colors.
12
According to Wilf (in Algorithms and Complexity, Prentice-Hall, 1986), heuristics are
“methods that seem to work well in practice, for reasons nobody understands.”
13
A fast algorithm to decide whether a given graph is 3-colorable is not (yet?) known. In
technical terms, this decision problem is NP-complete. See observation in page 5.
E 8.60 Show that χ(G) ≤ 6 for every planar graph G. (See exercises 1.275
and 8.30.)
E 8.61 (H EAWOOD ’ S T HEOREM14 ) Show that χ(G) ≤ 5 for every planar

graph G. (See exercises 1.275, 8.54 and 8.56.)
E 8.62 (A LGORITHM) Devise an algorithm that produces a 5-coloring of any

given planar graph.
!! E 8.63 (F OUR C OLOR T HEOREM15 ) Show that every planar graph admits
a vertex coloring with 4 or less colors. In other words, show that
χ(G) ≤ 4
for every planar graph G.
◦ E 8.64 Show that there are planar graphs that do not admit a vertex color-
ing with only 3 colors.
E 8.65 Is it true that χ(G) = ω(G) for every planar graph G? (See exer-
cises 8.38 and 8.39.)
E 8.66 Let G be the graph of Europe (see exercise 1.17). Show that χ(G) = 4.
!! E 8.67 (A LGORITHM) Devise an algorithm to produce a 4-coloring of any

given planar graph.
E 8.68 Show that α(G) ≥ 41 n(G) for every planar graph G. (It would be
very interesting to have a proof of this fact that did not rely on the four color
theorem, exercise 8.63.)
E 8.69 A face coloring of a plane map is an assignment of colors to the faces

of the map (see subsection 1.17) such that adjacent faces receive different
colors.
Deduce from the Four Color Theorem (exercise 8.63) that the faces of any
planar map whose graph is edge-biconnected can be colored with 4 or less
colors.
E 8.70 Show that the set of faces of every outerplanar graph (see exer-
cise 1.283) is 3-colorable.
14
Percy John Heawood ( − ).
15
Proved in 1976 by Kenneth Appel and Wolfgang Haken. Proof simplified in 1997 by
Neil Robertson, Daniel P. Sanders, Paul D. Seymour and Robin Thomas. See the pages “The
four color theorem”, “Four-Color Theorem” and “Four-Color Theorem.”
Coloring versus minors

Before going into this section, study chapter 19 (Planarity).
! E 8.71 Prove that the following conjecture by Hajós16 is false: For every
graph G, if χ(G) ≥ k, then G has a topological minor (see section 1.16)
isomorphic to Kk .
E 8.72 Let G be a graph such that χ(G) ≥ 3. Show that G has a minor (see
section 1.16) isomorphic to K3 . (Compare to exercise 8.38.)
E 8.73 Let G be a graph such that χ(G) ≥ 4. Show that G has a minor
isomorphic to K4 .
!! E 8.74 Let G be a graph such that χ(G) ≥ 5. Show that G has a minor iso-
morphic to K5 . (This is equivalent to the Four Color theorem, exercise 8.63.)
D 8.75 (H ADWIGER C ONJECTURE17 ) For every natural number k ≥ 2 and

every graph G, if χ(G) ≥ k then G has a minor isomorphic to Kk . (This is a
profound generalization of the Four Color theorem, exercise 8.63.)
Coloring random graphs

E 8.76 Let ε be a positive real number. Show that
1 n
χ(G) >
2 + ε log2 n
for almost every graph G in G(n). (See section 1.18.)
! E 8.77 Let ε be a positive real number smaller than 2. Show that
1 n
χ(G) <
2 − ε log2 n
for almost every graph G in G(n). (Compare to exercise 8.76.)

16
The conjecture was proposed by G. Hajós, in 1961.
17
The conjecture was proposed by H. Hadwiger, in 1943.
Perfect graphs
A graph is perfect if χ(G[X]) = ω(G[X]) for every subset X of VG . (See
exercise 8.38.)
E 8.78 Show a non-perfect graph G such that χ(G) = ω(G).
E 8.79 Show that every bicolorable graph is perfect.
! E 8.80 (L OVÁSZ ’ S T HEOREM18 ) Show that the complement of every perfect

graph is perfect.
!! E 8.81 (S TRONG P ERFECT G RAPH T HEOREM) An odd hole is an induced

circuit with an odd ≥ 5 number of vertices.
Prove that a graph G is perfect if and only if neither G nor G contains an
odd hole.19 (This characterization of perfect graphs had been conjectured by
Claude Berge in 1960.)
18
Published by Lásló Lovász in 1972.
19
This theorem was proved in 2002 by Maria Chudnovsky and Paul D. Seymour, based
on previous work by Neil Robertson and Robin Thomas.
Chapter 9
Matchings
Two edges of a graph are adjacent if they have a common endpoint. A

matching is a set of pairwise non-adjacent edges. In other words, a matching
in a graph is a set M of edges such that |M ∩ ∂(v)| ≤ 1 for each vertex v.
M AXIMUM M ATCHING P ROBLEM: Find a maximum matching in a

given graph.
A matching M ∗ is maximum if there is no matching M such that

|M | > |M ∗ |. The cardinality of a maximum matching in a graph G is denoted
by
α 0 (G) .
By the way, a matching M 0 is maximal if it is not part of a larger matching,
i.e., if there is no matching M such that M ⊃ M 0 .
The matching problem is a particular case of the stable set problem (see
exercise 9.15). Although we do not know how to solve the latter in an efficient
way, we know how to solve the former.
A matching M is perfect if each vertex of the graph is the endpoint of
some element of M . The following is an interesting specialization of the
problem above: Find a perfect matching in a given graph. It is clear that
not every graph has a perfect matching; the difficulty of the problem is to
decide whether the given graph has such a matching.
The following concepts are important when studying matchings:
1. A matching M saturates a vertex v if ∂(v) ∩ M 6= ∅, i.e., if some edge
of M is incident to v.
2. A matching M saturates a set X of vertices if M saturates each vertex
in X.
3. A path is alternating with regard to a matching M if its edges are
alternately in M and not in M . Sometimes it is more convenient to
say “M -alternating” than “alternating with regard to M ”.
95
FEOFILOFF Matchings 96
4. An augmenting path for a matching M is an M -alternating path of

non-null length whose endpoints are not saturated by M .
Exercises
◦ E 9.1 Let M be a set of edges of a graph G. Let H be the graph (VG , M ).
Show that M is a matching in G if and only if dH (v) ≤ 1 for every vertex v
of H.
◦ E 9.2 How many edges does a maximum matching in a complete graph

with n vertices have?
◦ E 9.3 How many edges does a maximum matching in a complete bipartite

graph have?
◦ E 9.4 Calculate a maximum matching in a path. Calculate a maximum

matching in a circuit.
◦ E 9.5 Suppose that a graph G has a perfect matching. Show that n(G) is
even.
E 9.6 Let G be a K6 and M be a perfect matching in G. Show that G − M

is planar. Show that G − M has a perfect matching, say M 0 . Show that the
complement of (G − M ) − M 0 is a circuit of length 6.
E 9.7 Calculate a maximum matching in a cubic graph which has a Hamilto-

nian circuit (see chapter 17).
◦ E 9.8 Is it true that every regular graph has a perfect matching?
◦ E 9.9 Find a maximum matching in the t-by-t queen graph.
E 9.10 Find a maximum matching in the t-by-t bishop graph.
E 9.11 Find a maximum matching in the t-by-t knight graph.
E 9.12 How many edges does a maximum matching in the cube Qk have?
E 9.13 Show a graph G and a matching in G which is maximal but not

maximum.
E 9.14 Is it true that, in any tree, every maximal matching is maximum?
E 9.15 Show that the maximum matching problem is a special case of the
maximum stable set problem.
E 9.16 Is it true that, in any graph, every non-isolated vertex is saturated by

some maximum matching? Is it true that every edge belongs to some perfect
matching?
. E 9.17 ♥ Let M and M 0 be two matchings in a graph G. Describe the

graph (VG , M ∪ M 0 ). Describe the graph (VG , M ⊕ M 0 ).1 What happens if M ⊕ M 0
matchings M and M 0 are perfect?
E 9.18 Suppose that a graph has a bridge a. Show that either every perfect
matching contains a, or no perfect matching contains a.
E 9.19 Prove that every forest has at most one perfect matching.
◦ E 9.20 Let M be a matching in a graph, and let P be an M -alternating path.

Show that every path in P is also M -alternating.
E 9.21 Let M be a matching in a graph, and let P be a maximal M -alternating

path. Suppose that the two extreme edges of P are not in M . Is it true that P
is an augmenting path?
? E 9.22 (A UGMENTING PATH) Suppose that P is an augmenting path for a

matching M . Prove that
M ⊕ EP
is a matching. Prove that |M ⊕ EP | > |M |.
? E 9.23 Let M be a matching in a graph G. Suppose that M is not maximum.

Prove that there is an augmenting path for M .
? E 9.24 (B ERGE ’ S T HEOREM2 ) Prove that a matching M is maximum if and

only if there is no augmenting path for M . (Follows from exercises 9.22
and 9.23.)
1
For any sets A and B, we denote by A ⊕ B the set (A r B) ∪ (B r A). It is easy to check
that A ⊕ B = (A ∪ B) r (A ∩ B).
2
Published in 1957 by Claude Berge ( − ).
! E 9.25 (A LGORITHM) Let M be a matching in a graph G. Let a and b be

two vertices not saturated by M . Write an algorithm to find an alternating
path with origin a and terminus b (or to decide that no such path exists).
E 9.26 ♥ Let M be a matching. Let (v0 , v1 , . . . , vk ) be a walk (see the end of

section 1.9) whose edges are alternately in M and not in M , and suppose
that v0 and vk are not saturated by M . Let A be the edge set of that walk.
Show that the set M ⊕ A may not be a matching. (Compare to exercise 9.22.)
E 9.27 (S LITHER) Two players, say A and B, alternately pick vertices of a

graph G. First, A picks a vertex v0 . Then, B picks a vertex v1 which is adjacent
to v0 . Then, A picks a vertex which is adjacent to v1 , but different from v0 and
from v1 . And so on.
Here is a clearer description of the game: The chosen vertices form a
path v0 v1 v2 · · · vk . If k is odd, A picks a vertex vk+1 different from the others
but adjacent to vk . If k is even, B does an analogous move. The last player
able to move wins the game.
Prove that B has a winning strategy if G has a perfect matching. Prove
that A has a winning strategy otherwise.
E 9.28 Let M be a matching, and X a set of vertices of a graph. Assuming X is

saturated by M , show that X is also saturated by some maximum matching.
(Compare with exercise 9.16.)
E 9.29 Let X and Y be two sets of vertices of a graph G. Suppose that X is

saturated by some matching, and that Y is saturated by some matching (not
necessarily the same).
If y is an element of Y r X, is it true that X ∪ {y} is saturated by some
matching?
If |Y | > |X|, is it true that there is some y in Y r X such that X ∪ {y} is
saturated by some matching?
? E 9.30 (M ATCHINGS VERSUS COVERS )

Show that, in any graph, for any
matching M and any cover K (see chapter 7),
|M | ≤ |K| .
Deduce that, if |M | = |K|, then M is a maximum matching, and K is a

minimum cover.3 Give an example of a graph that does not have a pair
(M, K) such that |M | = |K|. (See also exercise 9.33.)
α0 ≤ ? E 9.31 Show that α 0 (G) ≤ β(G) for every graph G.

3
Thus a cover of the same size of a matching is a maximality certificate of the matching.
◦ E 9.32 Let K be a minimal cover of a graph (see chapter 7). Is it true that
every edge of any matching has only one of its endpoints in K?
E 9.33 Let M be a matching and K be a cover (see chapter 7) such that

|M | = |K|. Show that M saturates K, and that every element of M has only
one endpoint in K. (See exercise 9.30.)
E 9.34 Suppose that M is a maximal matching in a graph. Let V (M ) be the

set of vertices saturated by M . Show that V (M ) is a cover (see chapter 7).
Pick one of the endpoints of each edge in M . Let W be the resulting set.
Is it true that W is a cover?
E 9.35 (A LMOST MAXIMUM MATCHING) Let M be a maximal matching

and M ∗ a maximum matching in a graph. Of course |M | ≤ |M ∗ |. Show
that |M | ≥ 21 |M ∗ |. Is it true that |M | > 21 |M ∗ | for every graph?
E 9.36 Suppose that a graph G has a perfect matching. Show that, for every
vertex v, the graph G − v has exactly one component with an odd number of
vertices.
E 9.37 Let G be a graph with n(G) ≥ 2k and δ(G) ≥ k. Show that G has a
matching with a least k edges.
Chapter 10
Matchings in bipartite graphs
When restricted to bipartite graphs, the maximum matching problem (see

chapter 9) has a very elegant and efficient solution. Two theorems (see
exercises 10.7 and 10.23) sum up the solution:
1. In a bipartite graph, a maximum matching has the same size as a
minimum cover.
2. A graph with a bipartition {U, W } has a matching that saturates U if
and only if |N(Z)| ≥ |Z| for every subset Z of U .
The expression N(Z) denotes the set of all vertices that are not in Z but have N(X)
some neighbor in Z. (See exercise 1.108.)
Exercises
E 10.1 Show a maximum matching in the graph shown on figure 10.1.
Figure 10.1: Find a maximum matching.
E 10.2 Find a maximum matching in the cube Qk .
E 10.3 Find a maximum matching in the graph shown on figure 10.2.
101
FEOFILOFF Matchings in bipartite graphs 102
Figure 10.2: Find a maximum matching.
. E 10.4 (D E C AEN ’ S L EMMA1 ) Let G be a bipartite graph with at least one

edge. Show that some vertex of G is saturated by all maximum matchings.
(Used in the inductive solution of exercise 10.6.)
◦ E 10.5 Is it true that every bipartite graph has an edge that belongs to
all maximum matchings? (Compare to exercise 10.4.) Is it true that every
bipartite graph has an edge that does not belong to any maximum matching?
? E 10.6 Show that every bipartite graph has a matching M and a cover K
such that
|M | = |K| .
(Compare to exercise 9.30. See exercise 10.4.)
Figure 10.3: The gray circles indicate a cover. The gray lines
indicate a matching. (Exercise 10.6.)
? E 10.7 (K ŐNIG –E GERVÁRY ’ S T HEOREM2 ) Let M ∗ be a maximum match-

ing and K∗ a minimum cover in a bicolorable graph. Show that |M ∗ | = |K∗ |.
(Follows from 9.30 and 10.6.)
E 10.8 Show that α 0 (G) = β(G) in every bicolorable graph G.
E 10.9 Find a maximum matching and a minimum cover in the graph shown
on figure 10.1.
E 10.10 Let G be a bicolorable graph. Prove that χ(G) = ω(G).

1
Published in 1988.
2
Published in 1931 by Dénes Kőnig ( − ). The theorem is also attributed to
Eugene Egerváry ( − ).
E 10.11 Give a necessary and sufficient condition for a bipartite graph to

have a matching with k edges.
E 10.12 Let G be a {U, W }-bipartite graph. Suppose that |U | = |W | and

m(G) > (k − 1) |U | for some positive integer k. Prove that G has a matching
of cardinality k.
Algorithms
◦ E 10.13 Let G be a {U, W }-bipartite graph. Let {U 0 , U 00 } be a partition of U ,
and {W 0 , W 00 } be a partition of W . Show that N(U 0 ) ⊆ W 0 if and only if
N(W 00 ) ⊆ U 00 . Show that if N(U 0 ) ⊆ W 0 then W 0 ∪ U 00 is a cover.
For any cover K of G, show that N(U r K) ⊆ W ∩ K and N(W r K) ⊆
U ∩ K.
. E 10.14 Let M be a matching in a {U, W }-bipartite graph G. Let V (M )

be the set of vertices that M saturates. Let X be the vertex set of all M -
alternating paths that have one endpoint in U r V (M ). Prove that
(W ∩ X) ∪ (U r X)
is a cover of G. (Used to solve exercise 10.15.)
. E 10.15 (A LGORITHM) Devise an efficient algorithm that will receive a

{U, W }-bipartite graph and a matching M and return (1) a matching M 0 such
that |M 0 | > |M | or (2) a cover K such that |K| = |M |. (See exercise 10.14.)
? E 10.16 (H UNGARIAN A LGORITHM3 ) Devise an efficient algorithm to re-

ceive a bipartite graph G and return a matching M and a cover K such
that |M | = |K|. (See exercise 10.15.) (This is the algorithmic version of
exercise 10.6.)
E 10.17 (A LGORITHM) Let M be a matching in a {U, W }-bipartite graph G.

Let V (M ) be the set of vertices saturated by M . Let a be a vertex in U rV (M ),
and b be a vertex in W rV (M ). Write an algorithm to find an alternating path
from a to b (or decide that no such path exists).
E 10.18 Use the Hungarian algorithm (exercise 10.16) to prove the Kőnig–
Egerváry theorem (exercise 10.7).
E 10.19 (A LGORITHM) Show how to find a maximum stable set in a bipartite

graph.
3
Reference to the Hungarian mathematicians Kőnig, Egerváry, etc.
Semi-perfect matchings
A matching in a bipartite graph is semi-perfect if it saturates one of the “sides”
of the graph. Clearly, every semi-perfect matching is maximum, but not
every maximum matching is semi-perfect.
P ROBLEM: Given a {U, W }-bipartite graph, find a matching that satu-

rates U .
◦ E 10.20 Let G be a {U, W }-bipartite graph. Let M be a matching that satu-

rates U . Prove that M is a maximum matching. Prove that U is a minimum
cover.
◦ E 10.21 Let G be a {U, W }-bipartite graph. Suppose that |N(Z)| < |Z| for
some subset Z of U . Show that G has no matching that saturates U .
? E 10.22 Let G be a {U, W }-bipartite graph. Suppose that

|N(Z)| ≥ |Z|
for every subset Z of U . Prove that G has a matching that saturates U .
? E 10.23 (H ALL’ S T HEOREM4 ) Show that a {U, W }-bipartite graph has a

matching that saturates U if and only if |N(Z)| ≥ |Z| for every subset Z
of U . (Follows from 10.21 and 10.22.)
◦ E 10.24 Which of the following statements hold for every{U, W }-bipartite

graph G? (1) If G has a matching that saturates U , then |N(Z)| ≥ |Z| for every
subset Z of U . (2) If G has a matching that saturates U , then |N(Z)| ≥ |Z| for
some subset Z of U . (3) If |N(Z)| < |Z| for some subset Z of U , then G does not
have a matching that saturates U . (4) If |N(Z)| ≥ |Z| for every subset Z of U ,
then G has a matching that saturates U . (5) If |N(Z)| < |Z| for every subset
Z of U , then G does not have a matching that saturates U . (6) If |N(Z)| ≥ |Z|
for some subset Z of U , then G has a matching that saturates U .
E 10.25 (A LGORITHM) Devise an efficient algorithm that will receive a bi-

partite graph and its bicoloring {U, W } and return (1) a matching that satu-
rates U or (2) a subset Z of U such that |N(Z)| > |Z|. (This is the algorithmic
version of Hall’s theorem, exercise 10.23.)
4
Published in 1935 by Philip Hall ( − ). (See article in Wikipedia.)
E 10.26 Deduce Kőnig–Egerváry’s theorem (exercise 10.7) from Hall’s theo-

rem (exercise 10.23).
E 10.27 Let M be a set of men, W be a set of women, and k be a positive

integer. Suppose that each man knows at most k women, and each women
knows at least k men. Prove that it is possible for each women to marry a
man she knows.
E 10.28 Let G be a {U, W }-bipartite graph with at least one edge. Suppose
that d(u) ≥ d(w) for every u in U and w in W . Prove that there is a matching
that covers U .
E 10.29 Let G be an r-regular bipartite graph with r > 0. Show that G has a
perfect matching.
E 10.30 Prove that a bicolorable graph G has a perfect matching ifSand only
if |N∗ (Z)| ≥ |Z| for every subset Z of VG , where N∗ (Z) is the set z∈Z N(z).
(Clearly N∗ (Z) contains N(Z).)
Give an example of a (non-bicolorable) graph that does not have a perfect
matching, but satisfies inequality |N∗ (Z)| ≥ |Z| for every set Z of vertices.
E 10.31 Let G be a {U, W }-bipartite graph, and X be a subset of U . Give a

necessary and sufficient condition for G to have a matching that saturates X.
. E 10.32 Let G be a {U, W }-bipartite graph, X be a subset of U , and Y be a

subset of W . Let M be a matching that saturates X, and N be a matching that
saturates Y . Show that there is a matching that saturates X ∪ Y .
E 10.33 Let G be a {U, W }-bipartite graph with at least one edge. Let X be
the set of vertices in U that have degree ∆(G). Show that G has a matching
that saturates X.
. E 10.34 ♥ Let G be a bicolorable graph with at least one edge. Show that
there is a matching that saturates all vertices of degree ∆(G). (See exercises
10.32 and 10.33.)
E 10.35 Let K be a complete {U, W }-bipartite graph with |U | = |W |. Let G

be a subgraph of K and set r = ∆(G). Show that there is an r-regular graph
H such that G ⊆ H ⊆ K.
E 10.36 Let G be a bicolorable graph and set r = ∆(G). Show that G is a

subgraph of some r-regular bicolorable graph.
E 10.37 (G ENERALIZATION OF H ALL’ S THEOREM) Let G be a {U, W }-

bipartite graph. Prove that every maximum matching in G has cardinality
min |U | − |Z| + |N(Z)| .

Z⊆U
E 10.38 Let G be a graph (not necessarily bicolorable), and let {A, B} be a

partition of VG . Suppose that there are less than k edges with one endpoint
in A and another in B (i.e., d(A) < k). Suppose also that graphs G[A] and G[B]
admit vertex colorings (see chapter 8) with k colors. Show that G admits a
vertex coloring with k colors.
Chapter 11
Matchings in arbitrary graphs
A component of a graph is odd if it has an odd number of vertices. The

number of odd components of a graph G will be denoted in this section
by o(G). o(G)
Exercises
E 11.1 Let T be a tree and suppose that o(T − v) = 1 for each vertex v of T .
Show that T has a perfect matching. (See exercise 9.36.)
E 11.2 Suppose that a graph G has a perfect matching. Show that o(G − S) ≤
|S| for every set S of vertices.
◦ E 11.3 Suppose that a graph G satisfies the condition o(G − S) ≤ |S| for
every set S of vertices. Prove that n(G) is even.
?! E 11.4 Suppose that a graph G has the following property: for every set S
of vertices,
o(G − S) ≤ |S| .
Show that G has a perfect matching.
? E 11.5 (T UTTE ’ S T HEOREM1 ) Show that a graph G has a perfect matching

if and only if o(G − S) ≤ |S| for every set S of vertices. (Follows from
exercises 11.2 and 11.4.)
?! E 11.6 (A LGORITHM) Sketch an efficient algorithm to decide whether a

graph has a perfect matching.
1
Published in 1947 by William T. Tutte ( − ). (see article in Wikipedia.)
107
FEOFILOFF Matchings in arbitrary graphs 108
E 11.7 Deduce Hall’s theorem (exercise 10.23) from Tutte’s theorem (exer-
cise 11.4).
? E 11.8 Let M be a matching and S be a set of vertices of a graph G. Prove

that the number of vertices not saturated by M is at least o(G − S) − |S|.
Deduce that
|M | ≤ γ(G, S) ,
γ( ) where γ(G, S) is the number 21 n(G) − 12 o(G − S) − |S| .

E 11.9 Let M be a matching and S be a set of vertices of a graph G. Suppose

that |M | = γ(G, S), where γ(G, S) is the number defined in exercise 11.8.
Show that matching M is maximum.2
?! E 11.10 Show that, in any graph G, there is a matching M and a subset S

of VG such that M saturates all but o(G − S) − |S| vertices, i.e., such that
|M | ≥ γ(G, S) ,
where γ(G, S) is the number defined in exercise 11.8.
?! E 11.11 (T UTTE –B ERGE ’ S T HEOREM3 ) Prove that, in any graph G,

α 0 (G) = γ(G) ,
where γ(G) is the minimum value of γ(G, S) for all subsets S of VG , and
γ(G, S) is the number defined in exercise 11.8. (See exercise 11.10.)
E 11.12 Deduce exercise 9.30 from exercise 11.8. Deduce Kőnig–Egerváry’s

theorem (exercise 10.7) from Tutte–Berge’s theorem (exercise 11.11).
E 11.13 Let G be a cubic bridgeless graph. Show that G has a perfect match-
ing. Show that not every cubic graph has a perfect matching.
?! E 11.14 (G ALLAI –E DMONDS D ECOMPOSITION4 ) Let G be a graph and D

the set of vertices that are not saturated by every maximum matching. (See
exercise 10.4.) Let A be the set N(D). (See the definition of N in exercise 1.108.)
Let C be the set VG r (D ∪ A). Show that, for every maximum matching M ∗
in G, we have that
2|M ∗ | = n(G) − c(G[D]) + |A| ,
where c(H) denotes the number of components of graph H.
2
The set S serves as a maximality certificate of the matching.
3
This is a combination of Tutte’s theorem (exercise 11.4) with a theorem by Claude Berge
( − ) published in 1958.
4
Published in 1963 and 1964 by Tibor Gallai ( − ), and in 1965 by Jack Edmonds.
! E 11.15 (E DMONDS ’ A LGORITHM5 ) Sketch an efficient algorithm to find a

maximum matching in any given graph.
! E 11.16 An edge cover6 of a graph is a set F of edges such that every vertex
of the graph is an endpoint of some element of F . (Do not confuse this
with the concept of vertex cover.) Devise an efficient algorithm to produce a
minimum edge cover.
! E 11.17 (M AXIMUM -W EIGHT M ATCHING A LGORITHM) Let K be a com-

plete graph and π be a function from EK to {0, 1, 2, 3, . . .}. For each edge e of
thePgraph, we say that π(e) is the weight of e. The weight of a subset F of EK
is e∈F π(e). Sketch an algorithm to find a maximum-weight matching in K.
5
Jack Edmonds.
6
Maybe I should say “cover of vertices by edges”.
Chapter 12
Edge coloring
An edge coloring, or covering by matchings, of a graph is a collection of

matchings that covers the edge set. More precisely, an edge coloring of a
graph G is a collection M1 , M2 , . . . , Mk of matchings such that M1 ∪ M2 ∪ · · ·
∪ Mk = EG . (We could require the matchings to be pairwise disjoint; this is
convenient but not essential.)
If we imagine that each matching Mi corresponds to a color, we can say
that an edge coloring is an assignment of colors to the edges of the graph
such that adjacent edges get different colors.
If M1 , . . . , Mk is an edge coloring, we say that k is the number of colors of
the coloring (even if some Mi is empty). We also say that this is a k-coloring.
An edge coloring is minimum if its number of colors is the smallest possible,
i.e., if no other coloring uses fewer colors.
E DGE C OLORING P ROBLEM: Find a minimum edge coloring of a given

graph.
The chromatic index of a graph G is the minimum number of colors

necessary to color the edges of G. This number is denoted by
χ 0 (G) .
(Do not confuse this with the chromatic number χ(G), defined in chapter 8.)
Exercises
◦ E 12.1 Let M1 , . . . , Mk be an edge coloring of a graph. Show that there is a
coloring M10 , . . . , Mk0 such that matchings M10 , . . . , Mk0 are pairwise disjoint.
E 12.2 An industrial process consists of a certain set of tasks. Each task is

executed by a worker on a machine and takes 1 day of work. Each worker is
111
FEOFILOFF Edge coloring 112
qualified to operate only some of the machines. How many days are needed
to complete the process?
E 12.3 A school can be represented by a {U, W }-bipartite graph: each vertex

in U is a teacher, each vertex in W is a class of student, and each teacher
is adjacent to the classes she must teach. A school week is divided into
periods (Monday from 8 to 10, Monday from 10 to 12, etc.), and each period
is represented by a color. An edge coloring of the graph is a scheduling of the
classes for a week. How many periods are necessary and sufficient to fulfill
the week’s program?1
E 12.4 Show that the edge coloring problem is a special case of the vertex
coloring problem (see chapter 8).
E 12.5 Show a graph with two different minimum edge colorings.
◦ E 12.6 Find a minimum edge coloring of a complete graph. Find a mini-

mum edge coloring of a complete bipartite graph.
◦ E 12.7 Compute the chromatic index of a path and of a circuit. Compute

the chromatic index of graphs with ∆ = 0, with ∆ = 1, and with ∆ = 2.
E 12.8 Calculate the chromatic index of the Petersen graph.
E 12.9 Let G be a cubic graph that has a Hamiltonian circuit. (A circuit C in

G is Hamiltonian if VC = VG . See chapter 17.) Prove that χ 0 (G) = 3.
E 12.10 Show that χ 0 (G) ≥ m(G)/α 0 (G) for every graph G.
? E 12.11 Show that any edge coloring of a graph G uses at least ∆(G) colors.
0
χ ≥ In other words, show that
χ 0 (G) ≥ ∆(G)
for every graph G. Show that this is a special case of the inequality χ ≥ ω in
exercise 8.38.
◦ E 12.12 Let G be an r-regular graph with an odd number of vertices. Show

that χ 0 (G) > r.
E 12.13 Let G be an r-regular graph with r ≥ 2. Suppose that G has a bridge

and show that χ 0 (G) > r. (See exercise 9.18.)
1
This is the “timetabling problem.”
E 12.14 Let G be an r-regular graph with r ≥ 1. Suppose that G has an

articulation and show that χ 0 (G) > r.
E 12.15 Suppose that n(G) is odd and m(G) > ∆(G) (n(G) − 1)/2. Show that
χ 0 (G) > ∆(G).
E 12.16 Let G be an r-regular graph, r ≥ 1, with an odd number of vertices.

Let H be the subgraph obtained by removing at most (r − 1)/2 edges from G.
Show that χ 0 (H) > ∆(H).
E 12.17 Show that the edge set of every tree T can be colored with (only)
∆(T ) colors. (Compare to exercise 12.11.)
E 12.18 Show that χ 0 (G) ≤ 2∆(G) − 1 for every graph G. (Hint: induction on
the number of edges of G.)
E 12.19 (M INIMAL COLORING ALGORITHM) Consider the following greedy

algorithm for coloring the edges of a graph G. Each iteration of the algorithm
starts with a collection M1 , . . . , Mj of matchings. In each iteration,
pick an edge e which is not in M1 ∪ · · · ∪ Mj ; if there is an i such that
Mi ∪ {e} is a matching, then start a new iteration with M1 , . . . , Mi−1 ,
Mi ∪ {e}, Mi+1 , . . . , Mj ; else, start a new iteration with M1 ,. . . , Mj , {e}.
Show that the algorithm uses at most 2∆(G) − 1 matchings. Show that the
algorithm uses at most 2χ 0 (G) − 1 matchings. Does the algorithm produce a
minimum coloring?
E 12.20 (M INIMAL COLORING ALGORITHM) Consider the following greedy

algorithm for coloring the edges of a graph G:
the j-th iteration starts with a collection M1 , M2 , . . . , Mj−1 of matchings
and calculates a maximal matching Mj in the graph G − (M1 ∪ M2 ∪ · · ·
∪ Mj−1 ).
Show that the algorithm uses at most 2∆(G) − 1 colors. Show that the
algorithm uses at most 2χ 0 (G) − 1 colors. Does the algorithm produce a
minimum coloring?
E 12.21 (A LGORITHM) Consider the following algorithm for coloring the

edges of a graph G:
the j-th iteration starts with a collection M1 , M2 , . . . , Mj−1 of match-
ings and calculates a maximum matching Mj in the graph G − (M1 ∪
M2 ∪ · · · ∪ Mj−1 ).
Does this algorithm produce a minimum coloring?
E 12.22 (C OLOR EXCHANGE HEURISTIC) Consider the following “alternat-

ing path color exchange” heuristic2 that tries to solve the edge coloring
problem:
At the beginning of each iteration we have a partial coloring, i.e., a
collection M1 , M2 , . . . , Mk of pairwise disjoint matchings. Let vw be an
uncolored edge, i.e., an edge which is not in M1 ∪ · · · ∪ Mk . Let Mi be a
“missing” color at v, and let Mj be a “missing” color at w. Let P be the
component of graph (VG , Mi ∪ Mj ) that contains v. Substitute Mi ⊕ EP
for Mi . Then, substitute Mj ∪ {vw} for Mj and start a new iteration.
Complete the details and discuss the heuristic. Does it solve the edge color-
ing problem?
E 12.23 Show that every bipartite r-regular graph admits an edge coloring
with only r colors. (See exercise 10.29.)
E 12.24 Pick 16 squares in an 8-by-8 chess board so that each row and each
column of the board contains exactly two of the chosen squares. Prove that it
is possible to place 8 white and 8 black pawns in the 16 chosen squares so that
each row and each column contains exactly one white and one black pawn.
? E 12.25 Let G be a bicolorable graph. Show that the edge set of G can be
colored with no more than ∆(G) colors. (See heuristic 12.22 or exercise 10.34.)
? E 12.26 (K ŐNIG ’ S T HEOREM3 ) Show that χ 0 (G) = ∆(G) for every bicol-
orable graph G. (Follows from exercises 12.11 and 12.25.)
E 12.27 Show minimum edge colorings of the graphs in figures 10.1 and 10.2.
E 12.28 Let M and N be two matchings of a graph G. Suppose that

|M | − |N | ≥ 2. Show that there are matchings M 0 and N 0 such that M ∪ N =

M 0 ∪ N 0 and |M 0 | − |N 0 | < |M | − |N |.
E 12.29 Let G be a graph and set k = χ 0 (G). Showthat there is a k-coloring
M1 , M2 , . . . , Mk of the edges such that |Mi | − |Mj | ≤ 1 for every pair i,j of
colors. Write a “formula” for |Mi | in terms of m(G). (See exercise 12.28.)
2
Wilf says that heuristics are “methods that seem to work well in practice, for reasons
nobody understands” (Algorithms and Complexity, Prentice-Hall, 1986).
3
Dénes Kőnig ( − ). (See article in Wikipedia.)
? E 12.30 (V IZING ’ S T HEOREM4 ) Show that

χ 0 (G) ≤ ∆(G) + 1
for every graph G.5 (If we combine this with exercise 12.11, we can say that
∆ ≤ χ 0 ≤ ∆ + 1 for every graph.)
E 12.31 Show that the color exchange heuristic suggested in exercise 12.22 is
not sufficient to prove Vizing’s theorem (exercise 12.30).
E 12.32 (E RD ŐS AND W ILSON T HEOREM) Let G 1 (n) be the collection of all
graphs in G(n) (see section 1.18) for which χ 0 = ∆. Show that
|G 1 (n)|
lim = 1.
n→∞ |G(n)|
D 12.33 (A LGORITHM) Devise a fast algorithm to calculate χ 0 (G) for any

given graph G.
D 12.34 (A LGORITHM) Devise a fast algorithm to solve the edge coloring

problem.
E 12.35 Let X be the set of vertices of a graph G that have degree ∆(G). Show
the following: if G[X] is a forest, then χ 0 (G) = ∆(G).
Planar graphs
E 12.36 Prove that the following statement is equivalent to the Four Color
Theorem (exercise 8.63): χ 0 (G) = 3 for every cubic edge-biconnected planar
graph G. (Compare to exercise 12.13. See exercise 8.69.)
4
Published in 1964–1965 by Vadim G. Vizing ( − ). Discovered, independently,
by Ram Prakash Gupta in 1966.
5
It is tempting to compare this inequality with inequality χ ≤ ∆ + 1 in exercise 8.30. But
the reasons behind the two inequalities are very different.
Chapter 13
Connectors and acyclic sets
A connector of a graph G is any subset C of EG such that graph (VG , C) is

connected.1 A connector C∗ is minimum if there is no other connector C
such that |C| < |C∗ |.
M INIMUM C ONNECTOR P ROBLEM: Find a minimum connector of a

given graph.
A connector Ĉ is minimal if there is no connector C such that C ⊂ Ĉ. Ev-

ery minimum connector is, of course, minimal. It is a bit surprising (given the
case of vertex covers, for example) that the converse is true (see exercise 13.5).
Because of this, the minimum connector problem is computationally very
easy.
A set F of edges of a graph G is acyclic if the graph (VG , F ) has no circuits,
i.e., if (VG , F ) is a forest. An acyclic subset F ∗ of EG is maximum if there is
no acyclic subset F such that |F | > |F ∗ |.
M AXIMUM A CYCLIC S ET P ROBLEM: Given a graph G, find a maxi-

mum acyclic subset of EG .
An acyclic subset F̌ of EG is maximal if there is no acyclic subset F of EG

such that F ⊃ F̌ . Every maximum acyclic subset is, of course, maximal. It is
a bit surprising that the converse is true (see exercise 13.6). Because of this,
the maximum acyclic subset problem is computationally very easy.
A spanning tree of a graph G is any spanning subgraph of G that hap-
pens to be a tree.2 A spanning tree is essentially the same as a minimal
connector and a maximal acyclic set (see exercise 13.4).
1
See Schrijver [Sch03, p.855], for example.
2
A spanning tree of a graph could be called skeleton of the graph. In German, one says
Gerüst (= scaffold).
117
FEOFILOFF Connectors and acyclic sets 118
Exercises
◦ E 13.1 Show that a graph has a connector if and only if it is connected.
Show that every graph has an acyclic set.
E 13.2 Let C be a minimal connector of a graph. Show that C is a maximal

acyclic set.
E 13.3 Let G be a connected graph, and F be a maximal acyclic subset of EG .

Show that F is a minimal connector. (See exercise 1.199.)
E 13.4 Let C be a minimal connector, and F be a maximal acyclic set of a

connected graph G. Show that graphs (VG , C) and (VG , F ) are spanning trees
of G.
Let T be a spanning tree of G. Show that ET is a minimal connector and
also a maximal acyclic set of G.
? E 13.5 Show that every minimal connector of a graph G has exactly n(G)−1
edges. (See exercise 1.228.) Deduce that every minimal connector is mini-
mum.
? E 13.6 Show that every maximal acyclic set of a graph G has exactly
n(G) − c(G) edges, where c(G) is the number of components of G. (See
exercise 1.231.) Deduce that every maximal acyclic set is maximum.
E 13.7 (A LGORITHM) Devise an efficient algorithm to receive a graph G and

return a minimum connector of G (or a proof that G is not connected).
Devise an efficient algorithm to receive a graph G and return a maximum
acyclic subset of EG .
? E 13.8 (E DGE EXCHANGE) Let C be a minimal connector of a graph G and

b an element of EG r C. Show that there is an element a of C such that
(C ∪ {b}) r {a}
is a minimal connector of G.
E 13.9 Let a be an edge in a minimal connector C of a graph G. Give a

necessary and sufficient condition for EG r C to have an edge b such that
(C r {a}) ∪ {b} is a connector. (Compare to exercise 13.8.)
E 13.10 (A LGORITHM) Suppose that each edge e of a graph G has a numeric

“weight”
P π(e) ≥ 0. The weight of any set A of edges is then is the number
e∈A π(e).
Devise an algorithm to find a minimum-weight connector of G.3
3
The famous algorithms of J. B. Kruskal and R. C. Prim solve this problem. They are
among the oldest and best known greedy algorithms in graph theory. The proof of correction
of these algorithms relies on exercise 13.8.
Chapter 14
Minimum paths and circuits
A path is shorter than another one if the length of the former is smaller than
that of the latter. A path P∗ is shortest, or minimum, if no shorter path has
the same endpoints as P∗ .
S HORTEST PATH P ROBLEM: Given vertices v and w of a graph, find a

shortest path with endpoints v and w.
The distance between two vertices v and w is the length of a shortest

path with endpoints v and w.1 (If there is no path with these endpoints, the
distance is not defined.) The distance between vertices v and w of a graph G
will be denoted by
distG (v, w) .
If G is implicit, we will simply write dist(v, w).
A circuit is minimum if the graph has no shorter circuit. The girth of a
graph is the length of a minimum circuit. (If the graph has no circuit, its girth
is not defined.)
Exercises
E 14.1 Compute the distance between vertex x and each of the other vertices
in figure 14.1. Then, show a shortest path between x and y.
◦ E 14.2 Let k be the distance between two vertices v and w in a graph. Show
that (1) there is a path of length k from v to w and (2) there is no path of length
smaller than k from v to w. Show the converse: if (1) and (2) hold, then the
distance between v and w is k.
1
The expressions “minimum distance” and “shortest distance” are redundant and
should be avoided.
121
FEOFILOFF Minimum paths and circuits 122
y
Figure 14.1: Find a shortest path between x
and y. See exercise 14.1.
E 14.3 Suppose that v0 v1 · · · vk is a shortest path (among those with end-

points v0 and vk ). Prove that
dist(v0 , vj ) = j
for every index j.
? E 14.4 (T RIANGLE I NEQUALITY) Let (x, y, z) be a triple of vertices of a

connected graph. Prove that
dist(x, y) + dist(y, z) ≥ dist(x, z) .
E 14.5 Let r be a vertex and uv be an edge of a connected graph. Show that
|dist(r, u) − dist(r, v)| ≤ 1 .
E 14.6 (B REATH -F IRST S EARCH A LGORITHM) Devise an efficient algorithm

that will receive two vertices v and w of a graph and compute the distance
between v and w. Devise an efficient algorithm to find a shortest path
between two given vertices.
E 14.7 (D ISTANCE T REE) Let r be a vertex of a connected graph G. Show

that G has a spanning tree T such that
distG (r, x) = distT (r, x)
for every vertex x (i.e., the distance between r and x in G is equal to the
distance between r and x in T ).
◦ E 14.8 Is it true that every connected graph G has a spanning tree T such
that distG (u, v) = distT (u, v) for every pair u,v of vertices?
E 14.9 The eccentricity of a vertex v in a graph is the number exc(v) :=

maxw∈V dist(v, w). A center is a vertex of minimum eccentricity. The radius
of the graph is the eccentricity of a center.
Show that every tree has at most two centers, and if it has two then they
are adjacent.
E 14.10 The Heawood2 graph has vertex set {0, 1, 2, . . . , 13}. Each vertex i is
adjacent to vertices (i + 1) mod 14 and (i + 13) mod 14.3 In addition, each i is
adjacent to a third vertex, which depends on the parity of i: if i is even, then it
is adjacent to (i+5) mod 14, and if i is odd, then it is adjacent to (i+9) mod 14.
Draw a figure of the Heawood graph. Find a minimum-length circuit in
the graph.
E 14.11 Show that every connected graph with m ≥ 3n/2 has a circuit of
length ≤ c log n for some constant c.
E 14.12 (A LGORITHM) Devise an algorithm to calculate the girth of any

given graph. Devise an algorithm to find a minimum circuit in any given
graph. (See exercise 14.6.)
Parity constraints
We say that a circuit or path is odd if its length is an odd number. Similarly,
a circuit or path is even if its length is an even number.
The odd girth of a graph is the length of a minimum odd circuit in the
graph. The even girth is defined similarly.
E 14.13 Let r be a vertex of a connected graph G. Let u and v be two adjacent

vertices such that dist(r, u) = dist(r, v). Show that G has an odd circuit of
length at most dist(r, u) + dist(r, v) + 1. (See exercise 14.3.)
E 14.14 Let r be a vertex of a connected graph G. Let x and y be two adjacent

vertices such that dist(r, x) and dist(r, y) have the same parity (i.e., both are
even or both are odd). Show that G has an odd circuit.
E 14.15 (Converse of 14.13) Let r be a vertex of a connected graph G.

Let O be an odd circuit in G. Show that O has an edge xy such that
distG (r, x) = distG (r, y). (See exercise 14.5.)
2
Percy John Heawood ( − ).
3
The expression “i mod j” denotes the remainder of the division of i by j.
E 14.16 Let r be a vertex of a connected graph G. Show that G is bicolorable

if and only if dist(r, u) 6= dist(r, v) for every edge uv. (See exercises 14.13
and 14.15.)
E 14.17 Use the concept of distance to show that a graph is bicolorable if and
only if it has no odd circuits. (Compare to exercise 4.15. See exercise 14.14.)
E 14.18 (A LGORITHM) Devise an algorithm to calculate the odd girth of any

given graph. Devise an algorithm to find a minimum odd circuit in any given
graph. (See exercises 14.13, 14.15 and 14.6. Compare to exercise 1.123.)
! E 14.19 (A LGORITHM) Devise an algorithm to calculate the even girth of

any given graph. Devise an algorithm to find a minimum even circuit in any
given graph.
! E 14.20 (A LGORITHM) Given two vertices u and v of a graph G, find a

shortest path in the collection of all even paths whose endpoints are u and v.
! E 14.21 (A LGORITHM) Give two vertices u and v of a graph G, find a

shortest path in the collection of all odd paths whose endpoints are u and v.
Random graphs
E 14.22 The diameter of a graph G is the number max(u,v) dist(u, v), where
the maximum is taken over all the pairs (u, v) of vertices. Prove that the
diameter of almost every graph in G(n) (see section 1.18) is at most 2.
Chapter 15
Flows
A flow in a graph is a collection of paths that share no edges.1 (Perhaps

“spaghetti” would be a good alternative for “flow”!) More precisely, a flow
is a collection F of paths such that
EP ∩ EQ = ∅
for every pair (P, Q) of distinct elements of F.

Given vertices a and b of a graph G, we will say that a flow F connects
a to b if every path in F has origin a and terminus b. We can also say, under
these circumstances, that F is a flow between a and b, or from a to b. (A flow
from b to a is essentially the same as a flow from a to b.)
A flow F from a to b is maximum if |F| ≥ |F 0 | for every flow F 0 from a
to b.
M AXIMUM F LOW P ROBLEM: Given two vertices a and b of a graph G,

find a maximum flow from a to b.
A set C of edges separates a from b if every path from a to b has at least

one edge in C. According to exercise 15.4, every set that separates a from b
is, essentially, a cut ∂(X) such that X contains a but does not contain b.
Exercises
E 15.1 Consider the bishop graph on a 3-by-3 board. Let a be the upper left
corner square, and b be the upper right corner square. Find a maximum flow
from a to b.
E 15.2 Consider the queen graph on a 3-by-3 board. Let a be the upper
1
This use of the word “flow” is unorthodox. In most books, the word is used in a
somewhat different way.
125
FEOFILOFF Flows 126
left corner square, and b be the square in the middle of the board. Find a
maximum flow from a to b.
E 15.3 Consider the knight graph on a 3-by-3 board. Let a be the first square
of the first row, and b be the last square of the second row. Find a maximum
flow from a to b.
E 15.4 (S EPARATORS VERSUS CUTS) Let a and b be two vertices of a graph G.

Let X be a subset of VG that contains a but does not contain b. Show that ∂(X)
separates a from b.
Let C be a set of edges that separates a from b. Show that there exists a
subset X of VG such that a ∈ X, b ∈/ X and ∂(X) ⊆ C.
◦ E 15.5 Let a and b be two vertices of a graph. Suppose that there is a flow of
cardinality k between a and b. Show that every set of edges that separates a
from b has at least k edges.2
? E 15.6 (F LOW VERSUS CUT )Let a and b be two vertices of a graph G.

Suppose that every cut that separates a from b has at least k edges. Show
that some flow that connects a to b in G has cardinality k. (Compare to
exercises 15.5 and 1.208.)
? E 15.7 (M ENGER ’ S THEOREM 3 )

Let a and b be two vertices of a graph.
∗
Let F be a maximum flow among those that connect a to b. Let C∗ be a
minimum set of edges among those that separate a from b. Show that
|F ∗ | = |C∗ | .
(This is a combination of exercises 15.5 and 15.6.4 )
◦ E 15.8 Let a and b be two vertices of a graph G. Suppose that every set that
separates a from b has at least 2 edges. Let P be a path in G with endpoints a
and b. Is it true that G − EP has a path with endpoints a and b?
E 15.9 (A LGORITHM) Write an algorithm that will receive two vertices a and
b of a graph G and return a flow F from a to b and a set X that contains a but
not b such that |F| = d(X).
2
Thus, a cut with k edges certifies the inexistence of a flow of size greater than k.
3
Karl Menger ( − ). The “g” sounds like “goat” and not like “gentle.”
4
It is also a special case of the Max-Flow Min-Cut Theorem, by Ford, Fulkerson, Elias,
Feinstein, and Shannon.
FEOFILOFF Flows 127
E 15.10 Let G be a graph and let A and B be two non-empty subsets of VG

such that A ∩ B = ∅. A barrier is any subset F of EG such that every path
from A to B has one edge in F .
Suppose that every barrier has at least k edges. Show that there is a
collection of k paths from A to B such that no edge belongs to two of the
paths.
k-edge-connected graphs
The edge-connectivity of a graph G is the cardinality of the smallest subset C
of EG such that G−C is disconnected (i.e., has two or more components). The
edge-connectivity of G is denoted by
κ 0 (G) .
This definition of connectivity does not apply in case G has only one vertex,
because then there is no C such that G − C is disconnected. The convention,
in this case, is to say that κ 0 (G) = 1. (Maybe ∞ would make more sense.)
We say that a graph G is k-edge-connected for every k ≤ κ 0 (G). Thus,
a 1-edge-connected graph is the same as a connected graph, and a 2-edge-
connected graph is the same as an edge-biconnected graph (see section 1.13).
◦ E 15.11 Calculate the edge-connectivity of a path. Calculate the edge-

connectivity of a circuit.
E 15.12 Calculate the edge-connectivity of a complete graph with n ≥ 2

vertices.
E 15.13 Let G be a k-edge-connected graph, with k > 0. Let C be a set of k

edges. Show that G − C has at most 2 components.
◦ E 15.14 Let G be a graph with two or more vertices, and let k be a natural
number. Show that G is k-edge-connected if and only if G − C is connected
for every subset C of EG such that |C| < k.
E 15.15 Let G be a graph with two or more vertices and k a natural number.
Show that G is k-edge-connected if and only if d(X) ≥ k for every set X of
vertices such that ∅ ⊂ X ⊂ VG . (See exercise 15.4.)
E 15.16 Let Bt be one of the components of the bishop graph on a t-by-t

board. Calculate κ 0 (Bt ) for t = 2, 3, 4.
FEOFILOFF Flows 128
E 15.17 Let Qt be the queen graph on a t-by-t board. Calculate κ 0 (Qt ) for
t = 2, 3, 4.
E 15.18 Let C4 be the knight graph on a 4-by-4 board. Calculate κ 0 (C4 ).
? E 15.19 Let G be a graph with two or more vertices. Show (from Menger’s
theorem, exercise 15.7) that G is k-edge-connected if and only if every pair of
its vertices is connected by a flow with cardinality k.
? E 15.20 Show that κ 0 (G) ≤ δ(G) for every graph G with two or more
vertices. Show that the inequality can be strict.
E 15.21 Let G be a graph with two or more vertices such that δ(G) ≥
(n(G) − 1)/2. Show that κ 0 (G) = δ(G).
◦ E 15.22 Let G be a k-edge-connected graph. Show that m(G) ≥ k n(G)/2.
E 15.23 Let G be a k-edge-connected graph. Let A and B be two non-empty

subsets of VG such that A ∩ B = ∅. Show that there is a flow F with
cardinality k in G such that every path in F has an endpoint in A and another
in B.
E 15.24 Let G be a (2k−1)-edge-connected graph. Show that G has a bipartite

spanning subgraph H which is k-edge-connected.
Chapter 16
Internally disjoint flow
A vertex of a path is considered internal if it is different from both the original

and the terminus of the path. Two paths in a graph are internally disjoint
if they have no common internal vertices, i.e., if each vertex of the graph is
internal to at most one of the paths.
For vertices a and b of a graph, an internally disjoint flow is a collection
of pairwise internally disjoint paths from a to b. Hence,
VP ∩ VQ = {a, b}
for every pair (P, Q) of paths in the collection. We will say that such a
collection connects a to b.
M AXIMUM INTERNALLY DISJOINT FLOW P ROBLEM: Given two ver-

tices a and b of a graph, find a maximum internally disjoint flow
connecting a to b.
To avoid fruitless discussions, we shall restrict the problem to the case in

which a and b are not adjacent.
A separator of (a, b) is any set S of vertices such that a and b are in distinct
components of G − S. In other words, a separator of (a, b) is any subset S of
VG r {a, b} such that every path with endpoints a and b has at least one vertex
in S. (Of course there is no separator of (a, b) if a and b are adjacent.)
Exercises
E 16.1 Consider the bishop graph on a 4-by-4 board. Let a be the first square
of the first row, and b be the last square of the last row. Find a maximum
internally disjoint flow connecting a to b. Repeat the exercise with b being the
third square of the first row.
129
FEOFILOFF Internally disjoint flow 130
E 16.2 Consider the queen graph on a 3-by-3 board. Let a be the top left
corner square, and b be the square in the middle of the board. Find a
maximum internally disjoint flow connecting a to b.
E 16.3 Consider the knight graph on a 3-by-3 board. Let a be the first square
of the first row, and b be the last square of the second row. Find a maximum
internally disjoint flow connecting a to b.
◦ E 16.4 Let v be an articulation in a graph G, and let a and b be vertices in

different components of G − v. Check that {v} separates a from b.
◦ E 16.5 Criticize the following alternative definition of a separator: “A sepa-

rator of (a, b) is a set S of vertices such that every path with endpoints a and b
has at least one vertex in S.”
◦ E 16.6 Let a and b be two non-adjacent vertices of a graph. Suppose that an

internally disjoint flow from a to b has k paths. Show that every separator of
(a, b) has at least k vertices.1 (What happens if a and b are adjacent?)
? E 16.7 (F LOW VERSUS SEPARATOR) Let a and b be two non-adjacent ver-

tices of a graph G. Suppose that every separator of (a, b) has at least k
vertices. Show that G has an internally disjoint flow of size k connecting a
to b. (Compare to exercises 16.6 and 1.218.)
? E 16.8 (M ENGER ’ S T HEOREM2 ) Let a and b be two non-adjacent vertices

of a graph. Let P ∗ be a maximum internally disjoint flow among all of those
that connect a to b. Let S∗ be a minimum separator of (a, b). Show that
|P ∗ | = |S∗ | .
(This is a combination of exercises 16.6 and 16.7.)
? E 16.9 Deduce Kőnig–Egerváry’s theorem (exercise 10.7) from Menger’s

theorem (exercise 16.8).
E 16.10 (FAN LEMMA) Let a be a vertex of a graph G and let B be a non-

empty subset of VG r {a}. A fan is a collection of paths from a to B such that
VP ∩ VQ = {a} for every pair (P, Q) of paths in the collection. A barrier is any
subset S of VG r {a} such that every path from a to B has a vertex in S.
Suppose that every barrier has k or more vertices. Show that there is a
fan with k paths.
1
Thus, a separator with k vertices is a certificate of inexistence of an internally disjoint
flow of size greater than k.
2
Karl Menger ( − ). Pronounce the “g” as in “goat”, not as in “gentle.”
E 16.11 Let G be a graph, and let A and B be two non-empty subsets of VG .

A collection of paths is disjoint if VP ∩ VQ = ∅ for each pair (P, Q) of paths
of the collection. A barrier is any subset S of VG such that every path from A
to B has a vertex in S.
Suppose that every barrier has at least k vertices. Show that there is a
disjoint collection of k paths from A to B.
Connectivity
The connectivity of a graph G is the cardinality of the smallest subset S of VG
such that G − S is disconnected (i.e., has two or more components). The
connectivity of a graph G is denoted by
κ(G) .
This definition does not apply when G is complete, because in that case there
is no S such that G − S is disconnected.3 By convention, we set κ(Kn ) = n − 1
for every n ≥ 2 and κ(K1 ) = 1.
We say that a graph G is k-connected for every k ≤ κ(G). Thus, a 1-
connected graph is the same as a connected graph, and a 2-connected graph
is the same as a biconnected graph (see section 1.14).
◦ E 16.12 Compute the connectivity of a path. Compute the connectivity of a

circuit.
◦ E 16.13 Let G be a complete graph with n ≥ 2 vertices, and let e be one of

its edges. Calculate the connectivity of G − e.
E 16.14 Let G be a non-complete graph and k a natural number. Show that G

is k-connected if and only if G − S is connected for every subset S of VG such
that |S| < k.
E 16.15 Let Bt be one of the components of the bishop graph on a t-by-t

board. Calculate κ(Bt ) for t = 2, 3, 4.
E 16.16 Let Qt be the queen graph on a t-by-t board. Calculate κ(Qt ) for
t = 2, 3, 4.
E 16.17 Let K4 be the knight graph on a 4-by-4 board. Calculate κ(K4 ).

3
We could say, perhaps, that κ(G) is ∞ if G is complete.
E 16.18 Let G be a circuit of length 6. Calculate the connectivity of G.
E 16.19 Calculate the connectivity of the Petersen graph.
? E 16.20 Let G be a non-complete graph. Show (from Menger’s theorem,

exercise 16.8) that G is k-connected if and only if each pair of non-adjacent
vertices of G is connected by an internally disjoint flow of size k.
◦ E 16.21 Show that every k-connected graph with two or more vertices is
k-edge-connected. Show that the converse is not true, i.e., that not every k-
edge-connected graph with two or more vertices is k-connected.
? E 16.22 Show that κ(G) ≤ κ 0 (G) for every graph G with two or more
vertices. Show that the inequality may be strict.
E 16.23 Show that κ(G) = κ 0 (G) for every cubic graph G.
E 16.24 Let k be a natural number greater than 1, and G be a k-connected

graph with n(G) ≥ 2k. Show that G has a circuit with 2k or more vertices.
E 16.25 (D IRAC ’ S T HEOREM4 ) Let k be a natural number greater than 1, and

let G be a k-connected graph. Let Z be a set of k vertices of G. Show that
some circuit in G contains all the vertices of Z.
4
Published in 1952 by Gabriel Andrew Dirac ( − ).
Chapter 17
Hamiltonian circuits and paths
A circuit in a graph is longest if the graph does not have a longer circuit. The
circumference of a graph is the length of a longest circuit in the graph.
L ONGEST C IRCUIT P ROBLEM: Find a longest circuit in a given graph.
The problem of finding a longest path is formulated similarly. A path in

a graph is longest if the graph does not have a longer path.
A circuit is Hamiltonian1 if it contains all the vertices of the graph. Any
Hamiltonian circuit is, of course, longest. The longest circuit problem has the
following obvious specialization:
H AMILTONIAN C IRCUIT P ROBLEM: Decide whether a given graph has

a Hamiltonian circuit.
The concept of Hamiltonian path and the Hamiltonian path problem are
defined similarly.
Some of the exercises below involve the condition “δ(G) ≥ k.” Recall
that this condition is equivalent to “|N(v)| ≥ k for every vertex v,” since
|N(v)| = d(v) for every vertex v.
Exercises
◦ E 17.1 Is it true that every complete graph has a Hamiltonian circuit?
◦ E 17.2 Give necessary and sufficient conditions for a complete bipartite

graph to have a Hamiltonian circuit.
1
Reference to William Rowan Hamilton ( − ). (See article in Wikipedia.) A
reference to Thomas P. Kirkman ( − ) would be be fairer (see article in Wikipedia).
133
FEOFILOFF Hamiltonian circuits and paths 134
E 17.3 Find a longest circuit in the graphs shown in figure 17.1.
Figure 17.1: Find a longest circuit. See exercise 17.3.
E 17.4 Find a longest circuit in the Petersen graph. Find a longest path in the
Petersen graph.
E 17.5 Prove that, for all k ≥ 2, the graph Qk has a Hamiltonian circuit. (Hint:
Use induction on k.)
E 17.6 Give a necessary and sufficient condition for a grid to have a Hamil-
tonian circuit.
E 17.7 Find a Hamiltonian circuit in the t-by-t knight graph. (See article in
Wikipedia and article in Wolfram MathWorld.)
◦ E 17.8 Show that χ 0 (G) = 3 for every cubic graph G that has a Hamiltonian
circuit.
E 17.9 (A LGORITHM) Discuss the following algorithm for the Hamiltonian

circuit problem: Given a graph G, generate a list of all permutations of VG ;
discard the permutations that do not correspond to Hamiltonian circuits;
return any of the remaining permutations.
E 17.10 Show that every graph G has a path of length at least δ(G). (See
exercise 1.125.)
E 17.11 Show that every graph G has a circuit with δ(G) + 1 or more vertices,
provided δ(G) is greater than 1. (See exercise 1.128 in section 1.9.)
E 17.12 Show that every graph G has a path with at least χ(G) vertices, where
χ(G) is the chromatic number (see chapter 8) of G. (See exercise 8.47).
E 17.13 Let P ∗ and Q∗ be two longest paths in a connected graph G. Show

that P ∗ and Q∗ have a common vertex. (See exercise 1.170.)
◦ E 17.14 Let G be a graph with a Hamiltonian circuit. Show that G has no

bridges. Show that G has no articulations.
E 17.15 Let G be a graph with a Hamiltonian circuit. Show that every edge
of G belongs to a circuit.
E 17.16 Let G be a {U, W }-bipartite graph such that |U | 6= |W |. Prove that G

has no Hamiltonian circuit. (Another way of posing the question: for every
{U, W }-bipartite graph with a Hamiltonian circuit, one has |U | = |W |.)
E 17.17 Suppose that a graph G has a stable set with more than n(G)/2
vertices. Show that G has no Hamiltonian circuit.
Is it true that every graph G with α(G) ≤ n(G)/2 has a Hamiltonian
circuit?
E 17.18 (N ECESSARY CONDITION) Let S be a set of vertices of a graph G.

Suppose that |S| < n(G) and
c(G − S) > |S| + 1 ,
where c(G − S) is the number of components of G − S. Show that G has no

Hamiltonian path. (See exercise 1.174.)
? E 17.19 (N ECESSARY CONDITION) Let S be a set of vertices of a graph G.

Suppose that 0 < |S| < n(G) and
c(G − S) > |S| ,
where c(G − S) is the number of components of G − S. Show that G has

no Hamiltonian circuit. (See exercise 1.175.) Another way of posing the
question: If G has a Hamiltonian circuit, then c(G − S) ≤ |S| for every non-
empty proper subset S of VG .
Show that the condition “c(G − S) > |S|” is a generalization of exer-
cises 17.14, 17.16 and 17.17.
E 17.20 Suppose that a graph G satisfies the inequality c(G − S) ≤ |S| for
every set S of vertices such that 0 < |S| < n(G). Is it true that G has a
Hamiltonian circuit?
D 17.21 (S UFFICIENT CONDITION : C HVÁTAL’ S CONJECTURE2 ) Let G be a

graph such that c(G − S) ≤ |S|/2 for every subset S of VG such that
2 ≤ |S| < n(G). Prove that G has a Hamiltonian circuit. (Compare to
exercise 17.19.)
E 17.22 Is it true that there is a natural number k such that every k-connected
graph (see page 131) has a Hamiltonian circuit? (Compare to exercises 17.19
and 17.35.)
E 17.23 Let G be a connected graph and O be a circuit in G such that, for

each edge e of O, the graph O − e is a longest path in G. Prove that G has a
Hamiltonian circuit.
E 17.24 Let G be a graph with 4 or more vertices such that δ(G) ≥ n(G) − 2.
Show that G has a Hamiltonian circuit.
E 17.25 Let G be a graph with n vertices and m edges. Suppose that m ≥

2 + 21 (n − 1)(n − 2). Prove that G has a Hamiltonian circuit.
? E 17.26 (S UFFICIENT CONDITION : D IRAC ’ S T HEOREM3 ) Let G be a graph

with 3 or more vertices that satisfies the condition
δ(G) ≥ n(G)/2 .
Show that G has a Hamiltonian circuit. (Hint: Use exercise 1.129.)
? E 17.27 (G ENERALIZATION OF D IRAC ’ S THEOREM) Let G be a graph

with 3 or more vertices that satisfies the condition
dG (u) + dG (v) ≥ n(G)
for every pair (u, v) of distinct non-adjacent vertices. Show that G has a
Hamiltonian circuit. (Hint: Use exercise 1.129.)
E 17.28 Let G be a graph and {V1 , V2 , V3 } be a partition of VG into non-empty

parts. Suppose that (1) each vertex in V1 is adjacent to all vertices of V2 ∪ V3 ,
and (2) each vertex of V2 is adjacent to all vertices of V3 .
Prove that, if |V2 | = 2|V1 | and |V3 | = 3|V1 |, then G has a Hamiltonian
circuit. Prove that, if |V2 | = 2|V1 | and |V3 | = 3|V1 | + 1, then G does not have a
2
Proposed by Vašek Chvátal in 1971.
3
Published in 1952 by Gabriel Andrew Dirac ( − ).
E 17.29 Let A be an algorithm that decides whether a given graph has a

Hamiltonian circuit. Use A to formulate an algorithm to decide whether a
given graph has a Hamiltonian path.
Let B an algorithm that decides whether a given graph has a Hamilto-
nian path. Use B to formulate an algorithm to decide whether a given graph
has a Hamiltonian circuit.
D 17.30 (N ECESSARY AND SUFFICIENT CONDITION ?) Discover a necessary

and sufficient condition for a graph to have a Hamiltonian circuit. Discover
a necessary and sufficient condition for a graph to have a Hamiltonian path.
D 17.31 (A LGORITHM) Devise a fast algorithm to find a Hamiltonian circuit

in a graph (or decide that the graph has no such circuit).4
D 17.32 (A LGORITHM) Devise a fast algorithm to find a longest circuit in

any graph which is not a forest.5
D 17.33 (A LGORITHM) Devise a fast algorithm to find a Hamiltonian path

in a graph (or to decide that the graph has no such path).6
D 17.34 (T RAVELING S ALESMAN P ROBLEM (TSP)) Let K be a complete

graph and ϕ be a function from EK into {0, 1, 2, 3, . . .}. For each edge e of
P graph, we say that ϕ(e) is the cost of e. The cost of any subgraph H of K is
the
e∈EH ϕ(e). Devise an algorithm to find a minimum-cost Hamiltonian circuit
in K.7
Planar Hamiltonian graphs

! E 17.35 (T UTTE ’ S T HEOREM8 ) Show that every 4-connected planar graph
(see page 131) has a Hamiltonian circuit. (Compare to exercise 17.22.)
E 17.36 Show that not every 3-connected planar graph (see page 131) has a
4
Such an algorithm has not yet been found. In technical terms, the problem of deciding
whether a graph has a Hamiltonian circuit is NP-complete. See the books by Garey–
Johnson [GJ79], Harel [Har92], and Sipser [Sip97].
5
Such an algorithm has not yet been found.
6
Such an algorithm has not yet been found.
7
The problem is NP-hard. See the books by Garey–Johnson [GJ79], Harel [Har92] and
Sipser [Sip97]. See the website The Traveling Salesman Problem, maintained by Bill Cook at
Georgia Tech University.
8
William T. Tutte ( − ). (See article in Wikipedia.)
D 17.37 (B ARNETTE ’ S C ONJECTURE) Prove or disprove the following con-

jecture: Every 3-connected 3-regular bicolorable planar graph (see page 131)
has a Hamiltonian circuit.9
9
D. Barnette proposed the conjecture in 1970.
Chapter 18
Circuit covers
A circuit cover, or covering

S by circuits, of a graph G is any collection O of
circuits of G such that O∈O EO = EG . In other words, a circuit cover is a
collection of circuits such that each edge of the graph belongs to a least one
of the circuits of the collection.1
It would be natural to dedicate this chapter to the minimum circuit cover
problem. But this problem is very hard. (See the end of the chapter.) We will
deal then with the circuit decomposition problem, which is much simpler.
A circuit decomposition, or decomposition into circuits, or simple cir-
cuit cover, of a graph is a circuit cover that covers each edge of the graph
only once.
C IRCUIT D ECOMPOSITION P ROBLEM: Find a circuit decomposition of

a given graph.
Due to exercise 18.16, this problem is also known as the “Eulerian cycle
problem.”
Exercises
E 18.1 Show a circuit decomposition of each graph in figure 18.1.
E 18.2 For which values of p and q does a p-by-q grid have a circuit decom-
position?
E 18.3 Find a circuit decomposition of the knight graph.
E 18.4 For which values of k does the cube Qk have a circuit decomposition?
1
Coverings by circuits are very different from coverings by matchings (i.e., edge color-
ings) because a part of a circuit is not a circuit, while every part of a matching is a matching.
139
FEOFILOFF Circuit covers 140
Figure 18.1: Find a circuit decomposition. See exercise 18.1.
E 18.5 Give a necessary and sufficient condition for a complete graph to have
a circuit decomposition.
◦ E 18.6 Suppose that a graph G has a bridge. Show that G has no circuit
decomposition. (See exercise 1.199.)
E 18.7 Let F be a set of edges of a graph G with three or more vertices.

Suppose that the graph (VG , F ) is connected and has a circuit decomposition.
Prove that G is edge-biconnected. Is the converse true?
◦ E 18.8 Suppose that a graph G has an odd-degree vertex. Show that G has
no circuit decomposition.2 (Another way to say the same thing: if a graph G
has a circuit decomposition, then all vertices of G have even degree.)
? E 18.9 (T HEOREM V EBLEN3 AND E ULER4 ) Show that a graph has a

OF
circuit decomposition if and only if the degree of each of its vertices is even.
(Compare to exercise 18.8.) In other words, show that the absence of odd-
degree vertices is a necessary and sufficient condition for a graph to have a
circuit decomposition.
E 18.10 Show that a graph has a circuit decomposition if and only if all of its
cuts are even.
E 18.11 Graphs that have circuit decompositions have no odd vertices. On

the other hand, bicolorable graphs have no odd circuits. Is there something
behind this parallel?
E 18.12 Let G be the graph of a plane map M. Suppose that G is biconnected

and has no vertices of degree 2. Let G∗ be the graph of faces (i.e., the dual
graph) of the map M. Show that G∗ is bicolorable if and only if G has a circuit
decomposition.
2
Therefore, an odd-degree vertex is a certificate of inexistence of a circuit decomposition.
3
Oswald Veblen ( − ). See article in Wikipedia.
4
Leonhard Euler ( − ). See article in Wikipedia.
E 18.13 (A LGORITHM) Devise an algorithm that receives a graph G and

returns a circuit decomposition of G, or proves that there is no such decom-
position.
Eulerian cycles and trails

As we said in the end of section 1.9, a walk in a graph is any sequence
(v0 , v1 , v2 , . . . , vk−1 , vk ) of vertices such that vi is adjacent to vi−1 for every i
between 1 e k. We say that the walk goes from v0 to vk . The length of the
walk is the number k.
A trail is a walk without repeated edges, i.e., a walk whose edges are
pairwise distinct. A trail (v0 , . . . , vk ) is closed if v0 = vk .
A trail is Eulerian5 if it passes through all the edges of the graph.6 Thus,
a trail (v0 , v1 , . . . , vk−1 , vk ) is Eulerian if and only if {v0 v1 , v1 v2 , . . . , vk−1 vk } is
the set of (all the) edges of the graph.
A cycle is a closed trail.7 A cycle is Eulerian if and only if it passes
through all the edges of the graph.
E 18.14 Find an Eulerian cycle in the graph of figure 18.2.
a h
b
c g
e
d f
Figure 18.2: Find an Eulerian cycle. See exercise 18.14.
E 18.15 Consider the 21 tiles of the domino game which are not doubles.
Each of those tiles corresponds to a subset of cardinality 2 of the set
{0, 1, 2, . . . , 6}. One is allowed to make a tile {i, j} “touch” a tile {j, k} so as
to produce the sequence (i, j, j, k). Question: Is it possible to form a “wheel”
that contains all the 21 tiles? What if we eliminate all tiles that contain a “6”?
5
Reference to Leonhard Euler ( − ). See article in Wikipedia.
6
Some authors also require the trail to pass through all the vertices of the graph. The
difference between these two definitions is superficial.
7
According to this definition, a cycle may have length 0. A circuit, on the other hand,
has length at least 3 by definition.
? E 18.16 (E ULERIAN CYCLES) Show that every graph with an Eulerian cy-
cle has a circuit decomposition.
Show that every connected graph with a circuit decomposition has an
Eulerian cycle.
E 18.17 Give a necessary and sufficient condition for a graph to have a non-
closed Eulerian trail.
E 18.18 (A LGORITHM) Devise an algorithm tho find an Eulerian trail (closed

or not) in any given connected graph.
! E 18.19 (C HINESE P OSTMAN P ROBLEM8 ) Given a graph, find a shortest

walk among those that are closed and pass through all the edges of the graph.
E 18.20 Suppose that a graph G has an Eulerian cycle. Show that the line
graph L(G) has a Hamiltonian circuit (see exercise 1.24).
Show that the converse is not true: L(G) may have a Hamiltonian circuit
without G having an Eulerian cycle.
E 18.21 Let xy and yz be two edges of a connected graph G that has no odd-
degree vertices. Is it true that G has an Eulerian cycle in which xy and yz
appear consecutively?
E 18.22 Let G be a connected graph all of whose vertices have even degree.
Suppose also that m(G) is even. Prove that EG admits a partition {F1 , F2 }
such that |F1 ∩ ∂{v}| = |F2 ∩ ∂{v}| for each vertex v, i.e., v is incident to the
same number of edges of F1 and F2 .
Minimum circuit covers

As we said in the beginning of the chapter,
S a circuit cover of a graph G is any
collection O of circuits of G such that O∈O EO = EG .
A circuit cover O is minimum if there is no circuit cover O0 such that
|O0 | < |O|.
P
The total length of a circuit cover O is the sum O∈O |EO |. It is clear that
every circuit decomposition is a cover of minimum total length.
The thickness of a circuit cover O of a graph G is the number
maxe∈EG |{ O ∈ O : EO 3 e }|. So, if a circuit cover has thickness k,
then every edge of the graph belongs to at most k of the circuits. Conversely,
8
Proposed in 1962 by the Chinese mathematician Mei-Ko Kwan.
if each edge of the graph belongs to ≤ k circuits of the cover, then the cover
has thickness ≤ k. It is clear that a circuit decomposition is the same as a
cover of thickness 1.
Exercises
◦ E 18.23 Show that a graph has a circuit cover if and only if it has no bridges.
D 18.24 (M INIMUM CIRCUIT COVER) Devise an algorithm to find a mini-

mum circuit cover of any bridgeless graph.
! E 18.25 Show that, for every k even, the cube Qk can be covered with
only k/2 circuits.
E 18.26 Find a minimum circuit cover in the Petersen graph.
E 18.27 Find a minimum circuit cover of the first graph in figure 18.1. (This
graph can be described as K6 − M , where M is a perfect matching.)
D 18.28 (S HORTEST COVER) Find a circuit cover of minimum total length in

any given bridgeless graph.9
E 18.29 Find a circuit cover of minimum total length in the Petersen graph.
? E 18.30 Show that every edge-biconnected planar graph G has a circuit

cover of total length ≤ 2m(G).
D 18.31 (M INIMUM T HICKNESS C OVER) Find a minimum-thickness circuit

cover of any given bridgeless graph.
(According to the Circuit Double Cover conjecture,10 every bridgeless
graph has a cover of thickness ≤ 2.)
? E 18.32 Show that every edge-biconnected planar graph has a circuit cover
of thickness ≤ 2.
E 18.33 Find a minimum-thickness circuit cover of the Petersen graph.

9
An efficient algorithm for this problem is not (yet) known. In technical terms, the
problem is NP-hard.
10
The conjecture is attributed to George Szekeres and Paul Seymour.
E 18.34 Find a minimum-thickness circuit cover of K5 .
E 18.35 Find a minimum-thickness circuit cover of K3,3 .
! E 18.36 (T HEOREM OF K ILPATRICK AND J AEGER11 ) Show that every 4-

edge-connected graph (see page 127) has a circuit cover of thickness ≤ 2.
E 18.37 Show (by means of examples) that the concepts of minimum cover,
cover of minimum total length, and minimum-thickness cover are pairwise
distinct.
E 18.38 Why doesn’t the Chinese postman problem (exercise 18.19) solve the
minimum-thickness circuit cover problem (see exercise 18.31)? Why doesn’t
it solve the problem of the circuit cover of minimum total length (see exer-
cise 18.28)?
11
Published by Kilpatrick in 1975 and by F. Jaeger in 1976.
Chapter 19
Characterization of planarity
As we said in section 1.17, a graph is planar if it is representable by a plane

map, i.e., if it is isomorphic to the graph of some plane map.
P LANARITY P ROBLEM: Decide whether a given graph is planar or not.
If a graph is not planar, how can we make this evident? A very beautiful
answer involves the concept of forbidden minors (see section 1.16): every
non-planar graph has a minor which is obviously non-planar.
Exercises
? E 19.1 Show that K3,3 is not planar. (See, for example, exercise 1.271.)
? E 19.2 Show that K5 is not planar. (See, for example, exercise 1.270.)
Figure 19.1: K3,3 and K5 are not planar. See exercises 19.1 and 19.2.
◦ E 19.3 Show that every subgraph of a planar graph is planar. In other

words, if a graph G has a non-planar subgraph, then G is not planar.
◦ E 19.4 Suppose that all the proper subgraphs of a graph G are planar. Is it
true that G is planar?
145
FEOFILOFF Characterization of planarity 146
E 19.5 Suppose that a graph G has neither a subgraph isomorphic to K5 nor

a subgraph isomorphic to K3,3 . Is it true that G is planar?
?◦ E 19.6 Show that every topological minor (see section 1.16) of a planar
graph is planar. In other words, if a graph G has a non-planar topological
minor, then G is not planar. (In particular, if G contains a subdivision of K5
or K3,3 , then G is not planar.)
? E 19.7 Show that every minor (see section 1.16) of a planar graph is planar.
In other words, if a graph G has a non-planar minor, then G is not planar.
(In particular, if G has a subcontraction isomorphic to K5 or to K3,3 , then G is
not planar.)
E 19.8 Show that every proper minor of K5 is planar. Show that every proper
minor of K3,3 is planar.
◦ E 19.9 Show that K3,3 is not a minor of K5 . Show that K5 is not a minor
of K3,3 .
E 19.10 For which values of t is the t-by-t bishop graph planar?
E 19.11 For which values of t is the t-by-t knight graph planar?
E 19.12 Show that the Petersen graph is not planar. (See exercises 1.247
and 1.248.)
E 19.13 Show that the cube Q4 is not planar. (See exercise 1.249.)
?! E 19.14 (WAGNER ’ S T HEOREM1 ) Show that a graph is planar if and only

if it has neither a minor isomorphic to K5 nor a minor isomorphic to K3,3 .
?! E 19.15 (K URATOWSKI ’ S T HEOREM2 ) Show that a graph is planar if and

only if it has neither a topological minor isomorphic to K5 nor a topological
minor isomorphic to K3,3 . (Compare to exercise 19.6.)
E 19.16 Discuss the following statement: “Since K5 is not bicolorable, we can

conclude that every non-planar bicolorable graph has K3,3 as a topological
minor”.
1
Published in 1937 by Klaus W. Wagner ( − ).
2
Published in 1930 by Kazimierz Kuratowski ( − ).
! E 19.17 (A LGORITHM) Write an algorithm to decide whether a given

graph is planar.
! E 19.18 Show that every 4-connected non-planar graph has a K5 minor.

Show that every 3-connected non-planar graph with 6 or more vertices has
a K3,3 minor.
D 19.19 Prove the following conjecture by Dirac:3 If a graph G does not have
a K5 topological minor, then m(G) ≤ 3n(G) − 6. (Compare to exercise 1.268.)
E 19.20 Show that a graph is outerplanar (see exercise 1.283) if and only if it
has neither a K4 minor nor a K2,3 minor. Show that a graph is outerplanar if
and only if it has neither a K4 topological minor nor a K2,3 topological minor.
3
The conjecture was proposed by G. A. Dirac in 1964.
Appendix A
Hints for some of the exercises
Exercise 1.208. The proof does induction on the distance between r and s. It deals
with the case in which r and s are neighbors, then the case in which there is a path
of length 2 from r to s, and so on.
Let v0 v1 . . . vk be a path from r to s. By induction hypothesis, there are two
paths, P and Q, from v0 to vk−1 such that EP ∩ EQ = ∅. Let C be a circuit that
contains edge vk−1 vk . The graph P ∪ Q ∪ C contains two paths from v0 to vk that
share no edges.
Exercise 1.226. Suppose that there are two different paths, say P and Q, with
endpoints x and y. Find a circuit in the graph P ∪ Q.
Exercise 1.233. Let v be a vertex such that d(v) = ∆. For each neighbor w of v,
take a maximal path among those that have v as first vertex and w as second vertex.
Exercise 1.228. Write a proof by induction on m(G). Induction step: Let a be an

edge of T , and let T1 and T2 be the two components of T −a. By induction hypothesis,
m(T1 ) = n(T1 ) − 1 and m(T2 ) = n(T2 ) − 1.
Exercise 1.229. Induction on n(G). Induction step: Suppose m(G) = n(G) − 1.

Let v be a vertex such that d(v) = 1. The graph G − v is connected and m(G − v) =
n(G − v) − 1. By induction hypothesis, G − v has no circuits. Therefore, G has no
circuits.
Exercício 1.266. Do an induction on the number of faces. The induction base uses
the equality m = n − 1 which is valid for trees (see exercise 1.228).
Exercise 1.268. Begin by dealing with the case in which G is edge-biconnected.

See exercises 1.266 and 1.267.
Exercise 1.275. See exercise 1.268.
149
FEOFILOFF 150
Exercise 4.23. Let us say that the edges in D are red and the others are black. A
path is even if it has an even number of red edges, and odd if it has an odd number
of red edges.
Fundamental fact: if two paths have the same endpoints, then they have the
same parity. Prove this fact by induction on the number of shared vertices.
Exercise 5.27. Show that the algorithm from exercise 5.22 returns a stable set S
such that |S| ≥ n/(µ + 1).
Exercise 6.15. Assume ω ≤ 2. Build a bicolorable graph H such that VH = VG and

dG (v) ≤ dH (v) for every vertex v. Use exercise 4.12.
Exercise 8.47. Let {X1 , . . . , Xk } be a minimum coloring which maximizes the

number ki=1 i |Xi |. Then there is a path of the form x1 x2 . . . xk with xi ∈ Xi .
P
Another possibility: see algorithms in exercises 8.28 and 8.29.

Another possibility: remove the last vertex in a maximum-length path and
apply induction.
Exercise 8.41. In the beginning of each iteration, vertices v1 , . . . , vj have already

been colored with k colors, and G[{v1 , . . . , vj }] has a clique with k vertices.
Exercise 9.36. Show that G − v has at least one odd component. Then show that
G − v cannot have more than one odd component.
Exercise 10.4. Prove that one of the endpoints of each edge is saturated by all
maximum matchings. Proof by contradiction: suppose there is an edge uw and
maximum matchings M and N such that M does not saturate u and N does not
saturate w. Study the component of (VG , M ∪ N ) that contains u.
Exercise 10.6. Proof by induction on the number of vertices. Take a vertex u that
is saturated by all maximum matchings. Apply the induction hypothesis to G − u.
Exercise 10.18. Let M be a maximum matching. Let us say that a path is good if it
has an endpoint in U r V (M ) and is M -alternating. Let X be the set of vertices of
all good paths. Let K := (W ∩ X) ∪ (U r X). Show that K is a cover. Show that
|K| = |M |.
Exercise 10.12. Let M ∗ be a maximum matching, and suppose that |M ∗ | < k.

According to Kőnig’s theorem, G has a cover K∗ such that |K∗ | < k. Thus, m(G) ≤
|U | |K∗ | ≤ |U | (k − 1). Contradiction.
FEOFILOFF Hints for some of the exercises 151
Exercise 10.22. Let M be a matching and K a cover such that |M | = |K| (see
exercise 10.6). Show that |U | ≤ |K| and see exercise 9.30.
Exercise 10.22. The proof is an induction on the cardinality of U . The induction

step has two cases. In the first, |NG (Z)| > |Z| for every proper non-empty subset Z
of U . In the second, |NG (Y )| = |Y | for some proper non-empty subset Y of U . In
the first case, take any edge uw with u ∈ U amd apply the induction hypothesis to
G − {u, w}. In the second, apply the induction hypothesis to G − (Y ∪ NG (Y )) and
to G[(U r Y ) ∪ (W r N(Y ))].
Exercise 10.32. Consider the graph (VG , M ∪ N ). See exercise 9.17.
Exercise 12.2. Each worker is a vertex of my graph; each machine is a vertex as

well; each edge is a task that assigns a worker to a machine; each color is a work day.
Exercise 12.15. G does not have a perfect matching.
Exercise 12.16. G does not have a perfect matching. Follows from exercise 12.15.
Exercise 12.23. Make an induction on r. See exercise 10.29.
Exercise 13.4. It suffices to prove that each edge of C is a bridge in the graph
(VG , C). (See also exercises 1.149 and 1.157.)
Exercise 14.9. Let x and z be two non-adjacent vertices of a tree. Let L be the only
path from x to z. Show that if exc(x) = exc(z) then exc(y) < exc(x) for every internal
vertex y of L.
Exercise 14.18. For each vertex r, analyze the distance tree (exercise 14.7) centered
in r. See exercises 14.13, 14.5, 1.123, and 14.3.
Exercise 14.19. For each vertex r, analyze the distance tree 14.7 centered in r.
Exercise 14.20. Find a minimum-weight perfect matching (see exercise 11.17) in

an appropriate graph built from (G, u, v).
FEOFILOFF 152
Exercise 14.21. Find a minimum-weight perfect matching (see exercise 11.17) in

an appropriate graph built from (G, u, v).
Exercise 15.6. Do a proof by induction on k. Adopt the following definitions: For

every subset B of EG , let V (B) be the set of vertices that that are incident to elements
of B, and let G(B) be the graph (V (B) ∪ {r}, B). A subset B of EG is good if G(B) is
connected and dG−B (Y ) ≥ k − 1 for every Y that contains r but does not contain s.
Start by proving the following lemma: For every good set B, if s is not in G(B),
then there is an edge e in EG r B such that B ∪ {e} is good. Use exercise 1.115.
Exercise 16.10. Add to G a new vertex y and new edges connecting y to each
vertex in S. Show that the new graph is k-connected.
Exercise 16.25. Do an induction on k, starting with k = 2. At the induction step,

use the fan lemma, exercise 16.10.
Exercise 17.10. Take a maximal path. (See section 1.7.)
Exercise 17.19. See exercises 1.174 and 1.175.
Exercise 17.26. Let u and v be the endpoints of a maximum path P . Show that the
graph (VP , EP ∪ ∂(u) ∪ ∂(v)) has a Hamiltonian circuit.
Exercise 18.6. See exercises 1.110 and 18.8.
Exercise 18.7. See exercises 1.110, 1.199 and 18.6.
Exercise 18.19. If there are no odd-degree vertices, it suffices to find an Eulerian

cycle. If there are only two odd-degree vertices, it suffices to consider a minimum-
length path between those vertices. If there are more than two odd-degree vertices,
use the minimum-weight matching algorithm (exercise 11.17) to choose paths con-
necting odd vertices in pairs.
Exercise 19.6. Follows from 19.7 and 1.250.
Exercise 19.7. This is a generalization of exercise 19.6. See exercises 1.250

and 1.251.

FEOFILOFF Hints for some of the exercises 153

FEOFILOFF 154
Appendix B
The Greek alphabet
Just as other areas of mathematics, graph theory resorts to the Greek alphabet for
some of its notation:
α A alpha ν N nu
β B beta ξ Ξ xi
γ Γ gamma o O omicron
δ ∆ delta π Π pi
ε E epsilon ρ P rho
ζ Z zeta σ Σ sigma
η H eta τ T tau
θ Θ theta υ Υ upsilon
ι I iota ϕ Φ phi
κ K kappa χ X chi
λ Λ lambda ψ Ψ psi
µ M mu ω Ω omega
The symbol ∂ does not belong to the Greek alphabet. It is used, in this text, to
denote cuts (see section 1.8).
155
FEOFILOFF 156
Bibliography
[BM76] J.A. Bondy and U.S.R. Murty. Graph Theory with Applica-
tions. Macmillan/Elsevier, 1976. http://www.freetechbooks.
com/graph-theory-with-applications-t559.html. 5
[BM08] J.A. Bondy and U.S.R. Murty. Graph Theory. Graduate Texts in
Mathematics 244. Springer, 2008. 5, 18
[Bol98] B. Bollobás. Modern Graph Theory. Springer, 1998. 5
[Car11] D.M. Cardoso. Teoria dos Grafos e Aplicações. Internet: http:
//arquivoescolar.org/handle/arquivo-e/78, 2011.
[Die00] R. Diestel. Graph Theory. Springer, 2nd edition, 2000. http://
diestel-graph-theory.com/index.html. 5
[Die05] R. Diestel. Graph Theory. Springer, 3rd edition, 2005. http://
diestel-graph-theory.com/index.html. 5, 8, 18
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide
to the Theory of NP-Completeness. W.H. Freeman, 1979. 5, 137
[Har92] D. Harel. Algorithmics: The Spirit of Computing. Addison-Wesley,
2nd edition, 1992. 5, 137
[JNC10] D. Joyner, M.V. Nguyen, and N. Cohen. Algorithmic Graph Theory.
Google Code, 2010. [eBook].
[Knu93] D.E. Knuth. The Stanford GraphBase: A Platform for Combinatorial
Computing. ACM Press and Addison-Wesley, 1993. 12
[Lov93] L. Lovász. Combinatorial Problems and Exercises. North-Holland,
second edition, 1993. 5
[LP86] L. Lovász and M.D. Plummer. Matching Theory, volume 29 of
Annals of Discrete Mathematics. North-Holland, 1986. 5
[Luc79] C.L. Lucchesi. Introdução à Teoria dos Grafos. 12o. Colóquio Brasi-
leiro de Matemática. IMPA (Instituto de Matemática Pura e Apli-
cada), 1979. 5
157
FEOFILOFF BIBLIOGRAPHY 158
[MST+ 98] O. Melnikov, V. Sarvanov, R. Tyshkevich, V. Yemelichev, and

I. Zverovich. Exercises in Graph Theory, volume 19 of Kluwer Texts
in the Mathematical Sciences. Kluwer, 1998. 5
[OPG] Open Problem Garden. Internet: http://garden.irmacs.sfu.ca/.

Hosted by Simon Fraser University.
[Per09] J.M.S. Simões Pereira. Matemática Discreta: Grafos, Redes, Apli-

cações. Luz da Vida, Coimbra, Portugal, 2009. 20
[Sch03] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency.

Springer, 2003. 117
[Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Publish-

ing, 1997. http://www-math.mit.edu/~sipser/book.html. 5, 137
[vL90] J. van Leeuwen. Graph algorithms. In J. van Leeuwen, editor,

Algorithms and Complexity, volume A of Handbook of Theoretical
Computer Science, pages 527–631. Elsevier and MIT Press, 1990.
[Wil79] R.J. Wilson. Introduction to Graph Theory. Academic Press, 2nd

edition, 1979. 5
[Zha97] C.-Q. Zhang. Integer Flows and Cycle Covers of Graphs. Marcel
Dekker, 1997.
Index
bxc, 10, 36 ∆(G), 17

dxe, 74 κ(G), 131
V (2) , 8 κ 0 (G), 127
Adj , 17 µ(G), 17
VG , 8 o(G), 107
EG , 8 χ(G), 83
n(G), 8 χ 0 (G), 111
m(G), 8 ω(G), 77
c(G), 37 ∂(X), 27
d(v), 17 ∇(X), 27
d(X), 27
G, 8 α(G), 71
Kn , 8 α 0 (G), 95
Kp,q , 15 acyclic, 117
Qk , 12 adjacency matrix, 9
L(G), 14 adjacent, 8
N(v), 17 edges, 14, 95
N(X), 28 vertices, 8
X ⊂ Y , 24 algorithm
Y ⊃ X, 24 approximation, 82
A ⊕ B, 28 greedy, 73, 86, 89, 113
G ⊆ H, 24 Hungarian, 103
G ∪ H, 22 Kruskal, 119
G ∩ H, 22 max-flow min-cut, 126
G[X], 24 Prim, 119
G∼ = H, 59 alkanes, 9
G(n), 57 almost every, 57
G − v, 24 alternating path, 95
G − X, 24 Appel, 91
G − e, 24 approximation algorithm, 82, 99
G − A, 24 articulation, 43
α(G), 71 augmenting path, 96
α 0 (G), 95
β(G), 81
β(G), 81
Barnette, 138
γ(G, S), 108
Berge, 93
δ(G), 17
BFS, 122
δ(X), 27
159
FEOFILOFF INDEX 160
bicolorable, 67 of faces, 91
bicoloring, 67 of vertices, 83
biconnected, 43, 131 k-coloring, 83
edge-, 42 comparability, 14
bipartite, 15 complement, 8
complete, 15 complete, 8
bipartition, 15 component, 37
of a set, 67 conjecture
bishop (chess), 11 Barnette, 138
Bollobás, 5 Berge, 93
boundary of a face, 52 Chvátal, 136
breadth-first search, 122 circuit double cover, 143
bridge, 40 Hadwiger, 92
connected, 34
c(G), 37 k-connected, 131
Catlin, 85 connectivity, 127, 131
center, 123 connector, 117
certificate, 68, 87, 98, 108, 126, 130, 140 connects u to v, 20
chess board, 10 cover, 81
child of a vertex, 45 vertex, 81
Chinese postman, 142 covering
chromatic by circuits, 139
index, 111 cube, 12
number, 83 k-cube, 12
Chudnovsky, 93 cut, 27
Chvátal, 136 edge, 40
circuit, 20 vertex, 43
cover, 139 cycle, 33, 141
decomposition, 139
double cover, 143 D, 6
even, 69 δ(G), 17
minimum, 121 δ(X), 27
odd, 69 ∆(G), 17
circumference, 133 d(v), 17
clique, 77 d(X), 27
cover, 84 ∂(X), 27
number, 77 degree
closed average, 17
trail, 141 maximum, 17
walk, 33 minimum, 17
coboundary, 27 of a face, 52
collection, 57 of a set of vertices, 27
color exchange heuristic, 114 of a vertex, 17
colorable, 83 sequence, 65
k-colorable, 83 diameter, 124
coloring Dirac, 132, 136, 147
minimum, 83, 111 disjoint graphs, 22
FEOFILOFF INDEX 161
dist( ), 121 Gallai, 66, 88, 108

distance, 121 girth, 121
tree, 122 graph, 8
dual of plane map, 53 acyclic, 45
bicolorable, 67
E, 6 biconnected, 43, 131
◦ E, 6 bipartite, 15
! E, 6 bishop, 11
!! E, 6 Catlin, 85
? E, 6 k-colorable, 83
?! E, 6 comparability, 14
?◦ E, 6 complement, 8
. E, 6 complete, 8
E ♥, 6 complete bipartite, 15
EG , 8 cubic, 17
eccentricity, 123 dual, 53
edge, 8 edge-biconnected, 42, 127
coloring, 111 empty, 8
cover, 109 grid, 10
endpoints, 8 Heawood, 31, 123
edge-biconnected, 42, 127 interval, 14
k-edge-connected, 127 king, 12
edge-connectivity, 127 Kneser, 12
edges knight, 11
adjacent, 14, 95 line, 14
multiple, 53 of a plane map, 51
parallel, 53 of a square matrix, 13
Edmonds, 108 of Europe, 13
Egerváry, 102 of the faces, 53
empty graph, 8 outerplanar, 56
endpoints, 8, 20 perfect, 93
Erdős, 66, 115 Petersen, 12
Euler, 54, 141 planar, 23, 52
Eulerian plane, 51
cycle, 141 queen, 10
trail, 141 random, 57
Euler’s formula, 54 regular, 17
even girth, 123 rook, 11
Turán, 75
face of a map, 52
words, 12
flow, 125
graph design, 65
internally disjoint, 129
graphic
forest, 45
sequence, 65
fringe, 27
greedy, 73, 86, 113
γ(G, S), 108 grid, 10
G(n), 57
Hadwiger, 92
FEOFILOFF INDEX 162
Hajós, 92 lines (of a plane map), 51

Haken, 91 longest
Hall, 104 circuit, 133
Hamilton, 133 path, 133
Hamiltonian loop, 8, 53
circuit, 133 Lovász, 5, 12, 93
path, 133
Heawood, 31, 123 m(G), 8
hexagon, 20 µ(G), 17
hydrocarbons, 9 matching, 95
maximum weight, 109
incidence matrix, 9 perfect, 95
incident, 8 matrix
independence number, 71 adjacency, 9
independent set, 71 incidence, 9
induced subgraph, 24 maximal, 71, 95
induction, 24, 134 maximal vs maximum, 30, 71, 95, 117
internal vertex, 20, 129 maximum, 25, 71, 95
internally disjoint, 43, 129 flow, 125
intersection of graphs, 22 Menger, 126, 130
interval, 14 minimal vs minimum, 117
isolated (vertex), 17 minor, 48
isolator, 29 multiple edges, 8, 53
isomorphism, 59
isthmus, 40 n(G), 8
N(v), 17
Kn , 8 N(X), 28
Kp,q , 15 neighbor, 8
Kn , 8 neighborhood, 17
κ(G), 131 NP-complete, 5
κ 0 (G), 127 NP-hard, 5
king (chess), 12 number of colors, 83, 111
Kirkman, 133
Kneser, 12 o(G), 107
knight (chess), 11 ω(G), 77
Kőnig, 102, 114 odd
Kruskal, 119 circuit, 67
Kuratowski, 146 component, 107
girth, 123
L(G), 14 hole, 93
leaf, 45 origin of walk, 32
length outerplanar, 56
of a circuit, 20
parallel edges, 8, 53
of a path, 20
parent of a vertex, 45
of a trail, 32
parity, 69
of a walk, 32, 141
partial order, 14
line graph, 14
partition, 15
FEOFILOFF INDEX 163
path, 20 star, 15
endpoints, 20 subcontraction, 48
even, 69 subdivision, 49
maximal, 30 subgraph, 24
maximum, 30 maximal, 37
odd, 69 subpartition, 48
pentagon, 20 support of a plane map, 52
perfect symmetric difference, 28, 97
elimination scheme, 87 Szekeres, 143
graph, 93
terminus of walk, 32
matching, 95
theorem
permutation, 20, 45
Berge, 97
Petersen, 12
Brooks, 87
planar, 23, 52, 145
Dirac, 132, 136
plane map, 51
Erdős and Gallai, 66
points (of a plane map), 51
Euler, 140
Prim, 119
Four Color, 91
problem
Gallai & Roy, 88
Chinese postman, 142
Hall, 104
traveling salesman, 137
Havel and Hakimi, 66
proper subgraph, 24
Kőnig, 114
Qk , 12 Kőnig–Egerváry, 102
queen (chess), 10 Kuratowski, 146
Menger, 126, 130
radius, 123 Turán, 75
random, 57 Tutte, 107, 137
regular, 17 Tutte–Berge, 108
Robertson, 91, 93 Veblen, 140
rook (chess), 11 Vizing, 115
root of a tree, 45 Wagner, 146
Roy, 88 Thomas, 91, 93
topological minor, 48
saturated vertex, 95 trail, 32, 141
self-complementary, 62 traveling salesman, 137
separates, 32, 125, 129 tree, 45
separator, 129 triangle, 20
Seymour, 91, 93, 143 triangle inequality, 122
shortest path, 121 trivial cut, 27
simple graph, 8 TSP, 137
slither, 98 Turán, 75
spanning Tutte, 107, 137
subgraph, 24
tree, 117 union of graphs, 22
square, 20 unordered pair, 8
stability number, 71 uses k colors, 83
stable set, 71
VG , 8
FEOFILOFF INDEX 164
vertex, 8
cover, 81
isolated, 17
Wagner, 146
walk, 32, 141
closed, 33
from v to w, 32, 141
origin, 32
simple, 32
terminus, 32
weight of an edge, 109, 119
wheel, 22
Wilson, 115
words, 12
χ(G), 83
χ 0 (G), 111
Younger, 5

FJKL

Uploaded by

Copyright:

Available Formats

FJKL

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

FJKL

Uploaded by

Copyright:

Available Formats

Graph Theory Exercises

translated into English by

March 14, 2019

3 Graph design with given degrees 65

10 Matchings in bipartite graphs 101

11 Matchings in arbitrary graphs 107

12 Edge coloring 111

13 Connectors and acyclic sets 117

14 Minimum paths and circuits 121

16 Internally disjoint flow 129

17 Hamiltonian circuits and paths 133

18 Circuit covers 139

19 Characterization of planarity 145

A Hints for some of the exercises 149

B The Greek alphabet 155

Organization. Chapter 1 deals with basic concepts. Each of the other

Classification of the exercises. Most exercises have a generic prefix E. Some

◦E ... particularly easy drill

Acknowledgments. I am thankful to Rogério Brito for solving various ty-

IME–USP, São Paulo, January 2013

I am thankful to Murilo Santos de Lima for the excellent translation of

IME–USP, São Paulo, March 2019

E XAMPLE : the vertices of the graph are t, u, v, w, x, y, z and

According to our definition, a graph cannot have two different edges

n(G) := |VG | and m(G) := |EG | .

E 1.2 Draw a figure of a K5 and another of a K5 . How many edges does a Kn

1 if u is one of the endpoints of e ,

Figure 1.2: A 3-by-4 grid (see exercise 1.6).

(0, 2) (1, 2) (2, 2)

Write the adjacency and incidence matrices of the graph.

E 1.22 Consider k intervals of finite length, I1 , I2 , . . . , Ik , on the real line. Let

E 1.23 Let  be a partial order relation on a finite set V . Therefore, the

Figure 1.4: A graph (left) and its line graph (right).

1.2 Bipartite graphs

Figure 1.5: A complete bipartite graph.

◦ E 1.26 How many edges can a {U, W }-bipartite graph have?

E 1.29 Is it true that the t-by-t knight graph is bipartite?

E 1.30 What is the shape of the adjacency matrix of a bipartite graph?

1.3 Neighborhoods and vertex degrees

◦ E 1.34 For r = 1, 2, 3, draw a figure of an r-regular graph with 12 vertices.

Figure 1.6: Petersen graph. See exercises 1.15 and 1.36.

. E 1.40 Let G be a {U, W }-bipartite graph. Suppose G is r-regular, with

◦ E 1.43 Show that µ(G) = 2m(G)/n(G) for every graph G.

E 1.45 Show that every graph has δ ≤ 2m/n ≤ ∆.

E 1.51 How many edges does the k-dimensional cube have?

E 1.53 Let G be the complement of graph G. Calculate δ(G) and ∆(G) as a

1.4 Paths and circuits

Figure 1.7: A path and a circuit.

The length of a path20 or circuit G is the number m(G). Of course, a path

◦ E 1.59 Draw a figure of the path 1 2 4 3 5. Draw a figure of the path 1 3 2 4 3 5.

◦ E 1.60 Verify that the path u v w x y z can also be denoted by z y x w v u.

◦ E 1.61 Consider the circuit u v w x y z u. Show that z y x w v u z is also a cir-

◦ E 1.63 Is it true that the 3-by-3 knight graph is a circuit?

◦ E 1.65 Suppose that P is a path of length n − 1 and O is a circuit of length n.

◦ E 1.66 Draw a figure of the complement of a path of length 3. Draw a figure

E 1.68 Is it true that every 2-regular graph is a circuit?

E 1.69 Let G be a graph with n(G) ≥ 3, ∆(G) = 2 and δ(G) = 1. If G has

1.5 Union and intersection of graphs

E 1.23 Let be a partial order relation on a finite set V . Therefore, the