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.

Now, the result is well-known and 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 doesn't seem to be very motivated, hence I constantly forget its details. However, there is a simple way to "recover" it in your memory using the duality between maximum flow and minimum cut.

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)$$$, finding minimum cut between $$$s$$$ and $$$t$$$ is done as follows:

• Find a maximum flow $$$f$$$ from $$$s$$$ to $$$t$$$ in the network;
• Find $$$X$$$, the set of all vertices reachable from $$$s$$$ in the residual network;
• Minimum cut is formed by $$$S=X$$$ and $$$T=V \setminus X$$$, that is the minimum cut is formed by the edges going from $$$S$$$ to $$$T$$$.

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

• There is an edge of capacity $$$1$$$ going from $$$s$$$ to every vertex from $$$A$$$;
• There is an edge of capacity $$$1$$$ going from every vertex from $$$B$$$ to $$$t$$$;
• There is an edge of capacity $$$+\infty$$$ going between some vertices of $$$A$$$ and $$$B$$$, as defined by the bipartite graph.

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

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

Generally, some vertices from $$$A$$$ and some vertices from $$$B$$$ will be with the source in the min