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$

1 Answer 1

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$ Commented Nov 25, 2017 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$ Commented Nov 25, 2017 at 1:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .