Editing Hall's marriage theorem (section)

== 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 (graph theory)|König's theorem]]<ref>The naming of this theorem is inconsistent in the literature. There is the result concerning matchings in bipartite graphs and its interpretation as a covering of (0,1)-matrices. {{harvtxt|Hall|1986}} and {{harvtxt|van Lint|Wilson|1992}} refer to the matrix form as König's theorem, while {{harvtxt|Roberts|Tesman|2009}} refer to this version as the Kőnig-Egerváry theorem. The bipartite graph version is called Kőnig's theorem by {{harvtxt|Cameron|1994}} and {{harvtxt|Roberts|Tesman|2009}}.</ref>
* [[Menger's theorem]] (1927)
* The [[max-flow min-cut theorem]] (Ford–Fulkerson algorithm)
* The [[Birkhoff–Von Neumann theorem]] (1946)
* [[Dilworth's theorem]].

In particular,<ref>[https://web.archive.org/web/20221027074219/http://www.robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]</ref><ref>{{harvnb|Reichmeider|1984}}</ref> there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.