A unified proof for Karzanov's exact matching theorem

Hans-Florian Geerdes, Jácint Szabó


We give a short inductive proof for a pair of theorems of Karzanov characterizing when complete and complete bipartite graphs with red and blue edges have a perfect matching with exactly k red edges. In contrast with Karzanov's approach, our proof handles both cases simultaneously.

Bibtex entry:

AUTHOR = {Geerdes, Hans-Florian and Szab{\'o}, J{\'a}cint},
TITLE = {A unified proof for Karzanov's exact matching theorem},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {QP-2011-02}

Last modification: 22.11.2022. Please email your comments to Tamás Király!