# Maximum matching = Minimum odd vertex cover

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.

• Are you familiar with the Gallai-Edmonds decomposition? Jan 31 at 19:10
• No, this question was asked in a course I'm taking and the lecturer suggested the method I tried above Feb 1 at 15:53