# 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