# The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5,

The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\text{Capacity}(S) = |L_2|+|R_1|+\text{edges}(L_1, R_2)$.

Here, $L_1 = S \cap L$, $L_2 = L \setminus S$, $R_1 = S \cap R$ and $R_2 = R \setminus S$. Furthermore, $L$ are the left edges and $R$ are the right edges.

I don't understand how he arrived at the conclusion that

number of edges that go from $S$ to $\overline{S} = |L_2|+|R_1|+\text{edges}(L_1, R_2)$

I don't understand the meaning of this expression. I drew it out on paper (highlighting all graph elements of the expression) and I still don't get it. Could somebody please explain to me how this expression is generated in simple and detailed terms?

• What attempts have you made on your own? Have you tried working through some examples (with small graphs and cuts)?
– D.W.
Commented Apr 18, 2014 at 0:21

The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are:
1. Edges from $s$ to $\overline{S}$, that is, from $s$ to $\overline{S} \cap L$. There are $|L_2|$ of these.
2. Edges from $S$ to $t$, that is, from $S \cap R$ to $t$. There are $|R_1|$ of these.
3. Edges from $S \setminus \{s\}$ to $\overline{S} \setminus \{t\}$, that is, from $S \cap L$ to $\overline{S} \cap R$. There are $\mathrm{edges}(L_1,R_2)$ of these.
It is crucial that in $G'$ the edges are oriented, and that when counting edges crossing the cut $(S,\overline{S})$, we only count edges going from $S$ to $\overline{S}$.