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

Question

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?

Answer 1

A graph that can be black-white colored is a bipartite graph. Kőnig's theorem says that in any bipartite graph, the size of the minimum vertex cover is equal to the size of a maximum matching.

In the grid graph, there is always a matching that covers all the vertices of the less-popular color. (In the grid graph, it's more popular to think of this matching as a domino tiling, and we can always domino tile either the entire grid, or the entire grid except for a corner.)

So the size of this matching is equal to the number of vertices of the less-popular color, and by Kőnig's theorem, no vertex cover can be smaller than this.

In other bipartite graphs, this is true whenever there is a matching that covers the smaller part of the graph. If that does not hold, the minimum vertex cover will also be smaller.