Proposition - In bipartiten Graphen liegen die Endpunkte eines augmentierenden Pfades in unterschiedlichen Farbklassen

• Involvierte Definitionen:
  • Matching
  • Bipartiter Graph
  • Farbklasse
  • Augmentierender Pfad
• Veranstaltung:
  • AlMa
• Referenz: @herzogWiSe22

⠀

Proposition: In bipartiten Graphen liegen die Endpunkte eines augmentierenden Pfades in unterschiedlichen Farbklassen

Sei ein bipartiter Graph.
Seien die Farbklassen von .
Sei ein Matching von .

Sei ein augmentierender Pfad bezüglich , dann gilt:

in anderen Worten: die Endpunkte von müssen in unterschiedlichen Farbklassen liegen. Andernfalls handelt es sich nicht um einen augmentierenden Pfad.