Menger's Theorem

Definition (Minimum to Disconnect)

If $u,v\in G$, that are not neighbors, then define $\kappa (u,v)$ as the minimum number of vertices to disconnect $u$ from $v$.

Example:

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n$

source code

Here, we see that $\kappa (u,v)=2$, by removing vertices $a,b$. We can describe the set of Cut vertices as the cutset of $u,v$.

Lemma (Minimum Cut: Unique Paths)

If $\kappa >1$ then $u,v$ are in the same block since we have no cut vertex to separate them. But then this means they share the same cycle by theorem.

If we $\ell$ vertex-disjoint $u\to v$ paths, then $\kappa \ge \ell$ as a lower bound.

  graph LR;
  u((u)) o--o v((v));
  u o---o v;
  u o---o v;
  u o---o v;
u o---o v;

where cutting any path here still gives us another $\ell -1$ paths to cut.

We require vertex-disjoint because if two paths overlap, then removing the overlapping vertex disconnects both paths.

Menger’s Theorem (Vertex Form)

If $u,v\in G$, two non-adjacent vertices in a finite Graph, then it is possible to find $\kappa (u,v)$ many vertex-disjoint paths.

Proof: We proceed with strong induction on $|E|$.

Base Case: If $|E|=0$, then we can find $0$ paths, and thus $\kappa =0$. The theorem holds.

Inductive Step: Let $|E|=m$. Assume Menger’s Theorem holds for all graphs with $<m$ edges. Let $W$ be the minimum $u\to v$ vertex cutset of size $\kappa =\kappa (u,v)$,

graph LR;
	u[Hu] o--o w[[W]];
	w o--o v[Hv];
	u o--o w;
	u o--o w;
	u o--o w;
	v o--o w;
	v o--o w;
	v o--o w;

where $W$ is our cutset. We see that in graph $G-W$, it forms at least two connected components. Denote $H_v$ as the subgraph with the vertex $v$ and likewise with $H_u$.

We can form two new graphs by graph contraction:

$$\begin{array}{rl}{G}_u& :=V(H_u)\to u^{\prime }\\ G_v& :=V(H_v)\to v^{\prime }\end{array}$$

giving us graph $G_u$

graph LR;
	u((u')) o--o w[[W]];
	w o--o v[Hv];
	u o--o w;
	u o--o w;
	u o--o w;
	v o--o w;
	v o--o w;
	v o--o w;

and graph $G_v$

graph LR;
	u[Hu] o--o w[[W]];
	w o--o v((v'));
	u o--o w;
	u o--o w;
	u o--o w;
	v o--o w;
	v o--o w;
	v o--o w;

In graph $G_u$, cutset $W$ is a $u^{\prime }\to v$ cut of size $\kappa$. By definition of $W$, this must be the minimum, such that ${\kappa }_{G_u}(u^{\prime },v)=\kappa$. Symmetrically, ${\kappa }_{G_v}(u,v^{\prime })=\kappa$.

Since we did strong induction, we can apply the inductive hypothesis on $G_u$ and $G_v$. We have three cases:

Case 1: Suppose $H_u\ne \{u\}$ and $H_v\ne \{v\}$. WLOG, upon graph contraction, we reduce the number of edges by at least one, such that $|E(G_u)|<m$.

Then we can apply the inductive hypothesis such that on $G_u$, there are $\kappa$ vertex-disjoint $u^{\prime }\to v$ paths, corresponding to the $W\to v$ paths in $G$ from $H_u$. Likewise, on $G_v$ there are $\kappa$ vertex-disjoint $u\to v^{\prime }$ paths, corresponding to the $u\to W$ paths in $G$ from $H_v$.

As $H_u\cap H_v=\varnothing$, then these two paths only intersect at $W$. Thus, we get $\kappa$ total vertex-disjoint paths from $u\to v$ in $G$.

Case 2: Suppose $H_u=\{u\}$ and $H_v=\{v\}$. Then trivially, neighborhood¹ $N(u)=N(v)=W$, which must be the minimal cut set.

Case 3: WLOG, $H_u=\{u\}$ and $H_v\ne \{v\}$. We need strictly less than $m$ edges to apply the IH. The inductive steps fails here, since any minimum cut $W$ results in one of the contracted graphs having $m$ edges (since we do not remove any internal edges from $G_u$ or $G_v$).

We know here that $W=N(u)$ since $u$ has no other neighbors in $H_u$.

Case 3A: Suppose $x\in N(u)\cap N(v)$. Then any cutset $W$ over $u\to v$ must contain $x$. Consider a new graph $G^{\prime }=G-\{x\}$, which has fewer edges than $G$. Since $x$ is in every $W$, then min-cut $W^{\prime }$ of $G^{\prime }$ has size ${\kappa }^{\prime }=\kappa -1$. By the inductive hypothesis, there are $\kappa -1$ vertex-disjoint $u\to v$ paths in $G^{\prime }$ and thus $G$. But then we also have another path $u\to x\to v$ which exists in $G$ and is vertex-disjoint.

This gives us a total of $\kappa -1+1=\kappa$ vertex-disjoint $u\to v$ paths, and we are done.

Case 3B: Suppose $N(u)\cap N(v)=\varnothing$. Then every vertex $w\in W$ is adjacent to either only to $u$ only to $v$, but not both. Since $|E(G)|>0$, then there must be some edge $e=(x,y)$ where $x\in N(u)$ and $y\in H_v$.

graph LR;
    u((u));
    y((y));

    subgraph W
        Nu;
        x;
    end

    u o--o Nu;
    u o--o Nu;
    u o--o Nu;
    u o--o x;
    
    x o--e--o y;

Let graph $G^{\prime }=G-\{e\}$. Then we can apply the inductive hypothesis on $G^{\prime }$ such that ${\kappa }_{G^{\prime }}(u,v)={\kappa }^{\prime }$. But removing an arbitrary edge may or may not reduce $\kappa$, such that

$${\kappa }_{G^{\prime }}(u,v)={\kappa }^{\prime }\le \kappa ={\kappa }_G(u,v)$$

This gives us two cases:

Case 3BA: If ${\kappa }^{\prime }=\kappa$, then by the inductive hypothesis, we get that $G^{\prime }$ has a $\kappa$ many vertex-disjoint $u\to v$ paths, which are also paths in $G$.

Case 3BB: It is possible that the set that we cut is all of the neighbors of $u$, such that ${\kappa }^{\prime }<\kappa$. Since we remove one edge, then we can only remove $u\to v$ path, such that ${\kappa }_{G^{\prime }}(u,v)=\kappa -1$. By the induction hypothesis, we have $\kappa -1$ vertex-disjoint $u\to v$ paths in $G^{\prime }$.

Let $W^{\prime }$ be the minimum cutset in $G^{\prime }$ for $u,v$. We know $|W^{\prime }|=\kappa -1$. But then $W^{\prime }$ is not a $u\to v$ cutset in $G$ since the minimum is of size $\kappa$. Indeed, this means there are some vertices we “miss” from cutting $W^{\prime }$ in $G$. Since the only difference is $e$, then we can construct some path $P$ in $G$ that must use $e$. This gives

$$P:u\to x\to y\to v$$

So, $W=W^{\prime }\cup \{x\}$. But then this can be true for $y$, such that

graph LR;
    u((u));
    y((y));
	x;
	
    subgraph W
        Nu;
        y;
    end

    u o--o Nu;
    u o--o Nu;
    u o--o Nu;
    u o--o x;
    
    x o--e--o y;

In this case, if $y\in N(v)$ we defer to Case 2. If not, then as $W^{\prime }$ is a minimal cut for $G^{\prime }$ by IH, adding $e$ to $G^{\prime }$ gives path $P$. Then by the same logic as Case 3A, $W^{\prime }\cup \{y\}$ is a cutset with $\kappa -1+1=\kappa$. Then apply Case 1 with $H_u=\{u,x\}$ and we are done.

Case 4: We have the case where $\kappa =1$ such that $G$ is $u\to x\to y\to v$ only. Then any $x,y$ is a cutset and we are done.

This completes the proof.

See link, which closest resembles the proof in class.

Menger’s Theorem (Weak Edge Form)

Let $\lambda (u,v)$ represent the minimum number of removed edges to separate $u$ from $v$. Then

$$\lambda (u,v)\ge \text{max number of edge-disjoint paths from }u\to v$$

Equality is true. But this is proved in the Maxflow-Mincut Theorem which will be proved later in the course.

Footnotes

1. Fix $u\in V(G)$. For every edge $(a,u)$, $N(u)$ is the set of such $a$. ↩