Definition: A set $CβŠ†V$ and a collection of subsets $𝐡_1,…,𝐡_π‘˜βŠ†V$ is an odd vertex cover if for every edge 𝑒 either $π‘’βˆ©πΆβ‰ βˆ…$ or $𝑒 βŠ† B_i$ for some 𝑖.

The cost of the odd vertex cover is defined to be: $|C| + \sum_{i=1}^{k} \lfloor{\frac{|B_i|}{2}}\rfloor$

Without loss of generality, we may assume that all the sets $B_i$ are of odd size, hence the name, and that C and $B_1,…,B_k$ are disjoint.

Theorem: In any graph, the size of the maximum matching is equal to the cost of the minimum odd vertex cover.

How can I prove it? I tried to use Edmond's algorithm for finding maximum match. Then to take one side of these edges as $C$ and the blossoms as $B_i$'s. I don't have a formal proof for that though.

  • $\begingroup$ Are you familiar with the Gallai-Edmonds decomposition? $\endgroup$
    – Dániel G.
    Jan 31 at 19:10
  • $\begingroup$ No, this question was asked in a course I'm taking and the lecturer suggested the method I tried above $\endgroup$
    – Lianga
    Feb 1 at 15:53


You must log in to answer this question.