# Is the minimum vertex cover of a grid equal to the part with fewer vertices after coloring?

There is a $n \times m$ grid like:

O---O---O---O
|   |   |   |
O---O---O---O
|   |   |   |
O---O---O---O


Each O indicates a vertex. - and | indicate edges between vertices.

I can get the minimum vertex cover with Hungarian Algorithm, after black-white coloring to transform the grid into a bipartite. But the answer is always the part with fewer vertices in the bipartite.

How to prove this property in math? And is it a property for all connected graph that can be black-white colored?

• Nope. For example, take a tree with two adjacent vertices that each have $100$ leaves. This is a connected bipartite graph with $101$ vertices in each part, but the largest perfect matching only has $2$ edges (and the smallest vertex cover only $2$ vertices). Nov 25 '17 at 1:18