,i ii
INTRODUCTION TO GRAPH THEORY
NOTICE
This is the Summer 2005 version of the Instructor’s Solution Manual for
SECOND EDITION (2001) Introduction to Graph Theory, by Douglas B. West. A few solutions have
been added or clarified since last year’s version.
Also present is a (slightly edited) annotated syllabus for the one-
semester course taught from this book at the University of Illinois.
This version of the Solution Manual contains solutions for 99.4% of
the problems in Chapters 1–7 and 93% of the problems in Chapter 8. The
SOLUTION MANUAL author believes that only Problems 4.2.10, 7.1.36, 7.1.37, 7.2.39, 7.2.47,
and 7.3.31 in Chapters 1–7 are lacking solutions here. There problems are
too long or difficult for this text or use concepts not covered in the text; they
will be deleted in the third edition.
The positions of solutions that have not yet been written into the files
SUMMER 2005 VERSION are occupied by the statements of the corresponding problems. These prob-
c DOUGLAS B. WEST lems retain the (−), (!), (+), (∗) indicators. Also (•) is added to introduce
the statements of problems without other indicators. Thus every problem
whose solution is not included is marked by one of the indicators, for ease
of identification.
The author hopes that the solutions contained herein will be useful to
instructors. The level of detail in solutions varies. Instructors should feel
free to write up solutions with more or less detail according to the needs of
the class. Please do not leave solutions posted on the web.
MATHEMATICS DEPARTMENT Due to time limitations, the solutions have not been proofread or edited
as carefully as the text, especially in Chapter 8. Please send corrections to
UNIVERSITY OF ILLINOIS . The author thanks Fred Galvin in particular for con-
tributing improvements or alternative solutions for many of the problems
in the earlier chapters.
This will be the last version of the Solution Manual for the second
All rights reserved. No part of this work may be reproduced edition of the text. The third edition will have many new problems, such
as those posted at http://www.math.uiuc.edu/ west/igt/newprob.html . The
or transmitted in any form without permission. effort to include all solutions will resume for the third edition. Possibly
other pedagogical features may also be added later.
Inquiries may be sent to . Meanwhile, the author
apologizes for any inconvenience caused by the absence of some solutions.
Douglas B. West
,1 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 2
1.1.5. If every vertex of a graph G has degree 2, then G is a cycle—FALSE.
Such a graph can be a disconnected graph with each component a cycle. (If
infinite graphs are allowed, then the graph can be an infinite path.)
1.FUNDAMENTAL CONCEPTS 1.1.6. The graph below decomposes into copies of P4 .
• •
• •
1.1. WHAT IS A GRAPH? • •
1.1.1. Complete bipartite graphs and complete graphs. The complete bipar- 1.1.7. A graph with more than six vertices of odd degree cannot be decom-
tite graph K m,n is a complete graph if and only if m = n = 1 or {m, n} = {1, 0}. posed into three paths. Every vertex of odd degree must be the endpoint
of some path in a decomposition into paths. Three paths have only six
1.1.2. Adjacency matrices and incidence matrices for a 3-vertex path. endpoints.
0 1 1 0 1 0 0 0 1
! ! !
1 0 0 1 0 1 0 0 1 1.1.8. Decompositions of a graph. The graph below decomposes into copies
1 0 0 0 1 0 1 1 0 of K 1,3 with centers at the marked vertices. It decomposes into bold and
solid copies of P4 as shown.
1 1 1 1 1 0 0 1 1 0 0 1
! ! ! ! ! !
1 0 0 1 1 1 1 1 0 1 1 0 • •
0 1 1 0 0 1 1 0 1 1 1 1
• •
Adjacency matrices for a path and a cycle with six vertices.
• •
0 1 0 0 0 0 0 1 0 0 0 1
1 0 1 0 0 0 1 0 1 0 0 0 • •
0 1 0 1 0 0 0 1 0 1 0 0
0 0 1 0 1 0 0 0 1 0 1 0
1.1.9. A graph and its complement. With vertices labeled as shown, two
0 0 0 1 0 1 0 0 0 1 0 1
vertices are adjacent in the graph on the right if and only if they are not
0 0 0 0 1 0 1 0 0 0 1 0
adjacent in the graph on the left.
1.1.3. Adjacency matrix for K m,n .
b• •c f • •d
m n
f g h b
• • • •
m 0 1
• • • •
n 1 0 e h c e
a• •d a• •g
1.1.4. G ∼
= H if and only if G ∼= H . If f is an isomorphism from G to H ,
then f is a vertex bijection preserving adjacency and nonadjacency, and 1.1.10. The complement of a simple disconnected graph must be connected—
hence f preserves non-adjacency and adjacency in G and is an isomor- TRUE. A disconnected graph G has vertices x, y that do not belong to a
phism from G to H . The same argument applies for the converse, since the path. Hencex and y are adjacent in G . Furthermore, x and y have no com-
complement of G is G . mon neighbor in G , since that would yield a path connecting them. Hence
, 3 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 4
every vertex not in {x, y} is adjacent in G to at least one of {x, y}. Hence color. Each pair of adjacent squares has one of each color, so the remaining
every vertex can reach every other vertex in G using paths through {x, y}. squares cannot be partitioned into sets of this type.
Generalization: the two partite sets of a bipartite graph cannot be
1.1.11. Maximum clique and maximum independent set. Since two ver-
matched up using pairwise-disjoint edges if the two partite sets have un-
tices have degree 3 and there are only four other vertices, there is no clique
equal sizes.
of size 5. A complete subgraph with four vertices is shown in bold.
Since two vertices are adjacent to all others, an independent set con- 1.1.15. Common graphs in four families: A = {paths}, B = {cycles}, C =
taining either of them has only one vertex. Deleting them leaves P4 , in {complete graphs}, D = {bipartite graphs}.
which the maximum size of an independent set is two, as marked. A ∩ B = ∅: In a cycle, the numbers of vertices and edges are equal,
but this is false for a path.
•
A ∩ C = {K 1 , K 2 }: To be a path, a graph must contain no cycle.
• • • • A ∩ D = A: non-bipartite graphs have odd cycles.
B ∩ C = K 3 : Only when n = 3 does 2n = n .
• B ∩ D = {C 2k : k ≥ 2}: odd cycles are not bipartite.
C ∩ D = {K 1 , K 2 }: bipartite graphs cannot have triangles.
1.1.12. The Petersen graph. The Petersen graph contains odd cycles, so it
is not bipartite; for example, the vertices 12, 34, 51, 23, 45 form a 5-cycle. 1.1.16. The graphs below are not isomorphic. The graph on the left has four
cliques of size 4, and the graph on the right has only two. Alternatively, the
The vertices 12, 13, 14, 15 form an independent set of size 4, since any
complement of the graph on the left is disconnected (two 4-cycles), while
two of these vertices have 1 as a common element and hence are nonadja-
the complement of the graph on the right is connected (one 8-cycle).
cent. Visually, there is an independent set of size 4 marked on the drawing
of the Petersen graph on the cover of the book. There are many ways to • • • •
show that the graph has no larger independent set.
Proof 1. Two consecutive vertices on a cycle cannot both appear in an • • • •
independent set, so every cycle contributes at most half its vertices. Since
the vertex set is covered by two disjoint 5-cycles, every independent set has • • • •
size at most 4.
• • • •
Proof 2. Let ab be a vertex in an independent set S , where a, b ∈ [5].
We show that S has at most three additional vertices. The vertices not
adjacent to ab are ac, bd, ae, bc, ad, be, and they form a cycle in that order. 1.1.17. There are exactly two isomorphism classes of 4-regular simple
Hence at most half of them can be added to S . graphs with 7 vertices. Simple graphs G and H are isomorphic if and
only if their complements G and H are isomorphic, because an isomor-
1.1.13. The graph with vertex set {0, 1}k and x ↔ y when x and y differ in phism φ : V (G) → V (H ) is also an isomorphism from G to H , and vice
one place is bipartite. The partite sets are determined by the parity of the versa. Hence it suffices to count the isomorphism classes of 2-regular sim-
number of 1’s. Adjacent vertices have opposite parity. (This graph is the ple graphs with 7 vertices. Every component of a finite 2-regular graph is a
k -dimensional hypercube; see Section 1.3.) cycle. In a simple graph, each cycle has at least three vertices. Hence each
class it determined by partitioning 7 into integers of size at least 3 to be
1.1.14. Cutting opposite corner squares from an eight by eight checkerboard the sizes of the cycles. The only two graphs that result are C 7 and C 3 + C4
leaves a subboard that cannot be partitioned into rectangles consisting of – a single cycle or two cycles of lengths three and four.
two adjacent unit squares. 2-coloring the squares of a checkerboard so
that adjacent squares have opposite colors shows that the graph having 1.1.18. Isomorphism. Using the correspondence indicated below, the first
a vertex for each square and an edge for each pair of adjacent squares two graphs are isomorphic; the graphs are bipartite, with u i ↔ v j if and
is bipartite. The squares at opposite corners have the same color; when only if i 6= j . The third graph contains odd cycles and hence is not isomor-
these are deleted, there are 30 squares of that color and 32 of the other phic to the others.
INTRODUCTION TO GRAPH THEORY
NOTICE
This is the Summer 2005 version of the Instructor’s Solution Manual for
SECOND EDITION (2001) Introduction to Graph Theory, by Douglas B. West. A few solutions have
been added or clarified since last year’s version.
Also present is a (slightly edited) annotated syllabus for the one-
semester course taught from this book at the University of Illinois.
This version of the Solution Manual contains solutions for 99.4% of
the problems in Chapters 1–7 and 93% of the problems in Chapter 8. The
SOLUTION MANUAL author believes that only Problems 4.2.10, 7.1.36, 7.1.37, 7.2.39, 7.2.47,
and 7.3.31 in Chapters 1–7 are lacking solutions here. There problems are
too long or difficult for this text or use concepts not covered in the text; they
will be deleted in the third edition.
The positions of solutions that have not yet been written into the files
SUMMER 2005 VERSION are occupied by the statements of the corresponding problems. These prob-
c DOUGLAS B. WEST lems retain the (−), (!), (+), (∗) indicators. Also (•) is added to introduce
the statements of problems without other indicators. Thus every problem
whose solution is not included is marked by one of the indicators, for ease
of identification.
The author hopes that the solutions contained herein will be useful to
instructors. The level of detail in solutions varies. Instructors should feel
free to write up solutions with more or less detail according to the needs of
the class. Please do not leave solutions posted on the web.
MATHEMATICS DEPARTMENT Due to time limitations, the solutions have not been proofread or edited
as carefully as the text, especially in Chapter 8. Please send corrections to
UNIVERSITY OF ILLINOIS . The author thanks Fred Galvin in particular for con-
tributing improvements or alternative solutions for many of the problems
in the earlier chapters.
This will be the last version of the Solution Manual for the second
All rights reserved. No part of this work may be reproduced edition of the text. The third edition will have many new problems, such
as those posted at http://www.math.uiuc.edu/ west/igt/newprob.html . The
or transmitted in any form without permission. effort to include all solutions will resume for the third edition. Possibly
other pedagogical features may also be added later.
Inquiries may be sent to . Meanwhile, the author
apologizes for any inconvenience caused by the absence of some solutions.
Douglas B. West
,1 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 2
1.1.5. If every vertex of a graph G has degree 2, then G is a cycle—FALSE.
Such a graph can be a disconnected graph with each component a cycle. (If
infinite graphs are allowed, then the graph can be an infinite path.)
1.FUNDAMENTAL CONCEPTS 1.1.6. The graph below decomposes into copies of P4 .
• •
• •
1.1. WHAT IS A GRAPH? • •
1.1.1. Complete bipartite graphs and complete graphs. The complete bipar- 1.1.7. A graph with more than six vertices of odd degree cannot be decom-
tite graph K m,n is a complete graph if and only if m = n = 1 or {m, n} = {1, 0}. posed into three paths. Every vertex of odd degree must be the endpoint
of some path in a decomposition into paths. Three paths have only six
1.1.2. Adjacency matrices and incidence matrices for a 3-vertex path. endpoints.
0 1 1 0 1 0 0 0 1
! ! !
1 0 0 1 0 1 0 0 1 1.1.8. Decompositions of a graph. The graph below decomposes into copies
1 0 0 0 1 0 1 1 0 of K 1,3 with centers at the marked vertices. It decomposes into bold and
solid copies of P4 as shown.
1 1 1 1 1 0 0 1 1 0 0 1
! ! ! ! ! !
1 0 0 1 1 1 1 1 0 1 1 0 • •
0 1 1 0 0 1 1 0 1 1 1 1
• •
Adjacency matrices for a path and a cycle with six vertices.
• •
0 1 0 0 0 0 0 1 0 0 0 1
1 0 1 0 0 0 1 0 1 0 0 0 • •
0 1 0 1 0 0 0 1 0 1 0 0
0 0 1 0 1 0 0 0 1 0 1 0
1.1.9. A graph and its complement. With vertices labeled as shown, two
0 0 0 1 0 1 0 0 0 1 0 1
vertices are adjacent in the graph on the right if and only if they are not
0 0 0 0 1 0 1 0 0 0 1 0
adjacent in the graph on the left.
1.1.3. Adjacency matrix for K m,n .
b• •c f • •d
m n
f g h b
• • • •
m 0 1
• • • •
n 1 0 e h c e
a• •d a• •g
1.1.4. G ∼
= H if and only if G ∼= H . If f is an isomorphism from G to H ,
then f is a vertex bijection preserving adjacency and nonadjacency, and 1.1.10. The complement of a simple disconnected graph must be connected—
hence f preserves non-adjacency and adjacency in G and is an isomor- TRUE. A disconnected graph G has vertices x, y that do not belong to a
phism from G to H . The same argument applies for the converse, since the path. Hencex and y are adjacent in G . Furthermore, x and y have no com-
complement of G is G . mon neighbor in G , since that would yield a path connecting them. Hence
, 3 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 4
every vertex not in {x, y} is adjacent in G to at least one of {x, y}. Hence color. Each pair of adjacent squares has one of each color, so the remaining
every vertex can reach every other vertex in G using paths through {x, y}. squares cannot be partitioned into sets of this type.
Generalization: the two partite sets of a bipartite graph cannot be
1.1.11. Maximum clique and maximum independent set. Since two ver-
matched up using pairwise-disjoint edges if the two partite sets have un-
tices have degree 3 and there are only four other vertices, there is no clique
equal sizes.
of size 5. A complete subgraph with four vertices is shown in bold.
Since two vertices are adjacent to all others, an independent set con- 1.1.15. Common graphs in four families: A = {paths}, B = {cycles}, C =
taining either of them has only one vertex. Deleting them leaves P4 , in {complete graphs}, D = {bipartite graphs}.
which the maximum size of an independent set is two, as marked. A ∩ B = ∅: In a cycle, the numbers of vertices and edges are equal,
but this is false for a path.
•
A ∩ C = {K 1 , K 2 }: To be a path, a graph must contain no cycle.
• • • • A ∩ D = A: non-bipartite graphs have odd cycles.
B ∩ C = K 3 : Only when n = 3 does 2n = n .
• B ∩ D = {C 2k : k ≥ 2}: odd cycles are not bipartite.
C ∩ D = {K 1 , K 2 }: bipartite graphs cannot have triangles.
1.1.12. The Petersen graph. The Petersen graph contains odd cycles, so it
is not bipartite; for example, the vertices 12, 34, 51, 23, 45 form a 5-cycle. 1.1.16. The graphs below are not isomorphic. The graph on the left has four
cliques of size 4, and the graph on the right has only two. Alternatively, the
The vertices 12, 13, 14, 15 form an independent set of size 4, since any
complement of the graph on the left is disconnected (two 4-cycles), while
two of these vertices have 1 as a common element and hence are nonadja-
the complement of the graph on the right is connected (one 8-cycle).
cent. Visually, there is an independent set of size 4 marked on the drawing
of the Petersen graph on the cover of the book. There are many ways to • • • •
show that the graph has no larger independent set.
Proof 1. Two consecutive vertices on a cycle cannot both appear in an • • • •
independent set, so every cycle contributes at most half its vertices. Since
the vertex set is covered by two disjoint 5-cycles, every independent set has • • • •
size at most 4.
• • • •
Proof 2. Let ab be a vertex in an independent set S , where a, b ∈ [5].
We show that S has at most three additional vertices. The vertices not
adjacent to ab are ac, bd, ae, bc, ad, be, and they form a cycle in that order. 1.1.17. There are exactly two isomorphism classes of 4-regular simple
Hence at most half of them can be added to S . graphs with 7 vertices. Simple graphs G and H are isomorphic if and
only if their complements G and H are isomorphic, because an isomor-
1.1.13. The graph with vertex set {0, 1}k and x ↔ y when x and y differ in phism φ : V (G) → V (H ) is also an isomorphism from G to H , and vice
one place is bipartite. The partite sets are determined by the parity of the versa. Hence it suffices to count the isomorphism classes of 2-regular sim-
number of 1’s. Adjacent vertices have opposite parity. (This graph is the ple graphs with 7 vertices. Every component of a finite 2-regular graph is a
k -dimensional hypercube; see Section 1.3.) cycle. In a simple graph, each cycle has at least three vertices. Hence each
class it determined by partitioning 7 into integers of size at least 3 to be
1.1.14. Cutting opposite corner squares from an eight by eight checkerboard the sizes of the cycles. The only two graphs that result are C 7 and C 3 + C4
leaves a subboard that cannot be partitioned into rectangles consisting of – a single cycle or two cycles of lengths three and four.
two adjacent unit squares. 2-coloring the squares of a checkerboard so
that adjacent squares have opposite colors shows that the graph having 1.1.18. Isomorphism. Using the correspondence indicated below, the first
a vertex for each square and an edge for each pair of adjacent squares two graphs are isomorphic; the graphs are bipartite, with u i ↔ v j if and
is bipartite. The squares at opposite corners have the same color; when only if i 6= j . The third graph contains odd cycles and hence is not isomor-
these are deleted, there are 30 squares of that color and 32 of the other phic to the others.
