Kőnig's theorem through min-cut/max-flow duality

Kőnig's theorem through min-cut/max-flow duality

Hi everyone!

There is a somewhat well-known result about bipartite graphs which is formulated as follows:

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.

It is most likely well known to those familiar with the topic, but still might be of interest to someone.

Recall that given a flow network G=(V,E)G=(V,E), finding minimum cut between ss and tt is done as follows:

• Find a maximum flow ff from ss to tt in the network;
• Find XX, the set of all vertices reachable from ss in the residual network;
• Minimum cut is formed by S=XS=X and T=V∖XT=V∖X, that is the minimum cut is formed by the edges going from SS to TT.

Now, recall that bipartite matching between sets of vertices AA and BB may be found as maximum flow in the following network:

• There is an edge of capacity 11 going from ss to every vertex of AA;
• There is an edge of capacity 11 going from every vertex of BB to tt;
• There is an edge of capacity +∞+∞ going between some vertices of AA and BB, as defined by the bipartite graph.

Now... Is there anything special about minimum cut in such network?

Minimum cut (S,T)(S,T) in a flow network induced by a bipartite graph

Generally, some vertices from AA and some vertices from BB will be with the source ss in the cut, while other will be with the sink tt.

Let A=AS∪ATA=AS∪AT and B=BS∪BTB=BS∪BT, such that AS,BS⊂SAS,BS⊂S and AT,BT⊂TAT,BT⊂T. Then the following is evidently true:

• There are no edges from ASAS to BTBT (otherwise the cut would be infinite);
• Thus, every edge in the bipartite graph is incident to some vertex from ATAT or BSBS (or both);
• Minimum cut is formed only by edges going from SS to ATAT and from BSBS to TT and thus its size is |AT|+|BS||AT|+|BS|.

Putting it all together, the minimum vertex cover is AT∪BSAT∪BS, and it can be easily found from the minimum cut:

1. Find a minimum cut (S,T)(S,T) in the flow network of the maximum matching on bipartite graph with parts AA and BB;
2. A minimum vertex cover is comprised of the sets AT=(A∩T)AT=(A∩T) and BS=(B∩S)BS=(B∩S).