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 G1 be B together with Γ(B), and let G2 be X-B together with Y-Γ(B). We wish to show that Hall's condition is satisfied in both these graphs. For G1 this is clear, since Hall's condition holds in G and all edges from B end up in Γ(B). Now consider G2; 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 G1 and G2, and by the induction hypothesis, we can find a matching for these two graphs, which together give us the required matching of G.