1: In an X, Y-bigraph G, the deficiency of a set S is def(S) = |S|-|N(S); note that def (0) = 0. Prove that a'(G)= |X|-max def (S). SCX Hint: Form a bipartite graph G' such that GCG and such that G' has a matching that saturates X if and only if G has a matching of the desired size. Use Hall's Theorem applied to G' to then complete the proof.