MMAT5380 Graph Theory and Networks

Second Semester 2018-19

Suggested Solution for Assignment 1

1-1: (a) Following is a geometric drawing:

b c
a d

g f e

(b) (4, 3, 3, 3, 2, 1, 0).

(c) 4 + 3 + 3 + 3 + 2 + 1 + 0 = 16 = 2 × 8 and there are eight edges in G.

(d)
a b c d e f g ab ac ae af bc ce ef fg
a 0 1 1 0 1 1 0 a 1 1 1 1 0 0 0 0
b 1 0 1 0 0 0 0 b 1 0 0 0 1 0 0 0
c 1 1 0 0 1 0 0 c 0 1 0 0 1 1 0 0
A= M=
d 0 0 0 0 0 0 0 d 0 0 0 0 0 0 0 0
e 1 0 1 0 0 1 0 e 0 0 1 0 0 1 1 0
f 1 0 0 0 1 0 1 f 0 0 0 1 0 0 1 1
g 0 0 0 0 0 1 0 g 0 0 0 0 0 0 0 1

1-2: (i) The answer is not unique.

1 2

3
6

5 4

(ii) The answer is not unique.

1 2

3
6

5 4

1-3: (a) No. Suppose there exists a simple graph. Let v1 , . . . , v6 be vertices of G. Without loss of
generality we may assume deg(v1 ) = deg(v2 ) = 5. Then v1 and v2 are adjacent with other
vertices. Then deg(vi ) ≥ 2. It is a contradiction.

You may also apply the algorithm. You may find that it is impossible to obtain a simple graph.

(b) (5, 4, 3, 3, 3, 3, 3, 2) → (3, 2, 2, 2, 2, 3, 2) 8

(3, 3, 2, 2, 2, 2, 2) → (2, 1, 1, 2, 2, 2)
(2, 2, 2, 2, 1, 1) → (1, 1, 2, 1, 1)
1 2 3 5 4
(2, 1, 1, 1, 1) → (0, 0, 1, 1)
(1, 1, 0, 0) 6 7

1
 Note that the answer is not unique.

1-4: (a) Graphs H and K are subgraphs of G. The graph J is not, because J contains edge bd which is
not an edge of G.

(b) We found in (a) that only H and K are subgraphs of G. Of those two graphs, H is an induced
subgraph. For an induced subgraph, we must use the maximal subgraph with the given vertex
set. For the graph H, all necessary edges appear. Thus, H is induced. For the graph K, edge
ce would also need to appear since that edge is in G. Thus, K is not an induced subgraph of G.

1-5: F (1) = a, F (2) = c, F (3) = e, F (4) = b, F (5) = d and F (6) = f . The mapping F induces a
correspondence from the edges of G to the edges of H as follows: 14 → ab; 15 → ad; 16 → af ;
24 → cb; 25 → cd; 26 → cf ; 34 → eb; 35 → ed and 36 → ef . Thus the mapping F preserves the
adjacency. So we have shown that G is isomorphic to H.

1-6: (a) The right graph of the following figure shows the C3 × P4 .

× =

(b) In G × H, for a fixed vertex vj in H, vertices (uk , vj ) and (ul , vj ) are adjacent if and only if
vertices uk and ul are adjacent in G. So (uk , vj ) has degG (ui ) neighbors of the form (ul , vj ). For
a fixed vertex uk in G, vertices (uk , vj ) and (uk , vi ) are adjacent if and only if vertices vj and vi
are adjacent in H. So (uk , vj ) has degH (vj ) neighbors of the form (uk , vi ). Therefore, totally,
degG×H (ui , vj ) = degG (ui ) + degH (vj ).

1-7: Let G be a self-complementary graph with p vertices. Since G ∼

= G, the edge number of G is equal
p(p−1) p(p−1)
to that of G. On the other hand, since |E(G) ∪ E(G)| = 2 we have |E(G)| = 4 . Since the
edge number of a graph is an integer, we must have p = 4k or 4k + 1, for some integer k.

1-8: (a) For v ∈ N (A ∪ B), there is a vertex u ∈ A ∪ B such that v is adjacent with u, i.e., v ∈ N (u).
Since u ∈ A or u ∈ B, v ∈ N (u) ⊆ N (A) or v ∈ N (u) ⊆ N (B). Hence u ∈ N (A) ∪ N (B). Thus,
N (A ∪ B) ⊆ N (A) ∪ N (B).

Conversely, for v ∈ N (A) ∪ N (B), we have v ∈ N (A) or v ∈ N (B). By definition N (A) ⊆

N (A ∪ B) and N (B) ⊆ N (A ∪ B). So, N (A) ∪ N (B) ⊆ N (A ∪ B).

We have N (A ∪ B) = N (A) ∪ N (B).

(b) For v ∈ N (A ∩ B), there is a u ∈ A ∩ B such that v is adjacent with u. Since u ∈ A and u ∈ B,
v ∈ N (A) and u ∈ N (B). Thus v ∈ N (A) ∩ N (B). We obtain N (A ∩ B) ⊆ N (A) ∩ N (B).