0
$\begingroup$

Konig's theorem in graph theory says that for a bipartite graph $G$, the size of maximum matching in $G$ is equal to the size of minimum vertex cover of $G$.

Typically, one of the proofs is to construct a vertex cover based on a maximum matching whose sizes are equal (e.g., here). I am wondering is there the other way, say based on a minimum vertex cover, can one construct a matching so that their sizes are equal?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .