 Combinatorial optimisation

Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: released examination archive, member 2022/T/a18330w1.pdf; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.

We use finite simple graphs throughout the graph arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an edge cover exists only when there is no isolated vertex; for a nonempty connected graph this excludes the one-vertex graph. These minor domain qualifications are made explicit in the affected solutions.