MATH2069/2969 Semester 1 Main, 2019 page 2 of 6
SECTION A: Discrete Mathematics
Use separate writing booklets for sections A and B.
1. A group of 30 people get together to start a small company.
(a) How many different ways can they elect a managing committee of 8 people,
including 2 people appointed as co-presidents?
(b) 100 indistinguishable cards are printed with the company name and logo.
What is the number of ways to distribute the cards among the 30 employees,
given that everyone must have at least 2 cards?
(c) In their new building, there are 10 offices, so exactly 3 people will be assigned
to each office. How many ways are there to assign an office to each employee?
(d) There are 5 priority projects that the company needs to work on. How many
ways are there to assign an employee to each task, so that each task has at
least one person working on it?
2. (a) Write the characteristic polynomial of the recurrence relation
bn = bn−1 + 12 bn−2, where n > 2.
(b) Find the general solution of the recurrence relation
bn = bn−1 + 12 bn−2, where n > 2.
(c) Find one particular solution of the recurrence relation
an = an−1 + 12 an−2 − 4
n, where n > 2.
(d) Find the solution of the recurrence relation
an = an−1 + 12 an−2 − 4
n, where n > 2,
satisfying the initial conditions a0 = 0 and a1 = −2.
turn to page 3
MATH2069/2969 Semester 1 Main, 2019 page 3 of 6
3. This question is for MATH2069 students only.
(a) The generating function of a sequence an is given by the formula
A(z) =
3 + z
(1 + 2z)2
.
Write down an explicit formula for an.
(b) Let bn = a0an + a1an−1 + · · · + ana0. Find a closed form for the generating
function B(z) for the sequence bn.
(c) Let cn = a0 + a1 + · · · + an. Find a closed form for the generating function
C(z) for the sequence cn.
(d) Express the generating function for the sequence 2,−3, 4,−5, 6,−7, . . . in the
form P (z)
Q(z)
, where P (z) and Q(z) are both polynomials.
3. This question is for MATH2969 students only.
(a) Let B(z) =
∑
∞
n=0 bnz
n = log(1 + z) be defined as the unique formal power
series such that B′(z) = 1
1+z
, with b0 = 0. Write down a closed form for bn.
(b) Recall that exp(z) =
∑
∞
n=0
zn
n!
.
Let F (z) be a given formal power series and let G(z) be the unique formal
power series with zero constant term such that G′(z) = F (z). Prove that for
a given value of a0, the differential equation A
′(z) = F (z)A(z) has a unique
solution which is given by A(z) = a0 exp
(
G(z)
)
.
(c) Show that the formal power series A(z) = exp
(
log(1+2z+z2)
)
satisfies the
equation A′(z) = A(z)
2
1 + z
.
(d) Using the previous results, prove the identity
exp
(
log(1 + 2z + z2)
)
= 1 + 2z + z2.
turn to page 4
MATH2069/2969 Semester 1 Main, 2019 page 4 of 6
SECTION B: Graph Theory
Use separate writing booklets for sections A and B.
4. (a) Only one of the sequences (3, 3, 3, 3, 4, 5), (3, 3, 4, 4, 4, 6), and (3, 3, 3, 3, 4, 4)
is graphic. Explain why two of these sequences are not graphic.
(b) Draw a picture of a graph whose degree sequence coincides with the remain-
ing sequence in part (a).
(c) Either write down an Eulerian trail in the following graph, or explain why
none exists. a b
e
g
h
c
d
f
i
j
5. (a) Complete the formulation of the Travelling Salesman Problem: “Given a
connected weighted graph, find a walk which . . . ”.
(b) Find a walk which solves the Travelling Salesman Problem for the following
weighted graph. Justify your answer.
a
b c
e f
d
8
17
17
8 11 4
5
10
6
(c) Find a minimal spanning tree for the weighted graph in (b).
(d) Consider the trees with 7 vertices {1, 2, 3, 4, 5, 6, 7} which have a vertex of
degree 4.
(i) What is the possible number of leaves in such a tree?
(ii) What is the number of isomorphism classes of such trees?
Justify your answer to each of the questions.
(e) A tree has two vertices of degree 4. What is the minimum possible number
of vertices in such a tree? Justify your answer.
turn to page 5
MATH2069/2969 Semester 1 Main, 2019 page 5 of 6
6. This question is for MATH2069 students only.
(a) Let t be a natural number. Define what is meant for a graph G to be t-
colourable.
(b) Use mathematical induction on the number n of vertices in G to show that
any graph G is t-colourable for t = ∆(G) + 1.
(c) The graph H is given by the picture
(i) What is the maximum possible value of the chromatic number χ(H)
as provided by the Brooks Theorem?
(ii) What is the exact value of χ(H)? Justify your answer.
(iii) What are the possible values of the edge chromatic number χ′(H) as
provided by the Vizing Theorem?
(iv) What is the exact value of χ′(H)? Justify your answer.
6. This question is for MATH2969 students only.
(a) For any n > 6 the graph Gn can be drawn as a regular polygon with n
vertices together with all diagonals of the minimal length.
[ For instance, the picture above on this page represents Gn for n = 6 ].
(i) Calculate the chromatic numbers χ(Gn). Justify your answer.
(ii) Calculate the edge chromatic number χ′(G8). Justify your answer.
(iii) Prove that if n is odd then χ′(Gn) = 5.
(b) Find the chromatic polynomial for the graph
turn to page 6
MATH2069/2969 Semester 1 Main, 2019 page 6 of 6
This is the end of the examination paper.