CS1231S Discrete Structures Exam solutions

National University of Singapore
Department of Computer Science
2019/20 (Sem. 2) CS1231/CS1231S Discrete Structures Tutorial 10

1 Let G3 be the set of all undirected graphs whose vertices are a, b, c. Suppose G = ({a, b, c}, E) ∈ G3 .
Determine the number of possible G’s such that:
(i) G has a loop; (ii) G has a cycle;
(iii) G is cyclic; (iv) G is connected;
(v) G is a tree; (vi) G has exactly two connected components.
Solution:

Consider (labelled) undirected graphs with 3 nodes.
Each node may or may not have a loop (23 possibilities),
and each node pair may or may not have an edge (2(2) possibilities).
3


Total = 23 (23 ) = 26 = 64.

(i) #graphs with no loops = 13 2(2) = 8
3


⇒ #graphs with loops = 64 − 8 = 56.

(ii) #graphs with a cycle (choice only in loops) = 23 = 8.

(iii) #(∼loop∧ ∼cycle)= 2(2) − 1 = 7.
3


#cyclic = #(loop∨cycle) = 64 − 7 = 57.

(iv) #connected⇔ ∧, <, > or △ and any choice of loops: 4(23 ) = 32 possibilites

(v) tree ⇔ ∧, <, or > and no loops: 3 possibilities

(vi) G
has exactly 2 components ⇔ 1 edge only and any choice of loops:
3 3
1
2 = 24 possibilities.




1

, x
2 The diagram here illustrates an undirected graph K, called a 3-sided wheel:
(i) Let K = (VK , EK ). List the elements of EK . u
(ii) How many different 3-sided wheels are there with VK = {u, x, y, z}?
y z
(iii) Determine the number of different 3-sided wheels with VK ⊆ {1, 2, 3, 4, 5, 6}
3-sided wheel K
(e.g. u = 4, x = 6, y = 2, z = 3)?
with vertices u, x, y, z
w x u x
The diagram here shows two
u w
4-sided wheels H and H ′ :
y z y z
(iv) Explain why H 6= H ′ .
4-sided wheel H 4-sided wheel H’
(v) Determine the number of different 4-sided wheels H with vertex set VH = {1, 2, 3, 4, 5}.
(vi) Determine the number of different 4-sided wheels H with vertex set VH ⊆ {1, 2, 3, 4, 5, 6, 7}.
Solution:

(i) EK = {{u, x}, {u, y}, {u, z}, {x, y}, {y, z}, {x, z}}

(ii) Just 1, since EK already has all possible edges

(iii) There are 64 = 15 choices for VK ; each choice gives one 3-sided wheel.



Therefore, there are 15 possibilites.

(iv) H 6= H ′ since u in H has 4 edges, but u in H ′ has 3 edges.

(v) With u at the center, there are just 3 possible wheels,
determined by who is not connected to x by one edge.
There are 5 possible choices for the center,
so there are 5 × 3 = 15 possible 4-sided wheels (Multiplication Rule)

(vi) There are 75 = 21 choices for VH ; each choice gives 15 4-sided wheels.



Therefore there are 21 × 15 = 315 possible 4-sided wheels for VH ⊆ {1, 2, 3, 4, 5, 6, 7}.




2