Skip to content
Quantoros

A matching cannot be enlarged by simply adding one unused edge. Must it have maximum size? Give the smallest path…

Quant ResearchLevel: IntermediateGreedy matching trap

A matching cannot be enlarged by simply adding one unused edge. Must it have maximum size? Give the smallest path counterexample.

Hints
  • Use the middle edge of a four-vertex path.
  • Allow replacing chosen edges, not only adding new ones.

Answer

No: on four vertices 1-2-3-4, choose edge 2-3. It is maximal because every other edge touches it, but edges 1-2 and 3-4 give a larger matching of size two. Maximal means inclusion-maximal, not maximum cardinality.

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

Related questions