Hall's Marriage Theorem - Logical Equivalences

Logical Equivalences

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include:

• The König–Egerváry theorem (1931) (Dénes Kőnig, Jenő Egerváry)
• König's theorem
• Menger's theorem (1927)
• The max-flow min-cut theorem (Ford–Fulkerson algorithm)
• The Birkhoff–Von Neumann theorem (1946)
• Dilworth's theorem.

In particular, there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.