QP-2011-02

A unified proof for Karzanov's exact matching theorem

Hans-Florian Geerdes, Jácint Szabó



Abstract

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:

@techreport{egresqp-11-02,
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: 6.4.2021. Please email your comments to Tamás Király!