Introduction to Graph Theory (2007 Edition) – Solutions Manual – Koh Khee Meng

ALL 7 CHAPTERS COVERED




SOLUTIONS MANUAL

,Introduction to
Graph Theory
Solutions Manual

, Notation



N= {1, 2, 3, · · · }

|S|
n
= the number of elements in the finite set S
n!
r = the number of r-element subsets of an n-element set = r!(n−r)!
B\A= {x ∈ B|x ∈ / A}, where A and B are sets

Si = {x|x ∈ Si for some i ∈ I}, where Si is a set for each i ∈ I
i∈I
(⇒) proof of the implication “if P then Q” in the statement “P if and
only if Q”
(⇐) proof of the implication “if Q then P” in the statement “P if and
only if Q”
[Necessity] proof of the implication “if P then Q” in the statement “P if and
only if Q”
[Sufficiency] proof of the implication “if Q then P” in the statement “P if and
only if Q”

In what follows, G and H are multigraphs, and D is a digraph.
V (G) : the vertex set of G
E(G) : the edge set of G
v(G) : the number of vertices in G or the order of G
e(G) : the number of edges in G or the size of G
V (D) : the vertex set of D
E(D) : the arc set of D
v(D) : the number of vertices in D or the order of D
e(D) : the number of arcs in D
x→y: x is adjacent to y, where x, y are vertices in D
x → y : x is not adjacent to y, where x, y are vertices in D
G∼=H : G is isomorphic to H
A(G) : the adjacency matrix of G

vii

, viii Introduction to Graph Theory, Solutions Manual


G : the complement of G
[A] : the subgraph of G induced by A, where A ⊆ V (G)
e(A, B) : the number of edges in G having an end in A and the other in B,
where A, B ⊆ V (G)
G − v : the subgraph of G obtained by removing v and all edges incident
with v from G, where v ∈ V (G)
G − e : the subgraph of G obtained by removing e from G, where e ∈ E(G)
G − F : the subgraph of G obtained by removing all edges in F from G,
where F ⊆ E(G)
G − A : the subgraph of G obtained by removing each vertex in A together
with the edges incident with vertices in A from G, where A ⊆ V (G)
G + xy : the graph obtained by adding a new edge xy to G, where x, y ∈
V (G) and xy ∈ / E(G)
NG (u) : the set of vertices v such that uv ∈ E(G)
N (u) = NG (u)

N (S) = N (u), where S ⊆ V (G)
u∈S
d(v) = dG (v) : the degree of v in G, where v ∈ V (G)
id(v) : the indegree of v in D, where v ∈ V (D)
od(v) : the outdegree of v in D, where v ∈ V (D)
d(u, v) : the distance between u and v in G, where u, v ∈ V (G)
d(u, v) : the distance from u to v in D, where u, v ∈ V (D)
c(G) : the number of components in G
δ(G) : the minimum degree of G
∆(G) : the maximum degree of G
χ(G) : the chromatic number of G
α(G) : the independence number of G
G+H : the join of G and H
G∪H : the disjoint union of G and H
kG : the disjoint union of k copies of G
G(D) : the underlying graph of D
nG (H) : the number of subgraphs in G which are isomorphic to H
Cn : the cycle of order n
Kn : the complete graph of order n
Nn : the null graph or empty graph of order n
Pn : the path of order n
Wn : the wheel of order n, Wn = Cn−1 + K1
K(p, q) : the complete bipartite graph with a bipartition (X, Y ) such that
|X| = p and |Y | = q

, Contents




Preface v
Notation vii
1. Fundamental Concepts and Basic Results 1
Exercise 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Exercise 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Exercise 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2. Isomorphisms, Subgraphs and the Complement of a Graph 29
Exercise 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Exercise 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Exercise 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3. Bipartite Graphs and Trees 73
Exercise 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Exercise 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Exercise 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4. Vertex-colourings of Graphs 99
Exercise 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Exercise 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Exercise 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Exercise 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Exercise 4.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137




ix

,x Introduction to Graph Theory, Solutions Manual


5. Matchings in Bipartite Graphs 143
Exercise 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Exercise 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Exercise 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

6. Eulerian Multigraphs and Hamiltonian Graphs 173
Exercise 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Exercise 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Exercise 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Exercise 6.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

7. Digraphs and Tournaments 209
Exercise 7.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Exercise 7.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Exercise 7.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Exercise 7.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Books Recommended 249
Index 251

, Chapter 1

Fundamental Concepts and Basic
Results


Theorem 1.1 Let G be a multigraph with V (G) = {v1 , v2 , · · · , vn }. Then
n

d(vi ) = 2e(G).
i=1




Corollary 1.2 The number of odd vertices in any multigraph is even.

Exercise 1.2
Problem 1. Let G be the multigraph representing the following diagram.
Determine V (G), E(G), v(G) and e(G). Is G a simple graph?

w m

x
y




n

u v z



Solution. V (G) = {m, n, u, v, w, x, y, z},

E(G) = {my, uv, uw, ux, vx, vy, wx, xz, yz}, v(G) = 8 and e(G) = 9.

Yes, G is a simple graph.


1

,2 Introduction to Graph Theory, Solutions Manual


Problem 2. Draw the graph G modeling the flight connectivity between
twelve capital cities with the following vertex set V (G) and edge set E(G).

V (G) = {Asuncion, Beijing, Canberra, Dili, Havana, Kuala Lumpur,
London, Nairobi, Phnom Penh, Singapore, Wellington,
Zagreb}.
E(G) = {Asuncion-Havana, Asuncion-London, Beijing-Canberra,
Beijing-Kuala Lumpur, Beijing-London, Beijing-Phnom Penh,
Beijing-Singapore, Canberra-Dili, Dili-Kuala Lumpur,
Dili-Singapore, Havana-London, Havana-Nairobi,
Kuala Lumpur-London, Kuala Lumpur-Phnom Penh,
Kuala Lumpur-Singapore, Kuala Lumpur-Wellington,
London-Nairobi, London-Singapore, London-Wellington,
London-Zagreb, Phnom Penh-Singapore, Singapore-Wellington}.

(Note that you may use ‘A’ to represent ‘Asuncion’, ‘B’ to represent
‘Beijing’, ‘C’ to represent ‘Canberra’, etc.)


Solution.

A
Z B

W C



S D



P H


N K
L




, Exercise 1.2 3


Problem 3. Define a graph G such that V (G) = {2, 3, 4, 5, 11, 12, 13, 14}
and two vertices ‘s’ and ‘t’ are adjacent if and only if gcd{s, t} = 1. Draw
a diagram of G and find its size e(G).


Solution.

2
14 3




13 4




12 5
11


e(G) = 21.


Problem 4. The diagram below is a map of the road system in a town.
Draw a multigraph to model the road system, using a vertex to represent a
junction and an edge to represent a road joining two junctions.




Diagram for Problem 4

, 4 Introduction to Graph Theory, Solutions Manual


Solution.







Problem 5. Let G be a graph with V (G) = {1, 2, · · · , 10}, such that two
numbers ‘i’ and ‘j’ in V (G) are adjacent if and only if |i − j| ≤ 3. Draw
the graph G and determine e(G).


Solution.

1 2



10 3




9 4




8 5



7 6


e(G) = 24.