Bipartite Capacity Graph Theory Proof

Question

$ G = (V,E) $ is a bipartite graph and $ V = V1 ∪ V2 $.

$ U ⊆ V1 $ and is denoted as $ N(U) $ and is the set of all neighbours of $U$ in the graph $G$.

Construct an ordered graph $D = (V’,A)$ of G and all edgdes of G go from $V1$ to $V2$ and add an input $s$ and an output $t$ where there is an edge from $s$ to all vertices in $ V1$ and from all vertices in $V2$ to the output $t$. Choose capacity $c(a)= 1$ for all $a ∈ A$.

$ U ⊆ V'$ is a subset that contains $s$.

$ U1 = V1 ∩ U $ and $ U2 = V2 ∩ U $.

Prove the following:

$cap(δ^+(U)) ≥ |V1∖U1|+ |U2|+ |N(U1)∖U2| $.

$δ^+(U)$ is defined as the edges leaving $U$.

The proof should be very short, however I don't know where to start..Could someone help me?

Answer 1

This is a simple counting argument and it helps a lot to just draw the graph you constructed and consider all possibilities how an edge leaving $U$ can look like. For an edge $e = (v,w)$ (this notation means that the edge is directed from v to w) leaving $U$ it holds that either $v = s$ or $w \in V_2\cup \{t\}$. Now you just have to count:

1. Number of edges going from $s$ to $V_1\backslash U_1$. ( $= |V_1\backslash U_1|$)
2. Number of edges going from $U_1$ to $V_2\backslash U_2$. ( $= |N(U_1)\backslash U_2|$)
3. Number of edges going from $U_2$ to $t$ ( $= |U_2|$).

Since all edges have unit capacity, adding up these numbers yields the desired result.