Metraipolis › archive › dc_76e5650cfec4

Hall's marriage theorem — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T22:24:50.725Z
SHA-256 of the archived text: 9ef138d925b38c4c938029b02843c46987d5bb9c849a270fba0dd51130c9c810
Stable URL of this page: https://metraipolis.com/documento/dc_76e5650cfec4

How to cite

Hall's marriage theorem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_76e5650cfec4 (Metraipolis archive dc_76e5650cfec4, sha256 9ef138d925b38c4c938029b02843c46987d5bb9c849a270fba0dd51130c9c810)

BibTeX

@misc{dc76e5650cfec4,
  title = {Hall's marriage theorem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_76e5650cfec4; sha256 9ef138d925b38c4c938029b02843c46987d5bb9c849a270fba0dd51130c9c810},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist: The combinatorial formulation answers whether a finite collection of sets has a transversal—that is, whether an element can be chosen from each set without repetition. Hall's condition is that for any subset of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the subset. The graph theoretic formulation answers whether a finite bipartite graph has a perfect matching—that is, a way to match each vertex from one group uniquely to an adjacent vertex from the other group. Hall's condition is that any subset of vertices from one group has a neighbourhood of equal or greater size.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «combinatorics»).
Fonte: Wikipedia in inglese, voce «Hall's marriage theorem» — https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem
Wikidata Q536640 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q536640
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1343521441, consultata il 2026-10-07T22:05:42.032Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 23ff4263ac53ea0538b2731f5f809109be535e47815b819ec0b32139b11e6fff