7 Flows on networks, vertex and edge connectivity 7.2 Vertex and edge connectivity 7.4 Exercises

7.3 Menger’s theorem

Similar to Max-flow min-cut theorem, Menger’s theorem also can be proven under differing frameworks. We shall prove two of them and leave the rest as exercises.

Theorem 7.18.

(Menger’s theorem for edge-connectivity on digraphs) Let $s\neq t$ in a di-graph $G$ . Then we have that

	$\displaystyle\lambda(s,t)$	$\displaystyle:=\max\{k:\mbox{there exist $k$ edge-disjoint $s-t$ directed % paths }\}$
		$\displaystyle=\min\{\|E^{\prime}\|:\mbox{$E^{\prime}$ is an $s-t$ directed cut.}% \}=:C(s,t),$

where $E^{\prime}$ is an $s-t$ directed cut if every directed path from $s$ to $t$ contains at least one edge in $E^{\prime}$ .

As a corollary of the above theorem, we get the following more global result on edge-connectivity of directed graphs. For directed graphs too, we defined edge-connectivity as

\lambda(G):=\min\{|E^{\prime}|:\mbox{$E^{\prime}$ is an $s-t$ directed cut for% some $s\neq t$}\}.

Then Theorem 7.18 yields immediately that

\lambda(G)=\max\{k:\mbox{there exist $k$ edge-disjoint $s-t$ directed paths % for all $s\neq t$}\}.

(7.1)

The proof of Theorem 7.18 proceeds by first showing that deletion of incoming edges at $s$ and outgoing edges at $t$ do not change the LHS or RHS. Then, we shall show that by setting $c\equiv 1$ on $E$ , the LHS equals the max-flow and the RHS equals the min-cut thereby proving the theorem via max-flow min-cut theorem for digraphs.

Figure 7.2: The dotted line shows the minimum directed cut and it can be seen that there are two edge disjoint paths

Proof of Theorem 7.18.

Assume that $\lambda(s,t)>0$ else the theorem holds trivially.

Observe that $\lambda(s,t),C(s,t)$ remain unchanged if we delete incoming edges at $s$ and outgoing edges at $t$ and so we shall assume that there are no incoming edges at $s$ and outgoing edges at $t$ .

Suppose there are $k$ edge-disjoint paths. Then, any $s-t$ edge-cut $E^{\prime}$ has to contain at least one edge from each of the disjoint paths and hence $|E^{\prime}|\geq k$ . Thus, we trivially get that $\lambda(s,t)\leq C(s,t)$ as in the Max-flow Min-cut theorem.

Now we construct a directed network on $G$ by assigning capacity $1$ to every edge. Since $c\equiv 1$ , the max-flow $f$ is integral and further $f\in\{0,1\}$ . Trivially, if $v(f)\geq\lambda(s,t)$ as we can send a unit flow along each of the disjoint paths and strength and flow properties are preserved under addition. Consider the graph $G_{f}:=(V,\{e:f(e)=1\})$ . Since $v(f)\geq 1$ , there is a $s-t$ path $P_{1}$ in the graph $G_{f}$ (see Exercise 7.20 for a more general claim). Now consider the graph $G_{f}-P_{1}$ . This is nothing but the graph $G_{f_{1}}:=(V,\{e:f_{1}(e)=1\})$ where $f_{1}(e)=f(e)-\mathbf{1}[e\in P_{1}]$ . Since $e\to\mathbf{1}[e\in P_{1}]$ is also a flow, by linearity $f_{1}$ is also a flow and further $v(f_{1})=v(f)-1$ . Now, the same argument as above yields that there is a $s-t$ path $P_{2}$ in $G_{f}-P_{1}$ if $v(f_{1})\geq 1$ and also $P_{2}$ is edge-disjoint of $P_{1}$ . Repeating this argument, we can obtain $v(f)$ many edge-disjoint $s-t$ paths i.e., $\lambda(s,t)=MF(s,t):=$ max-flow in $G$ .

By our definition of capacity, note that $C(S,S^{c})=|E\cap(S\times S^{c})|$ for $s\in S,t\notin S$ . Since

\{E^{\prime}\subset E:\mbox{$G-E^{\prime}$ disconnects $s,t$}\}\supset\{E\cap(% S\times S^{c}):s\in S,t\notin S,S\subset V\},

we have that $C(s,t)\leq MC(s,t):=$ min-cut in $G$ . Thus we have that

MF(s,t)=\lambda(s,t)\leq C(s,t)\leq MC(s,t).

Now, from the Max-flow Min-cut theorem for directed graphs (Exercise 7.12), we have that the inequalities are all equalities and the proof is complete. ∎

Exercise 7.19.

Give a direct proof that $C(s,t)=MC(s,t)$ .

Exercise(A) 7.20.

Prove the following more general version of the claim used in the above proof : If $f$ is a $s-t$ flow with $v(f)>0$ , then there exists a directed $s-t$ path in the graph $G_{f}:=\{e:f(e)>0\}$ .

$S\subset V$ is an $s-t$ vertex cut if any directed path from $s$ to $t$ has a vertex in $S$ .

Theorem 7.21.

(Menger’s theorem for vertex-connectivity on digraphs) Let $s\neq t$ in a di-graph $G$ such that $(s,t)\notin E$ . Then we have that

\max\{k:\mbox{there exist $k$ vertex-disjoint $s-t$ directed paths }\}=\min\{|% E^{\prime}|:\mbox{$E^{\prime}$ is an $s-t$ vertex cut.}\}

One can easily obtain a corollary for vertex connectivity similar to (7.1). We leave the statement to the reader.

Proof.

One can try to prove a Max-flow Min-cut theorem for vertex capacities and then use the same to prove Menger’s theorem. But we will use a graph transformation to reduce the vertex-connectivity case to edge-connectivity case itself.

Consider the following enhanced graph $G^{\prime}$ : $V^{\prime}:=\{s,t\}\cup\{x_{1},x_{2}:x\in V-\{s,t\}\}$ and as for the edges $E^{\prime}$ , $s\sim x_{1}$ if $s\sim x$ in $G$ ; $x_{2}\sim t$ if $x\sim t$ in $G$ ; $x_{2}\sim y_{1}$ if $x\sim y$ in $G$ ; $x_{1}\sim x_{2}$ for all $x_{1},x_{2}$ . Set $c(x_{1},x_{2})=1$ for all $x$ and $c\equiv\infty$ otherwise.

Note that any directed $s-t$ path in $G^{\prime}$ is of the form $sa_{1}a_{2}b_{1}b_{2}\ldots z_{1}z_{2}t$ where $sab\ldots zt$ is the corresponding directed $s-t$ path in $G$ . Further if $P_{1},P_{2},\ldots,P_{k}$ are vertex-disjoint $s-t$ paths in $G$ , the corresponding paths in $G^{\prime}$ are trivially edge-disjoint as well. Conversely, let $P^{\prime}_{1},P^{\prime}_{2}$ be two edge disjoint paths in $G^{\prime}$ , say $sa_{1}a_{2}b_{1}b_{2}\ldots z_{1}z_{2}t$ and $sa^{\prime}_{1}a^{\prime}_{2}b^{\prime}_{1}b^{\prime}_{2}\ldots z^{\prime}_{1}% z^{\prime}_{2}t$ respectively. Then edge-disjointness implies that $(a_{1},a_{2})\neq(a^{\prime}_{1},a^{\prime}_{2}),\ldots,(z^{\prime}_{1},z^{% \prime}_{2})$ and similarly $(b_{1},b_{2})$ and so on. Thus, the corresponding paths $P_{1},P_{2}$ in $G$ are vertex-disjoint. Thus we have that

\lambda^{\prime}(s,t):=\mbox{ max edge-disjoint $s-t$ paths in $G^{\prime}$}=% \mbox{ max vertex-disjoint $s-t$ paths in $G$}=:\kappa(s,t).

If $S\subset V-\{s,t\}$ is a $s-t$ vertex cut in $G$ , then $\{(x_{1},x_{2}):x\in S\}$ is an $s-t$ edge-cut in $G^{\prime}$ . In other words, if $C^{\prime}(s,t)$ is the min edge-cut in $G^{\prime}$ and $VC(s,t)$ is the min vertex-cut in $G$ , then we have from the above inclusion that $C^{\prime}(s,t)\subset VC(s,t)$ . Consider a edge-cut $F\subset E^{\prime}$ in $G^{\prime}$ such that $F\subsetneq\{(x_{1},x_{2}):x\in V-\{s,t\}\}$ . If $(y_{2},x_{1})\in F$ (even $y_{2}=s$ is allowed), then replace $(y_{2},x_{1})$ with $(x_{1},x_{2})$ . This yields a cut $F^{\prime}$ such that $|F^{\prime}|\leq|F|$ depending on whether $(x_{1},x_{2})\in F$ or not. Similarly if $(x_{2},y_{1})\in F$ ( $y_{1}=t$ is allowed) then replace this edge by $(x_{1},x_{2})$ . Again we get a cut $F^{\prime}$ such that $|F^{\prime}|\leq|F|$ . Repeating this procedure we get a cut $F^{\prime}\subset\{(x_{1},x_{2}):x\in V-\{s,t\}\}$ and $|F^{\prime}|\leq|F|$ . Setting $S=\{x:(x_{1},x_{2})\in F^{\prime}\}$ , we obtain an $s-t$ vertex cut of $G$ such that $|S|=|F^{\prime}|$ . Thus $VC(s,t)\leq C^{\prime}(S,t)$ and so $C^{\prime}(s,t)=VC(s,t)$ .

Since $\lambda^{\prime}(s,t)=\kappa(s,t)$ and $C^{\prime}(s,t)=VC(s,t)$ , Menger’s theorem for vertex connectivity follows Menger’s theorem for edge connectivity (Theorem 7.18).

∎

Exercise(A) 7.22.

(Menger’s theorem for edge connectivity ; Menger (1927)) Let $G$ be a finite undirected graph and $u$ and $v$ two distinct vertices. Then the size of the minimum edge cut for $v$ and $v$ (the minimum $(u,v)$ -edge cut) is equal to the maximum number of pairwise edge-disjoint paths from $u$ to $v$ .

Exercise(A) 7.23.

(Menger’s theorem for vertex connectivity ; Menger (1927)) Let $G$ be a finite undirected graph, and let $u$ and $v$ be nonadjacent vertices in $G$ . Then, the maximum number of pairwise-internally-disjoint $(u,v)$ -paths in G equals the minimum number of vertices from $V(G)-{u,v}$ whose deletion separates $u$ and $v$ .

See https://en.wikipedia.org/wiki/Menger’s_theorem for versions of Menger’s theorem and variants. Menger’s theorem has more direct proofs as well, see [Sudakov 2019, Chapter3] for example.