0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can we say that for any connected bipartite the size of perfect match is always the size of the part with fewer vertices? $\endgroup$ Nov 25 '17 at 1:15
  • 1
    $\begingroup$ 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). $\endgroup$ Nov 25 '17 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.