Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
If I'm interpreting your question and comment correctly, you mean a minimum set of edges such that their deletion would make the graph disconnected. Consider the path with $4$ vertices, which is bipartite. You'll need at least two vertices to hit every edge, but deleting any edge will make the graph disconnected, so $|\mathrm{min\;cut}|\neq|\mathrm{min\;vertex\;cover}|$.
Contrary to the suggestions of the other users, I believe this can be proved (the counterexample provided does not address the OP's problem as OP clarified it in the comments).
Let the original graph be $G$, the new graph be $G^\prime$, the vertices on the left be $V_1$, the vertices on the right be $V_2$, and the source and sink be $s$ and $t$ respectively.
$|\text{min cut}| \leq |\text{min vertex cover}|$:
Let $C_1 \cup C_2$, where $C_1 \subseteq V_1, C_2 \subseteq V_2$, be the smallest vertex cover. Consider the following cut:
$S = \{s\} \cup (V_1 \setminus C_1 ) \cup C_2$
Then
$\bar{S} = \{t\} \cup C_1 \cup (V_2 \setminus C_2)$
Note that none of the arcs from $V_1$ to $V_2$ are present in the cut. We can see this as follows. If an arc starts from a vertex in $V_1$ inside the vertex cover, then it is not in $S$ in the first place. If an arc starts from a vertex in $V_1$ not in the vertex cover, then it must end in a vertex in $V_2$ in the cover (otherwise we would not have a vertex cover). Therefore, the arc must not be in the cut, since it connects two vertices within $S$.
As a result, the only arcs in the cut are those from $\{s\}$ to $C_1$ and from $C_2$ to $\{t\}$. The size of this cut is $|C_1 \cup C_2|$, or the size of the minimum vertex cover. Therefore, the size of the min cut is at most the size of the min vertex cover.
$|\text{min cut}| \geq |\text{min vertex cover}|$:
Let the minimum cut be $(S,\bar{S})$. We express the cut as follows:
$S = \{s\} \cup (V_1 \setminus C_1 ) \cup C_2$
$\bar{S} = \{t\} \cup C_1 \cup (V_2 \setminus C_2)$
where $C_1 \subseteq V_1$ and $C_2 \subseteq V_2$. Clearly, the arcs inside this cut consist of all the arcs from $\{s\}$ to $C_1$, from $V_2 \cap C_2$ to $\{t\}$, and from $V_1 \setminus C_1$ to $V_2 \setminus C_2$.
Consider the set $C_1 \cup C_2$. We may expand this set to a vertex cover by adding all the vertices of $V_1 \setminus C_1$ for which an arc from it to $V_2 \setminus C_2$ exists. Obviously the size of this set is the same as the size of the min cut. So the size of the minimum vertex cover is at most the size of the minimum cut and we are done.
