Solution Manual for Graphs & Digraphs 7th Edition by Chartrand 2024 PDF | Complete Step-by-Step Solutions and Worked Examples | Covers Graph Theory Fundamentals, Connectivity, Eulerian and Hamiltonian Graphs, Trees, Planarity, Coloring, Matchings, and Dig

Covers All 21 Chapters




SOLUTIONS MANUAL

, Table of Contents
Preface to the Sixth Edition xi

1. Introduction 1

1.1 Graphs 1
1.2 The Degree of a Vertex 5
1.3 Isomorphic Graphs 7
1.4 Regular Graphs 12
1.5 Bipartite Graphs 13
1.6 Operations on Graphs 16
1.7 Degree Sequences 18
1.8 Multigraphs 25
• Exercises for Chapter 1 28
2. Connected Graphs and Distance 37

2.1 Connected Graphs 37
2.2 Distance in Graphs 44
• Exercises for Chapter 2 51
3. Trees 57

3.1 Nonseparable Graphs 57
3.2 Introduction to Trees 62
3.3 Spanning Trees 69
3.4 The Minimum Spanning Tree Problem 81
• Exercises for Chapter 3 86
4. Connectivity 95

4.1 Connectivity and Edge-Connectivity 95
4.2 Theorems of Menger and Whitney 102
• Exercises for Chapter 4 110
5. Eulerian Graphs 115
5.1 The Königsberg Bridge Problem 115
5.2 Eulerian Circuits and Trails 117
• Exercises for Chapter 5 123
6. Hamiltonian Graphs 125

i

, 6.1 Hamilton’s Icosian Game 125
6.2 Sufficient Conditions for Hamiltonian Graphs 128
6.3 Toughness of Graphs 134
6.4 Highly Hamiltonian Graphs 140
6.5 Powers of Graphs and Line Graphs 145
• Exercises for Chapter 6 154
7. Digraphs 161
7.1 Introduction to Digraphs 161
7.2 Strong Digraphs 166
7.3 Eulerian and Hamiltonian Digraphs 167
7.4 Tournaments 169
7.5 Kings in Tournaments 179
7.6 Hamiltonian Tournaments 180
• Exercises for Chapter 7 184
8. Flows in Networks 191

8.1 Networks 191
8.2 The Max-Flow Min-Cut Theorem 199
8.3 Menger Theorems for Digraphs 207
• Exercises for Chapter 8 212
9. Automorphisms and Reconstruction 217

9.1 The Automorphism Group of a Graph 217
9.2 Cayley Color Graphs 223
9.3 The Reconstruction Problem 228
• Exercises for Chapter 9 235
10. Planar Graphs 239

10.1 The Euler Identity 239
10.2 Maximal Planar Graphs 248
10.3 Characterizations of Planar Graphs 252
10.4 Hamiltonian Planar Graphs 264
• Exercises for Chapter 10 268
11. Nonplanar Graphs 275
11.1 The Crossing Number of a Graph 275

ii

, 11.2 The Genus of a Graph 286
11.3 The Graph Minor Theorem 300
• Exercises for Chapter 11 302
12. Matchings, Independence and Domination 305

12.1 Matchings 305
12.2 1-Factors 310
12.3 Independence and Covers 317
12.4 Domination 322
• Exercises for Chapter 12 329
13. Factorization and Decomposition 335
13.1 Factorization 335
13.2 Decomposition 343
13.3 Cycle Decomposition 345
13.4 Graceful Graphs 351
• Exercises for Chapter 13 358
14. Vertex Colorings 363
14.1 The Chromatic Number of a Graph 363
14.2 Color-Critical Graphs 371
14.3 Bounds for the Chromatic Number 374
• Exercises for Chapter 14 385
15. Perfect Graphs and List Colorings 393
15.1 Perfect Graphs 393
15.2 The Perfect and Strong Perfect Graph Theorems 402
15.3 List Colorings 405
• Exercises for Chapter 15 410
16. Map Colorings 415
16.1 The Four Color Problem 415
16.2 Colorings of Planar Graphs 426
16.3 List Colorings of Planar Graphs 428
16.4 The Conjectures of Ha jós and Hadwiger 434
16.5 Chromatic Polynomials 438
16.6 The Heawood Map-Coloring Problem 444

iii

,iv

• Exercises for Chapter 16 448
17. Edge Colorings 453
17.1 The Chromatic Index of a Graph 453
17.2 Class One and Class Two Graphs 460
17.3 Tait Colorings 467
• Exercises for Chapter 17 476
18. Nowhere-Zero Flows and List Edge Colorings 481
18.1 Nowhere-Zero Flows 481
18.2 List Edge Colorings 491
18.3 Total Colorings 495
• Exercises for Chapter 18 500
19. Extremal Graph Theory 503
19.1 Turán’s Theorem 503
19.2 Extremal Subgraphs 505
19.3 Cages 509
• Exercises for Chapter 19 520
20. Ramsey Theory 523
20.1 Classical Ramsey Numbers 523
20.2 More General Ramsey Numbers 532
• Exercises for Chapter 20 538
21. The Probabilistic Method 543
21.1 The Probabilistic Method 543
21.2 Random Graphs 554
• Exercises for Chapter 21 561
Hints and Solutions to Odd-Numbered Exercises 563
Bibliography 589
Supplemental References 606
Index of Names 607
Index of Mathematical Terms 613
List of Symbols 625

,Chapter 1

Introduction

Section 1.1. Graphs
1. This information can be modeled (or represented) by the graph shown in Figure
1.1, where each small circle indicates a box and a line segment between two
boxes indicates that these two boxes contain at least one wire segment of the
same color.
B B1
.....8
.... ..........
.. .. . . . . . .
. . .. . . . .. .
. . .. . . . . . . .
. . .. .
. . . .. . . ..
.. .... . . .. . .... . ..
. . ... . .... .
. . . ..
.. .. .. . . . .
7 . . ..
. . ..... ......
B . .. . . . . ..
.
. .
. ..
.
.
B
. ..........................................................................................................
. .. .
2
. .
... .... .. . . .. . . .
. ..
. .. . ..
. .. . .. . . .. . ..
..
. . . ... . . ..
.... . .. .. . .. . . . . .
. .. . .. . .. . .. ..
.. ...
. ... .. . .. .... . . .... .
...... . .... . .. . . ....
.. ..
..
. . ... .. . ... B . .
B . . . .
.
. .. . 3
6 . . . .. ..
. .. .
. .. ..
. . . .. . . .. . . .
. .. . . . . . . .
.. . . . .. . . ... . . .
. . . .
.. . . . . . .. .... . .
......... . . ...
. .. .
..
. .

B5 B4

Figure 1.1: The graph in Exercise 1

2. The graph G is shown in Figure 1.2. The degree of ∅ is 7, the degree of each
of {1 }, {2 }and 3
{ }is 4, the degree of each of {1, 2} , {1, 3} and {2, 3} is 2 and
the degree of S is 1. The size of G is 13.

Section 1.2. The Degree of a vertex
3. Denote the degree of the remaining vertices by x. Since there are 8 vertices
of degree x, it follows that ·5 4 + ·6 5 +· 7 6 + 8x =
· 2 58. Thus, x = 3
and so the degree of each remaining vertex is 3.

1

,2 CHAPTER 1. INTRODUCTION

∅
.. .
.......
. .... .
. .
.. . .
...... . . .... .... . . . ......
S .. . .
. ...
.. . . .. .
.. .. . {1}
. .
. . .. .. . . . .
. .. ... .. ...
.... . ..
.. ..... . .
.. . .... .
.. . .
. . . . .. . . ...
. . . . ... .. .......
{2}
..... .
.
.. ..
. .
{2, 3} ..
....
.
. ..
. .... . . .....
. ...
. . . . ..
.. .
... . . ... .. ....
. . . .
..... . . ......
{1, 3} . . . ..
. .
... .
. {3}
.. .. .

{1, 2}

Figure 1.2: The graph G in Exercise 2


4. Proof. Assume, to the contrary, that G has at most k + 2 vertices of de-
gree k + 1, at most k vertices of degree k + 2 and at most k + 1 vertices of
degree k + 3. Since the order of G is n = 3k + 3, it follows that G has
exactly k + 2 vertices of degree k + 1, exactly k vertices of degree k + 2 and
exactly k + 1 vertices of degree k + 3. In each case, G has an odd number
of odd vertices, which is impossible.

5. Proof. Let G be a graph with r vertices of degree r, r + 1 vertices of degree
r +1 and r +2 vertices of degree r +2. Thus, the order of G is 3r +3. First,
we show that r is odd. Assume, to the contrary, that r is even. Then G
contains an odd number r + 1 of odd vertices, which is impossible by
Corollary 1.5. Thus, r is odd and G contains 2r + 2 vertices of odd degree.

6. Let G be the graph of order 2k with V (G) = {u1, u 2, . . . , uk, v1, v2, . . . ,
vk}. For each i with 1 ≤ i ≤ k, join each vertex ui to the i vertices v1, v2, . . . ,
vi. Then deg ui = i and deg vi = k + 1 — i for 1 ≤ i ≤ k.

Section 1.3. Isomorphic Graphs
7. (a) G1 ∼= G2.
∼
(b) H1 =/ H2 . For example, H1 has two vertices of degree 4, while H2 has
three vertices of degree 4.

8. (a) There are 34 such graphs, each of which has size m for some m with
0 ≤ m ≤10. By using complementary graphs the number of graphs of
order 5 and size m equals the number of graphs of order 5 and size 10— m
(see Figure 1.3).
(b) The minimum size of a graph G of order 5 such that every graph of order
5 and size 5 is isomorphic to some subgraph of G is 7. First, observe
that the graph G = P4 ∨ K1 has the desired property. If the minimum
size were 6, then G must consist of a 5-cycle C and an edge joining two

, 3
. ... .
. . ..
.
. . ... . .
.. .
. . .
. . . . . . . .
...
.
.
.
... .
.
. . .
. .
. .. .. .. .. . . .
. ..
. . ..
. . . .
.
...
.
.
. .
. . . . . .
. .
.
. . ..
.
.
. .
.. ..
.
. . . . . . . . . .
..... . . . . .
.
. . . . .. . .
... . . . .
....... .. .
. .. . . ..
.
. . . .
.... . ... .. . . .
.
. .. . . ... . . . .
.. . .. . .. . .
..
.
. . . .
.
. .. .. .
. .. . ... . . .
..
.
. ..
.
..
.
.
... ...
...
.
.. .
.....
..
... . .
.
.
. .
. . . .
.. . . . .. . .
.. .
..
.. .. . .. . . . .
. .. ...
.
.
.
. . ..
. . . .
.
.
..
. .
. .. . .
.
. . . . . . .

.. .. .. .
. . .
.. . . .
.
. . ..
...
. .. .
. . . .. ..
. . .
. .. ...
. . . .. . .. .. .. .. .. . .
.
.
.
.
.
. .
.. ... . ..
.. .
. . . ... . ..
.. . . . .
.



Figure 1.3: Graphs for Exercise 8


nonconsecutive vertices of C. This graph, however, does not have the
desired property.

9. (a) Proof. Let φ : V (G) → V (H) be an isomorphism from G to H.
| | | |
Then S = T and the mapping φ→′ : S T defined φ′(v) = φ(v) for∈all
v S is a bijection from S to T . To show that φ′ is an isomorphism
from G[S] to H[T ], it remains to show that φ′ maps adjacent vertices in
G[S] to adjacent vertices in H[T ] and maps nonadjacent vertices in
G[S] to nonadjacent vertices in H[T ]. Let u, v V (G[S]) = S. Since
∈
G[S] is an induced subgraph of G, it follows that u and v are adjacent in
G[S] if and only if u and v are adjacent in G. Since φ is an
isomorphism from G to H, it follows that u and v are adjacent in G if
and only if φ(u) = φ′(u) and φ(v) = φ′(v) are adjacent in H. Since
(1) φ′(u), φ′(v) T and ∈
(2) H[T ] is an induced subgraph of H, it follows that φ′(u) and φ′(v)
are adjacent in H if and only if φ′(u) and φ′(v) are adjacent in H[T ].
Therefore, u and v are adjacent in G[S] if and only if φ′(u) and φ′(v) are
adjacent in H[T ]. Therefore, φ′ is an isomorphism from G[S] to H[T
]
and so G[S] ∼ = H[T ].
(b) Let r = 3. Then G[S] has no edges and G[T ] has one edge. Thus
G[S] ∼
/= G[T ] and so G ∼
/= H.

10. (a) The three graphs with this property are shown in Figure 1.4(a).
(b) The graphs G, H, F1 and F2 in Figure 1.4(b) have this property.


Section 1.4. Regular Graphs

11. Proof. Denote the size of G by m. Thus, m = rn/2. The average degree of

,4 CHAPTER 1. INTRODUCTION
..... ..... ..... ......
. .. . . .
...... . ..
.. . . .....
.
.. . . . .....
. . ......
.

.... . ....
. .. . ..
..... ... ....
. . . . ..


u
.. .. (a) u...
u.....
. . . ..
. ..... ........ . .
... .. .
. . . .
.. .. .
y .....
.. ..
. ....
.. .
. .. .
. .... v .. ...
. ..... .. y ...... . . .......
. .. v y ....... ....
... v
.. .. .. ... .. . ..
G: .. .. . .
. .
. .
....
.
H : .. . ....
. . .. F : .
.
.
. F2 : ....
.
.. ..... . .. .. 1 ... . .... .
....
....
.. . . .. ...... . ....... ... . .. . . .. .. . ....
. . . . . . .
x w x w x w
(b)

Figure 1.4: The graphs Exercise 10


G is
2m rn/2
=2 = r.
n n
Since G is not r-regular, G contains a vertex v such that deg v /= r. We
consider two cases.

Case 1. deg v > r. Not all vertices of G have degree r or more, for otherwise,
rn Σ
2m = 2 = rn = deg v > rn,
n v∈V (G)

which is impossible. Hence G contains a vertex u with deg u < r. Therefore,
∆(G) ≥ deg v ≥ r + 1 and δ(G) ≤ deg u ≤ r — 1 and so ∆(G) — δ(G) ≥ 2.

Case 2. deg v < r. Not all vertices of G have degree r or less, for otherwise,
rn Σ
2m = 2 = rn = deg v < rn,
n v∈V (G)

which is impossible. Hence, G contains a vertex w with deg w > r. Therefore,
∆(G) ≥ deg w ≥ r + 1 and δ(G) ≤ deg v ≤ r — 1 and so ∆(G) — δ(G) ≥ 2.
12. Let k ≥ 2. For 0 ≤ i ≤ k — 1, let G i = C 3(k−i) + iC3. The graphs
G0, G1 , . . . , Gk−1 are pairwise non-isomorphic.
13. Let V (G) = {u, v, w, x} and E(G) = {uv, vw, wx, xu, vx}. Let e = vx. Then
G — e = C4 and G — u = C3.
14. (a) Let G1 = 2C3 and G2 = C6.
(b) Let H1 = 3C3 and H2 = C9.
15. If G itself is r-regular, then there is nothing to prove. So we may assume
that G is not r-regular. Let G′ be another copy of G and join corresponding

, 5

vertices whose degrees are less than r, calling the resulting graph G1. If G1
is r-regular, then G1 has the desired properties. If not, then we continue this
procedure until arriving at an r-regular graph Gk, where k = r — δ(G).
16. For each i with 1 ≤ i ≤ j, let vi be the vertex of G with deg vi = r — i and let
G′ be another copy of G where the vertex vi′ in G′ corresponds to the vertex
vi in G. Let H be the graph of order 2n obtained from G and G′ by joining vi
to vj′ −i+1, vj′ −i+2, . . . , vj′ for 1 i j. Then H is an r-regular graph of
order 2n containing G as an induced ≤ ≤ subgraph.

17. The Petersen graph.
18. (a) G6,1 = K6 and G5,2 is the Petersen graph.
n−k n
(b) The graph Gn,k is an k
-regular graph of order k
.

Section 1.5. Bipartite Graphs
19. Let x be the number of vertices of degree 8 in W . Then n = 10 + 4 + 3 +
x and m = ·6 10 = 60. Since m =· 4 2 +· 3 4 + 8x = 60, it follows that x
= 5 and so n = 22.

20. Proof. We have seen that the size of the complete bipartite graph K⌊ n ⌋,⌈ n ⌉
2 2
is ⌊n2/4⌋. For every bipartite graph with partite sets U and W with s = |U | ≤
|W | = t and s + t = n, clearly Ks,t has the maximum size. If 0 ≤ t — s ≤ 1,
then Ks,t = K⌊n/2⌋,⌈n/2⌉ and the size of Ks,t is ⌊n2/4⌋. Suppose that t—s ≥ 2. Then
t = ⌈n/2⌉ + p and s = ⌊n/2⌋ — p for some p ≥ 1. Then the size of Ks,t
is
(⌈n/2⌉ + p) (⌊n/2⌋ — p) = ⌊n2/4⌋ + p (⌊n/2⌋ — ⌈n/2⌉) — p2 < ⌊n2/4⌋.
Hence, K⌊ n ⌋,⌈ n ⌉ is the only bipartite graph having size ⌊n2/4⌋.
2 2

21. Proof. Suppose that the partite sets of a 3-partite graph G of order n = 3k
and size m are A, B and C, where |A| = a, |B| = b and |C| = c and a + b
+ c = 3k. We may assume that a ≥ b ≥ c. Then a ≥ k and c ≤ k. Hence, a = k +
x, c = k — y and b = 3k — a — c = k — x + y, where x, y ≥ 0. Then
m ≤ ab + ac + bc = 3k2 — x2 + xy — y2
2 3y2
= 3k2 — x — y + ≤ 3k 2,
2 4

where m = 3k2 if and only if x = y = 0 and so a = b = c = k, in which case,
G = Kk,k,k.

22. Proof. Define a relation R on V (G) by u R v if uv ∈ / E(G). The relation R
is clearly reflexive and symmetric. For vertices u, v and w of G, if uv ∈
/ E(G)
and vw ∈ / E(G), then uw ∈ / E(G). Thus, R is transitive and so R is an