TEST BANK FOR Introduction to Graph Theory 2nd Edition By Douglas B. West (Solution Manual).

INTRODUCTION TO GRAPH THEORY
SECOND EDITION (2001)
SOLUTION MANUAL
SUMMER 2005 VERSION

c DOUGLAS B. WEST
MATHEMATICS DEPARTMENT
UNIVERSITY OF 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 1–7 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 1–7 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 3­vertex 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 non­adjacency 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 cycle—FALSE.
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 5­cycle.
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 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 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
k­dimensional 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. 2­coloring 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 pairwise­disjoint 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: non­bipartite 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 4­cycles), while
the complement of the graph on the right is connected (one 8­cycle).













1.1.17. There are exactly two isomorphism classes of 4­regular 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 2­regular sim­
ple graphs with 7 vertices. Every component of a nite 2­regular 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.