Skip to content
Quantoros

A path alternates unused and matched edges and begins and ends at unmatched vertices. Why does flipping membership of…

Quant ResearchLevel: IntermediateAugmenting paths

A path alternates unused and matched edges and begins and ends at unmatched vertices. Why does flipping membership of all its edges improve the matching by exactly one?

Hints
  • Count edge types on an odd-length alternating path.
  • Check internal vertices separately from endpoints.

Answer

The path has one more unused edge than matched edges. Internal vertices lose one matched incident edge and gain one, while endpoints gain one. Thus the result remains a matching and its size rises by one.

Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial

Related questions