Description
Q1 Prove that in any Facebook community, there must exist two people who have the
same number of friends. Mathematical equivalently, prove that any simple graph G with at
least two vertices must contain two vertices of the same degree. [4 marks]
Q2 (a) Consider a minimum spanning tree (MST) of a connected, weighted graph. If we
remove an edge (u, v) of the MST, then we get two separate trees. Are these two trees the
MSTs on their respective sets of nodes? Is the edge (u, v) a least-weight edge crossing
between those two sets of nodes? [3 marks]
(b) Consider the following algorithm for finding an MST on a graph: split the nodes of the
graph arbitrarily into two nearly equal-sized sets, and find an MST on each of those sets.
Then connect the two MSTs with the least-cost edge between them. Would this
algorithm always return an MST of the original graph? [3 marks]
If your answer to these questions is Yes, prove them; if your answer is No, disprove
them by constructing a counterexample.
Q3 (a) An automotive company has three factories, each associated with different costs of
producing vehicles (the cost of raw materials, the cost of labour, and the environmental footprint per vehicle produced):
Materials Labour CO2 emissions
Factory 1 6 18 10
Factory 2 5 14 17
Factory 3 7 11 20
Each month the company can afford to pay for 4000 hours of labour and 4000 units of
raw materials. Additionally, labour politics require at least 100 cars to be produced
at Factory 1 and environmental regulations allow the company to emit at most 3000
units of CO2.
What is the optimal allocation of manufacturing capacity between the factories (i.e.
how many vehicles need to be produced by each factory to ensure that the company
produces the maximum possible number of vehicles each month)? (Hint: use Linear
Programming) [4 marks]
(b) Suppose that labour politics changes and the company is required to produce at
least 75 vehicles at each factory (at least 225 vehicles in total), other requirements
remaining in place as before. What would be the effect of such a development?
[1 mark]
1