The University of Hong Kong, Faculty of Engineering
COMP 2121C Discrete Mathematics. Assignment 5
Ravi
(Dated: April 22, 2024)
This Assignment 5 reviews understanding of the concepts in Graph Theory.
Students are expected to work on the assignment for a period of up to two weeks and submit their
solutions through Moodle. Typically, the solution sheet will be formatted in LaTeX but any clear,
legible solution sheet will be accepted. Answers will be judged on correctness, as well as evidence
of detailed understanding, so please show working and explain the steps leading to the final solution.
Assignment 5 Due Date: May 3rd 2024, 23:59.
1. Handshaking Theorem and Matchings [20 Marks]
(a) (10 marks) Show that in a football league with two divisions of 13 teams each, no schedule has each team
playing exactly nine games against teams in its own division and four games against teams in the other
division.
(b) (10 marks) Marissa is teaching Elementary Math to a group of toddlers in her area. She is preparing
n questions for her math exam. In each question, the students have to either add (+), subtract (−) or
multiply (×) a pair of numbers.
After choosing a multiset of n pairs of numbers {(a1, b1), (a2, b2), . . . , (an, bn)}, Marissa has to decide for
each of the n pairs, which of the three possible operations the students should perform. To avoid the
toddlers getting bored, Marissa wants to make sure that the n correct answers to her exam are all different.
Formulate a condition in terms of a matching in a suitably defined graph, and explain to Marissa how to
choose one of the three operations for each pair (ai, bi) to satisfy her requirement. Illustrate your condition
for the choice {(1, 2), (2, 1), (1, 2), (2, 1), (1, 2)}.
2. Graph Coloring [22 Marks]
(a) (11 marks) Prove that any simple undirected graph G = (V, E) with chromatic number equal to 3 and
maximum degree at most three has a bipartite subgraph with at least |E| − |V|/3 edges.
(b) (11 marks) Prove that any simple undirected connected graph G = (V, E) which contains at least one
vertex of degree less than ∆(G) (the maximum degree of all vertices in G) has chromatic number at most
∆(G).
3. Paths and Cycles [32 Marks]
(a) (12 marks) Landau is an old-fashioned hands-on electrical engineer and has designed a rotating drum
consisting of 2k sectors as shown in the Fig. 1 for the case k = 3. He wants to label each sector with either
a 0 or a 1 so that each k-bit string as read consecutively clockwise on the drum is different (three readers
are shown in the figure for the case k = 3). As the drum rotates in a clockwise manner, the k bits will be
read off at the positions indicated in the figure (essentially, Landau is looking for a 2k-bit string that allow
him to have all k different readings).
Your task is to help Landau assign a 0 or a 1 to each of the 2k sectors to satisfy his requirement. Use a suit-
ably defined directed pseudograph and an Euler circuit on the graph to help Landau solve his problem.
Hint: Consider a directed pseudograph with 2k−1 vertices with edges representing clockwise consecutive bit strings
and show that an Euler circuit exists for this graph.
(b) (10 marks) Let G = (V, E) be a simple undirected graph. Define a relation R on V by (v1, v2) ∈ R if
v1 = v2 or if there is a path in G from v1 to v2. Show that R is an equivalence relation. Describe the
partition of V induced byR.
Figure 1: The sign depicts a rotating drum consisting of 8 sectors. It is possible to label each of the 8 sectors with a 0 or a 1 so that
the reader reads each of the eight bit strings 000, 001, 010, 011, 100, 101, 110, 111 as the drum rotates.
(c) (10 marks) Suppose G = (V, E) is a simple undirected graph on |V| = n ≥ 3 vertices. Prove that if
|E| ≥ (n−12 ) + 2 then G has a Hamilton cycle.
4. Graph Connectivity and Graph Planarity [26 Marks]
(a) (10 marks) Let G = (V, E) be a simple undirected graph in which all vertices are of even degree. Is the
vertex connectivity κ(G) of G necessarily even, explain your answer. Is the edge connectivity λ(G) of G
necessarily even, explain your answer.
(b) (8 marks) In Fig. 2 is shown one football sign in the UK. Prove that it is mathematically impossible to
Figure 2: The sign depicts one side of a football whose surface is covered by hexagons (6-sided) that are not necessarily regular.
It is implied that this pattern will be observed when the football is viewed from any angle.
cover the surface of a sphere with the pattern depicted in the figure (even when each hexagon may be
distorted to be irregular).
(c) (8 marks) In Fig. 3 is the standard pattern covering a football using both hexagons (6-sided polygons) and
pentagons (5-sided polygons).
Figure 3: The picture depicts a football viewed from some angle.
When using this pattern to cover the surface of a football, what are the number of hexagons and the
number of pentagons? Show how these numbers are calculated.