World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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?

###### Answered By : Yuval Filmus

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}$.