Let G be a bipartite graph with bipartition (A, B) where |A| = |B| = 2n. Suppose for each X A where |X| n, |N(X)| |X|, and for each Y B where |Y| n, |N(Y)| |Y|. (i.e., Hall's condition holds for subsets of A and B of size at most n).

Use Knig's Theorem and Hall's Theorem to prove G has a perfect matching.