 Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/b/iii/solution

M^{'}

C^{'}

, the disjoint edges of

M^{'}

need distinct covering vertices. Therefore

∣ M^{'} ∣ \leq ∣ C^{'} ∣, ν (G) \leq τ (G) .

Now assume the assertion in part (ii). It supplies a matching in a graph

M

C

formed by choosing one endpoint of each edge of

M

. Because these edges are disjoint, the chosen endpoints are distinct, so

∣ C ∣ = ∣ M ∣

τ (G) \leq ∣ C ∣ = ∣ M ∣ \leq ν (G) \leq τ (G) .

Every inequality must be equality, proving Kőnig's theorem for bipartite matching:

ν (G) = τ (G) .

 New to topics? Read the docs here!