proof of Hall's Marriage Theorem

The following is full mathematical proof of Hall's Marriage Theorem which is an important result in combinatorics. We use the notation Γ(A) to denote the set of neighbours of the vertices in a set A.

Let G be a bipartite graph with bipartition X and Y. Suppose there is a matching from X to Y. Consider any subset A of X. Each edge of the matching takes each element of A to a different element in Y. Hence the set of neighbours of A is at least the size of A, so |Γ(A)|>=|A|. Hence Hall's condition is satisfied in G as required.

Conversely, suppose Hall's condition is satisfied in G: |Γ(A)|>=|A| for all subsets A in X. We prove the result by induction on |X|: for |X|=1, the result is immediate.

Suppose that for all non empty proper subsets A of X, we have strict inequality in Hall's condition: |Γ(A)|>|A|. Choose any x in X and any of its neighbours y in Y. Then Hall's condition holds in X-{x} and Y-{y}, so by the induction hypothesis we can match X-{x} to Y-{y} and so match X to Y.

Otherwise we can find a non empty proper subset B in X with |Γ(B)|=|B|. We split the bipartite graph up into two: let G₁ be B together with Γ(B), and let G₂ be X-B together with Y-Γ(B). We wish to show that Hall's condition is satisfied in both these graphs. For G₁ this is clear, since Hall's condition holds in G and all edges from B end up in Γ(B). Now consider G₂; take a subset A in X-B. Then

|ΓG2(A)| = |ΓG(A u B)| - |Γ(B)|
        >= |A u B| - |B| = |A|,

as required. Hence Hall's condition is satisfied in both G₁ and G₂, and by the induction hypothesis, we can find a matching for these two graphs, which together give us the required matching of G.

Comments on the proof

This is only one of several proofs of the theorem. Another one involves removing edges until a minimal graph in which Hall's condition is satisified is obtained. We then assume what is left is not a matching, and prove the result by contradiction. This proof also generalises to the case when X and Y are countably infinite.

If Hall's condition is satisfied, then as well telling us that a matching exists, the above proof gives us an algorithm for finding the matching. This is not always the case in combinatorics proofs: for example many proofs in Ramsey Theory only guarantee existence, and do not say anything about the actual sets which satisfy the properties in question.