Consider a bipartite graph consisting of two sets of nodes S and T such that every arc has its start node in S and its end node in T . A matching is a subset of arcs such that all the start nodes of the arcs are distinct and all the end nodes of the arcs are distinct. A maximal matching is a matching with a maximal number of arcs.
(a) Show that the problem of finding a maximal matching can be formulated as a max-flow problem.
(b) Define a cover C to be a subset of S∪T such that for each arc (i, j), either i ∈ C or j ∈ C (or both). A minimal cover is a cover with a minimal number of nodes. Show that the number of arcs in a maximal matching and the number of nodes in a minimal cover are equal. (Variants of this theorem were independently published by K¨onig [1931] and Egervary [1931].) Hint: Use the max-flow/min-cut theorem.