1. Let M be a matching in a bipartite graph G. Show that if M is suboptimal, i.e. contains fewer edges than some other matching in G, then G contains an augmenting path with respect to M. Does this fact generalize to matchings in non-bipartite graphs?
Hint: Recall how an augmenting path turns a given matching into a larger one. Can you reverse this process.
2. Derive the marriage theorem from Konig’s theorem.
Hint: If there is no matching of A, then by Konig’s theorem few vertices cover all the edges. How can this assumption help you to find a large subset of A with few neighbors?
3. Let G and H be defined as for the third proof of Halls theorem. Show that dH(b) ≤ 1 for every b ∈ B, and deduce the marriage theorem.
Hint: Show that the marriage condition fails in H for A1 S A2. The proof is almost a mirror image of the third proof, with unions and intersections interchanged.