# [Math] the relation between min-vertex cover and min-cut in a bipartite graph

combinatoricsgraph theory

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?

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.