From Wikipedia:

König's theorem states that, in bipartite graphs, the maximum matching

is equal in size to the minimum vertex cover.Via this result, the

minimum vertex cover, maximum independent set, and maximum vertex

biclique problems may be solved in polynomial time for bipartite

graphs.

König's theorem states about the relation between sizes of the maximum matching

and of the minimum vertex cover, not about conversion between any two of the four: the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique. So I wonder how to understand the sentence in bold?

Thanks!

## Best Answer

König's theorem says that two (normally different) problems--min vertex cover and max matching--become the same on bipartite graphs. The wikipedia page for König's theorem gives an example of the conversion. The other two problems are equivalent to these two.

Min vertex cover is trivially the same as max independent set (a set of vertices forms a min cover iff all vertices

notin the set are independent; see the wikipedia page for vertex cover for more details).Every independent set induces a clique in the complement graph (or a biclique in the case of bipartite graphs) so this problem too easily reduces from the others.