Description
Exercise 9.1
Draw undirected graphs for the given adjacency matrices:
i)
1 3 2
3 0 4
2 4 0
ii)
0 1 3 0 4
1 2 1 3 0
3 1 1 0 1
0 3 0 0 2
4 0 1 2 3
(2 Marks)
Exercise 9.2
Determine whether each given pair of graphs is isomorphic. Exhibit an isomorphism (and prove that it actually
is an isomorphism) or prove that no isomorphism exists.
i) u1
u2
u3
u4
u5
v1
v2
v3
v4
v5
ii)
u1 u2
u5 u4 u3
v1
v2
v3
v4
v5
iii) u1
u2
u3
u4
u5
u6
u7
u8
v1
v2
v3
v4
v5
v6
v7
v8
iv) u1
u2
u3
u4
u5
u6
u7
u8
v1
v2
v3
v4
v5
v6
v7
v8
(28 Marks)
Exercise 9.3
For which values of n do the following graphs have an Euler circuit?
i) Kn ii) Wn iii) Cn iv) Qn
(4 Marks)
Exercise 9.4
Show that a graph with at least two vertices is bipartite if and only if all simple circuits have even length.
Hint for the “if ” part: For two vertices u and v, let the distance d(u, v) be the length of the shortest path joining
u to v. Show that choosing an arbitrary vertex u and setting S = {v : 2 | d(u, v)} and T = {v : 2 ∤ d(u, v)}
defines a bipartition of the graph.
(4 Marks)
Exercise 9.5
Is the hypercube Qn bipartite for all n ∈ N? If so, give a bipartition. Otherwise, give a proof that it is not.
(3 Marks)
Exercise 9.6
The complement of a simple graph G = (V, E) is given by Gc = (V, Ec
), where Ec = V × V \ E, i.e., the
complement has the same vertex set and an edge is in Ec
if and only if it is not in E. A graph G is said to be
Self-complementary if G is isomorphic to Gc
.
i) Show that a self-complementary graph must have either 4m or 4m + 1 vertices, m ∈ N.
(3 Marks)
ii) Find all self-complementary graphs with 8 or fewer vertices.
(2 Marks)
Exercise 9.7
The parts of this question outline a proof of Ore’s Theorem. Suppose that G is a simple graph with n vertices,
n > 3, and deg(x) + deg(y) > n whenever x and y are nonadjacent vertices in G. Ore’s Theorem states that
under these conditions, G has a Hamilton circuit.
i) Show that if G does not have a Hamilton circuit, then there exists another graph H with the same vertices
as G, which can be constructed by adding edges to G such that the addition of a single edge would produce
a Hamilton circuit in H.
Hint: Add as many edges as possible at each successive vertex of G without producing a Hamilton circuit.
(2 Marks)
ii) Show that there is a Hamilton path in H.
(1 Mark)
iii) Let v1, v2, . . . , vn be a Hamilton path in H. Show that deg(v1) + deg(vn) > n and that there are at most
deg(v1) vertices not adjacent to vn (including vn itself).
(2 Marks)
iv) Let S be the set of vertices preceding each vertex adjacent to v1 in the Hamilton path. Show that S
contains deg(v1) vertices and vn ∈/ S.
(2 Marks)
v) Show that S contains a vertex vk, which is adjacent to vn, implying that there are edges connecting v1
and vk+1 and vk and vn.
(1 Mark)
vi) Show that part (iii) implies that v1, v2, . . . , vk−1, vk, vn, vn−1, . . . , vk+1, v1 is a Hamilton circuit in G.
Conclude from this contradiction that Ore’s Theorem holds.
(1 Mark)
Exercise 9.8
The following graph shows a simplified map of the Shanghai metro within the inner circle, leaving out all stations
that are not intersections of lines. Each edge is weighted with the travel time between these intersections.
Use Dijkstras algorithm to find the shortest path between Tiantong Rd. station (vertex U) and Zhaojiabang
Rd. station (vertex W). Give the distinguished set of vertices Sk and the labels of all vertices at every step of
the algorithm.
(5 Marks)
A B C D
E
F
G
I H
J
K
L
M
6 8 10
8
10
6
11
10
8
5
5
8
7
4 N 5 O 6 P 5 Q
R S T 10
U
5 7 7
7
4
7
5 V 4 W 9 X 9
Y
4
5
4
9
4
6
3
6
7
7
4
7
Z
3
3
5
3
6
10
Tiantong Rd.
Zhaojiabang Rd.
