In a bipartite graph, the size of a maximum matching equals the size of the minimum vertex cover.
I want to prove above theorem using max-flow-min-cut theorem. So I am trying to find the relationship between min-cut and min vertex cover, do you think |min-cut| = |min-vertex-cover|? If so, any proof for it?
Best Answer
I think your confusion lies in the correspondence between flows in a bipartite graph and maximum matchings. To find a maximum matching, consider the bipartite graph $G=(L,R,E)$ where $L$ is the set of vertices on the left side of the bipartition and $R$ is the set on the right side. Now, add a new vertex $s$ and a directed edge $(s,\ell)$ for each $\ell \in L$. Also, add a new vertex $t$ and a directed edge $(r,t)$ for each $r\in R$. Orient all of the edges in $E$ towards $T$ and set every edge in your new graph to have capacity 1. Below is an example of the resulting graph:
Solve for max flow on this graph with $s$ as your source and $t$ as your terminal. The saturated edges (which were originally in $E$) in a max flow for this graph correspond to the edges in a maximum matching, and the flow value is the size of said matching (convince yourself! i.e. assume you have a max matching that is bigger/ smaller than the flow value and see what that implies).
Now, the flow value also corresponds to the size of a minimum vertex cover, but NOT NECESSARILY the size of a minimum cut. This is because we added a source and a sink node, and the edges from $s$ to $L$ and from $R$ to $t$ which could now be part of our min cut in this new graph. Hope this clears up some confusion.