Four candidates A, B, C, D interview for desks W, X, Y. A, B and C are each qualified only for W, and D is qualified for X and Y. Give the maximum matching, the minimum vertex cover, the minimum cut value in the flow formulation, and state the theorems linking the three.

Four candidates A, B, C, D interview for desks W, X, Y. A, B and C are each qualified only for W, and D is qualified for X and Y. Give the maximum matching, the minimum vertex cover, the minimum cut value in the flow formulation, and state the theorems linking the three.

Approach: Build the unit-capacity flow network, find the matching by inspection, then find a set of vertices touching every edge and check the two numbers against each other.

2. The maximum matching pairs one of A, B, C with W and pairs D with X or Y, so its size is 2, and nothing larger exists because A, B and C compete for the single desk W. The minimum vertex cover is {W, D}, which touches all five edges and also has size 2. In the flow network with a source feeding each candidate at capacity 1, unit capacity qualification edges and each desk feeding the sink at capacity 1, the maximum flow is 2 and the minimum cut consists of the source to D edge and the W to sink edge, of value 2. The max flow min cut theorem gives matching size equal to cut value, and Konig's theorem gives maximum matching equal to minimum vertex cover in a bipartite graph, so all three coincide. Hall's condition fails on the set {A, B, C}, whose neighbourhood {W} has size 1, so the deficiency is 2, exactly the number of candidates left unmatched.

Follow-up: How does the answer change if each desk can take two candidates and each candidate can hold one seat?

Key concepts: maximum matching, vertex cover, max flow min cut, hall's condition.