INTRODUCTION TO GRAPH THEORY
SECOND EDITION (2001)
SOLUTION MANUAL
SUMMER 2005 VERSION
c DOUGLAS B. WEST
MATHEMATICS DEPARTMENT
UNIVERSITY OF
... [Show More] ILLINOIS
All rights reserved. No part of this work may be reproduced
or transmitted in any form without permission.
NOTICE
This is the Summer 2005 version of the Instructor's Solution Manual for
Introduction to Graph Theory, by Douglas B. West. A few solutions have
been added or claried 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 17 and 93% of the problems in Chapter 8. The
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 17 are lacking solutions here. There problems are
too long or difcult 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 les
are occupied by the statements of the corresponding problems. These prob
lems retain the ./, .!/, .C/, ./ 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 identication.
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.
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
[email protected]. 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
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
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 [email protected]. 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.FUNDAMENTAL CONCEPTS
1.1. WHAT IS A GRAPH?
1.1.1. Complete bipartite graphs and complete graphs. The complete bipar
tite graph Km;n is a complete graph if and only if m D n D 1 or fm; ng D f1; 0g.
1.1.2. Adjacency matrices and incidence matrices for a 3vertex path.
0 1 1
1 0 0
1 0 0
!
0 1 0
1 0 1
0 1 0
!
0 0 1
0 0 1
1 1 0
!
1 1
1 0
0 1
!
1 1
0 1
1 0
!
1 0
1 1
0 1
!
0 1
1 1
1 0
!
1 0
0 1
1 1
!
0 1
1 0
1 1
!
Adjacency matrices for a path and a cycle with six vertices.
0
BBBB@
0 1 0 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
1
CCCCA
0
BBBB@
0 1 0 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0
1
CCCCA
1.1.3. Adjacency matrix for Km;n.
m n
m 0 1
n 1 0
1.1.4. G D
H if and only if G D
H. If f is an isomorphism from G to H,
then f is a vertex bijection preserving adjacency and nonadjacency, and
hence f preserves nonadjacency and adjacency in G and is an isomor
phism from G to H. The same argument applies for the converse, since the
complement of G is G.
1.1.5. If every vertex of a graph G has degree 2, then G is a cycleFALSE.
Such a graph can be a disconnected graph with each component a cycle. (If
innite graphs are allowed, then the graph can be an innite path.)
1.1.6. The graph below decomposes into copies of P4.
1.1.7. A graph with more than six vertices of odd degree cannot be decom
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
endpoints.
1.1.8. Decompositions of a graph. The graph below decomposes into copies
of K1;3 with centers at the marked vertices. It decomposes into bold and
solid copies of P4 as shown.
1.1.9. A graph and its complement. With vertices labeled as shown, two
vertices are adjacent in the graph on the right if and only if they are not
adjacent in the graph on the left.
a
b c
d
e
f g
h
a
f d
g
c
h b
e
1.1.10. The complement of a simple disconnected graph must be connected
TRUE. A disconnected graph G has vertices x; y that do not belong to a
path. Hencex and y are adjacent in G. Furthermore, x and y have no com
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 fx; yg is adjacent in G to at least one of fx; yg. Hence
every vertex can reach every other vertex in G using paths through fx; yg.
1.1.11. Maximum clique and maximum independent set. Since two ver
tices have degree 3 and there are only four other vertices, there is no clique
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
taining either of them has only one vertex. Deleting them leaves P4, in
which the maximum size of an independent set is two, as marked.
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 5cycle.
The vertices 12; 13; 14; 15 form an independent set of size 4, since any
two of these vertices have 1 as a common element and hence are nonadja
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 5cycles, every independent set has
size at most 4.
Proof 2. Let ab be a vertex in an independent set S, where a; b 2 [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.
Hence at most half of them can be added to S.
1.1.13. The graph with vertex set f0; 1gk and x $ y when x and y differ in
one place is bipartite. The partite sets are determined by the parity of the
number of 1's. Adjacent vertices have opposite parity. (This graph is the
kdimensional hypercube; see Section 1.3.)
1.1.14. Cutting opposite corner squares from an eight by eight checkerboard
leaves a subboard that cannot be partitioned into rectangles consisting of
two adjacent unit squares. 2coloring the squares of a checkerboard so
that adjacent squares have opposite colors shows that the graph having
a vertex for each square and an edge for each pair of adjacent squares
is bipartite. The squares at opposite corners have the same color; when
these are deleted, there are 30 squares of that color and 32 of the other
color. Each pair of adjacent squares has one of each color, so the remaining
squares cannot be partitioned into sets of this type.
Generalization: the two partite sets of a bipartite graph cannot be
matched up using pairwisedisjoint edges if the two partite sets have un
equal sizes.
1.1.15. Common graphs in four families: A D fpathsg, B D fcyclesg, C D
fcomplete graphsg, D D fbipartite graphsg.
A \ B D ?: In a cycle, the numbers of vertices and edges are equal,
but this is false for a path.
A \ C D fK1; K2g: To be a path, a graph must contain no cycle.
A \ D D A: nonbipartite graphs have odd cycles.
B \ C D K3: Only when n D 3 does
n2
D n.
B \ D D fC2k : k 2g: odd cycles are not bipartite.
C \ D D fK1; K2g: bipartite graphs cannot have triangles.
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
complement of the graph on the left is disconnected (two 4cycles), while
the complement of the graph on the right is connected (one 8cycle).
1.1.17. There are exactly two isomorphism classes of 4regular simple
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
phism : V.G/ ! V.H/ is also an isomorphism from G to H, and vice
versa. Hence it sufces to count the isomorphism classes of 2regular sim
ple graphs with 7 vertices. Every component of a nite 2regular graph is a
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
the sizes of the cycles. The only two graphs that result are C7 and C3 C C4
a single cycle or two cycles of lengths three and four.
1.1.18. Isomorphism. Using the correspondence indicated below, the rst
two graphs are isomorphic; the graphs are bipartite, with ui $ vj if and
only if i 6D j . The third graph contains odd cycles and hence is not isomor
phic to the others.
5 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 6
v2 u4
u1 v3
u3 v1
v4 u2
u4
u3
u2
u1
v4
v3
v2
v1
Visually, the rst two graphs are Q3 and the graph obtained by delet
ing four disjoint edges from K4;4. In Q3, each vertex is adjacent to the
vertices whose names have opposite parity of the number of 1s, except for
the complementary vertex. Hence Q3 also has the structure of K4;4 with
four disjoint edges deleted; this proves isomorphism without specifying an
explicit bijection.
1.1.19. Isomorphism of graphs. The rightmost two graphs below are iso
morphic. The outside 10cycle in the rightmost graph corresponds to the
intermediate ring in the second graph. Pulling one of the inner 5cycles of
the rightmost graph out to the outside transforms the graph into the same
drawing as the second graph.
The graph on the left is bipartite, as shown by marking one partite set.
It cannot be isomorphic to the others, since they contain 5cycles.
1.1.20. Among the graphs below, the rst (F) and third (H) are isomorphic,
and the middle graph (G) is not isomorphic to either of these.
F and H are isomorphic. We exhibit an isomorphism (a bijection from
V.F/ to V.H/ that preserves the adjacency relation). To do this, we name
the vertices of F, write the name of each vertex of F on the corresponding
vertex in H, and show that the names of the edges are the same in H and
F. This proves that H is a way to redraw F. We have done this below using
the rst eight letters and the rst eight natural numbers as names.
To prove quickly that the adjacency relation is preserved, observe that
1; a; 2; b; 3; c; 4; d; 5; e; 6; f; 7; g; 8; h is a cycle in both drawings, and the ad
ditional edges 1c; 2d; 3e; 4 f; 5g; 6h; 7a; 8b are also the same in both draw
ings. Thus the two graphs have the same edges under this vertex corre
spondence. Equivalently, if we list the vertices in this specied order for
the two drawings, the two adjacency matrices are the same, but that is
harder to verify.
G is not isomorphic to F or to H. In F and in H, the numbers form an
independent set, as do the letters. Thus F and H are bipartite. The graph
G cannot be bipartite, since it contains an odd cycle. The vertices above
the horizontal axis of the picture induce a cycle of length 7.
It is also true that the middle graph contains a 4cycle and the others
do not, but it is harder to prove the absence of a 4cycle than to prove the
absence of an odd cycle.
h
2
f
d 8
6
b
4
1
a
7
g
5
e
3
c
a
2
b
3
c
4
d
e 5
6
f
7
g
8
h
1
1.1.21. Isomorphism. Both graphs are bipartite, as shown below by mark
ing one partite set. In the graph on the right, every vertex appears in
eight 4cycles. In the graph on the left, every vertex appears in only six
4cycles (it is enough just to check one). Thus they are not isomorphic.
Alternatively, for every vertex in the right graph there are ve vertices
having common neighbors with it, while in the left graph there are six
such vertices.
1.1.22. Isomorphism of explicit graphs. Among the graphs below,
fG1; G2; G5g are pairwise isomorphic. Also G3 D
G4, and these are not
isomorphic to any of the others. Thus there are exactly two isomorphism
classes represented among these graphs.
To prove these statements, one can present explicit bijections between
vertex sets and verify that these preserve the adjacency relation (such as
by displaying the adjacency matrix, for example). One can also make other
structural arguments. For example, one can move the highest vertex in G3
down into the middle of the picture to obtain G4; from this one can list the
desired bijection.
7 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 8
One can also recall that two graphs are isomorphic if and only if their
complements are isomorphic. The complements of G1, G2, and G5 are cy
cles of length 7, which are pairwise isomorphic. Each of G3 and G4 consists
of two components that are cycles of lengths 3 and 4; these graphs are
isomorphic to each other but not to a 7cycle.
G1 G2 G3 G4 G5
1.1.23. Smallest pairs of nonisomorphic graphs with the same vertex de
grees. For multigraphs, loopless multigraphs, and simple graphs, the re
quired numbers of vertices are 2,4,5; constructions for the upper bounds
appear below. We must prove that these constructions are smallest.
a) general b) loopless c) simple
a) With 1 vertex, every edge is a loop, and the isomorphism class is
determined by the number of edges, which is determined by the vertex
degree. Hence nonisomorphic graphs with the same vertex degrees have
at least two vertices.
b) Every loopless graph is a graph, so the answer for loopless graphs
is at least 2. The isomorphism class of a loopless graph with two vertices
is determined by the number of copies of the edge, which is determined
by the vertex degrees. The isomorphism class of a loopless graph with
three vertices is determined by the edge multiplicities. Let the three vertex
degrees be a; b; c, and let the multiplicities of the opposite edges be x; y; z,
where Since a D y C z, b D x C z, and c D x C y, we can solve for the
multiplicities in terms of the degrees by x D .bCca/=2, y D .aCcb/=2,
and z D .a C b c/=2. Hence the multiplicities are determined by the
degrees, and all loopless graphs with vertex degrees a; b; c are pairwise
isomorphic. Hence nonisomorphic loopless graphs with the same vertex
degrees have at least four vertices.
c) Since a simple graph is a loopless graph, the answer for simple
graphs is at least 4. There are 11 isomorphism classes of simple graphs
with four vertices. For each of 0,1,5, or 6 edges, there is only one isomor
phism class. For 2 edges, there are two isomorphism classes, but they have
different lists of vertex degrees (similarly for 4 edges). For 3 edges, the
three isomorphism classes have degree lists 3111, 2220, and 2211, all dif
ferent. Hence nonisomorphic simple graphs with the same vertex degrees
must have at least ve vertices.
1.1.24. Isomorphisms for the Petersen graph. Isomorphism is proved by
giving an adjacencypreserving bijection between the vertex sets. For picto
rial representations of graphs, this is equivalent to labeling the two graphs
with the same vertex labels so that the adjacency relation is the same
in both pictures; the labels correspond to a permutation of the rows and
columns of the adjacency matrices to make them identical. The various
drawings of the Petersen graph below illustrate its symmetries; the label
ings indicate that these are all the same (unlabeled) graph. The number
of isomorphisms from one graph to another is the same as the number of
isomorphisms from the graph to itself.
45
12
23 13
51
34
41 52
35
24
12
52
23
35
13
51
34
24 41
45
24 51
41
35
12
34
52
13
45
23
12
34
52
13
51 24
23
41
35
45
1.1.25. The Petersen graph has no cycle of length 7. Suppose that the Pe
tersen graph has a cycle C of length 7. Since any two vertices of C are
connected by a path of length at most 3 on C, any additional edge with
endpoints on C would create a cycle of length at most 4. Hence the third
neighbor of each vertex on C is not on C.
9 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 10
Thus there are seven edges from V.C/ to the remaining three vertices.
By the pigeonhole principle, one of the remaining vertices receives at least
three of these edges. This vertex x not on C has three neighbors on C.
For any three vertices on C, either two are adjacent or two have a common
neighbor on C (again the pigeonhole principle applies). Using x, this com
pletes a cycle of length at most 4. We have shown that the assumption of a
7cycle leads to a contradiction.
Alternative completion of proof. Let u be a vertex on C, and let v;w
be the two vertices farthest from u on C. As argued earlier, no edges join
vertices of C that are not consecutive on C. Thus u is not adjacent to v or w.
Hence u; v have a common neighbor off C, as do u;w. Since u has only one
neighbor off C, these two common neighbors are the same. The resulting
vertex x is adjacent to all of u; v;w, and now x; v;w is a 3cycle.
1.1.26. A kregular graph of girth four has at least 2k vertices, with equality
only for Kk;k . Let G be kregular of girth four, and chose x y 2 E.G/. Girth
4 implies that G is simple and that x and y have no common neighbors.
Thus the neighborhoods N.x/ and N.y/ are disjoint sets of size k, which
forces at least 2k vertices into G. Possibly there are others.
Note also that N.x/ and N.y/ are independent sets, since G has no
triangle. If G has no vertices other than these, then the vertices in N.x/
can have neighbors only in N.y/. Since G is kregular, every vertex of N.x/
must be adjacent to every vertex of N.y/. Thus G is isomorphic to Kk;k ,
with partite sets N.x/ and N.y/. In other words, there is only one such
isomorphism class for each value of k.
Comment. One can also start with a vertex x, choose y from among
the k vertices in N.x/, and observe that N.y/ must have k 1 more vertices
not in N.x/ [ fxg. The proof then proceeds as above.
(An alternative proof uses the methods of Section 1.3. A trianglefree
simple graph with n vertices has at most n2=4 edges. Since G is kregular,
this yields n2=4 nk=2, and hence n 2k. Furthermore, equality holds
in the edge bound only for Kn=2;n=2, so this is the only such graph with 2k
vertices. (C. Pikscher))
N.x/ fyg
x
N.y/ fxg
y
1.1.27. A simple graph of girth 5 in which every vertex has degree at least
k has at least k2 C 1 vertices, with equality achieveable when k 2 f2; 3g. Let
G be kregular of girth ve. Let S be the set consisting of a vertex x and
its neighbors. Since G has no cycle of length less than ve, G is simple,
and any two neighbors of x are nonadjacent and have no common neighbor
other than x. Hence each y 2 S fxg has at least k 1 neighbors that
are not in S and not neighbors of any vertex in S. Hence G has at least
k.k 1/ vertices outside S and at least k C1 vertices in S for at least k2 C1
altogether.
The 5cycle achieves equality when k D 2. For k D 3, growing the graph
symmetrically from x permits completing the graph by adding edges among
the nonneighbors of x. The result is the Petersen graph. (Comment: For
k > 3, it is known that girth 5 with minimum degree k and exactly k2 C 1
vertices is impossible, except for k D 7 and possibly for k D 57.)
x
1.1.28. The Odd Graph has girth 6. The Odd Graph Ok is the disjointness
graph of the set of kelement subsets of [2k C 1].
Vertices with a common neighbor correspond to ksets with k 1 com
mon elements. Thus they have exactly one common neighbor, and Ok has
no 4cycle. Two vertices at distance 2 from a single vertex have at least
k 2 common neighbors. For k > 2, such vertices cannot be adjacent, and
thus Ok has no 5cycle when k > 2. To form a 6cycle when k 2, let
A D f2; . . . ; kg, B D fk C2; . . . ; 2kg, a D 1, b D k C1, c D 2k C1. A 6cycle is
A [ fag, B [ fbg, A [ fcg, B [ fag, A [ fbg, B [ fcg.
The Odd Graph also is not bipartite. The successive elements
f1; . . . ; kg, fk C 1; . . . ; 2kg, f2k C 1; 1; . . . ; k 1g, . . ., fk C 2; . . . ; 2k C 1g
form an odd cycle.
1.1.29. Among any 6 people, there are 3 mutual acquaintances or 3 mutual
strangers. Let G be the graph of the acquaintance relation, and let x be one
of the people. Since x has 5 potential neighbors, x has at least 3 neighbors
or at least 3 nonneighbors. By symmetry (if we complement G, we still
have to prove the same statement), we may assume that x has at least 3
neighbors. If any pair of these people are acquainted, then with x we have
3 mutual acquaintances, but if no pair of neighbors of x is acquainted, then
the neighbors of x are three mutual strangers.
1.1.30. The number of edges incident to vi is the ith diagonal entry in MMT
and in A2. In both MMT and A2 this is the sum of the squares of the entries
11 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 12
in the ith [Show Less]