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

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.
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 10­cycle in the rightmost graph corresponds to the
intermediate ring in the second graph. Pulling one of the inner 5­cycles 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 5­cycles.
















































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 4­cycle and the others
do not, but it is harder to prove the absence of a 4­cycle 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 4­cycles. In the graph on the left, every vertex appears in only six
4­cycles (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