Proposition - Augmentierende Pfade haben stets eine ungerade Länge

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

⠀

Proposition: Augmentierende Pfade haben stets eine ungerade Länge

Sei ein Graph.
Sei ein Matching von .
Sei ein augmentierender Pfad.

Dann gilt:

• ist ungerade.
• ist gerade.

Beweis

Sei ein augmentierender Pfad. Dann lassen sich stets die aufeinanderfolgenden Kanten des Pfades zu Paaren anordnen, sodass außerhalb des Matchings und innerhalb des Matchings liegt.

Also:

• , denn liegt nach Definition in dem Matching, aber nicht
• …

Lediglich für die letzte Kante finden wir keinen Partner mehr. Wir haben also Kanten, die sich zu Paaren anordnen lassen, und eine zusätzliche Kante, die übrig bleibt.

Da also folgt , was zu zeigen war. Damit gilt:

Da per definitionem jeder Pfad eine Knote mehr als Kanten hat, gilt weiter

Damit folgt, dass gerade ist.