Theorem - Heiratssatz von Hall

• Involvierte Definitionen:
  • Bipartiter Graph
  • Farbklasse
  • Matching
  • Gematchte Knoten
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Theorem: Heiratssatz von Hall

Sei ein bipartiter Graph.
Seien die Farbklassen von .

Dann gilt nach dem Heiratssatz von Hall:

hat ein Matching, sodass alle Knoten von gematcht sind