## 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