Deriving κ ≤ λ ≤ δ from Menger's Theorem

The Three Connectivity Parameters

The inequality $\kappa(G)\le\lambda(G)\le\delta(G)$ compares three ways a graph can fail to withstand deletions. Vertex connectivity measures how many vertices must be removed to disconnect a connected graph; edge connectivity measures how many edges must be removed; minimum degree gives a simple upper bound on the latter. Menger’s theorem links the first two parameters to disjoint paths between pairs of vertices. The conventions for complete and disconnected graphs matter, so we state them before using the inequality.

Definition: Throughout, $G=(V,E)$ is a finite, nonempty simple graph, and $\delta(G)=\min_{v\in V}\deg(v)$. If $G$ is disconnected, set $\kappa(G)=\lambda(G)=0$. If $G$ is connected and complete of order $n$, set $\kappa(G)=n-1$. For a connected graph of order at least $2$, $\lambda(G)$ is the minimum number of edges whose deletion disconnects it. Set $\lambda(K_1)=0$ by convention: no edge deletion disconnects $K_1$, but the parameter is defined to be $0$. For a connected noncomplete graph, $\kappa(G)$ is the minimum size of a vertex set whose deletion disconnects the graph.

For connected noncomplete graphs, the minimum vertex separator exists: choose two nonadjacent vertices $u,v$, and deleting all neighbors of $u$ separates $u$ from $v$. A vertex separator for $u,v$ is a set $S\subseteq V\setminus\{u,v\}$ such that $u$ and $v$ lie in different components of $G-S$. We will use local connectivity only for nonadjacent pairs, which avoids endpoint complications in the vertex version of Menger’s theorem.

For distinct vertices $u,v$, let $\lambda(u,v)$ be the maximum number of pairwise edge-disjoint $u$-$v$ paths. For nonadjacent $u,v$, let $\kappa(u,v)$ be the maximum number of $u$-$v$ paths that are pairwise internally vertex-disjoint: no internal vertex of one path is an internal vertex of another. The edge and vertex forms of Menger’s theorem, established in the earlier material on Menger’s theorem, say that $\lambda(u,v)$ equals the minimum size of an edge set separating $u$ from $v$, and that $\kappa(u,v)$ equals the minimum size of a vertex separator for $u,v$, respectively.

Reducing the First Inequality to Nonadjacent Pairs

To use vertex Menger’s theorem, we need a nonadjacent pair whose local edge connectivity is $\lambda(G)$. We first justify that such a pair exists in every connected noncomplete graph. For any connected graph of order at least $2$, the minimum of $\lambda(u,v)$ over all distinct pairs equals $\lambda(G)$: every global edge cut separates some pair, and every edge set separating a pair disconnects the graph. The following argument shows that restricting this minimum to nonadjacent pairs does not change it.

Lemma: If $G$ is connected and noncomplete, there are nonadjacent vertices $u,v$ such that $\lambda(u,v)=\lambda(G)$.

Proof. Choose a minimum edge cut $F$, so $|F|=\lambda(G)$, and let $A$ be the vertex set of one component of $G-F$; put $B=V\setminus A$. Every edge of $G$ between $A$ and $B$ belongs to $F$. In fact, $F$ consists exactly of these crossing edges: any deleted edge that is not needed to separate $A$ from $B$ could be restored, giving a smaller edge cut. Suppose first that some $u\in A$ and $v\in B$ are nonadjacent. The cut $F$ separates them, so the edge form of Menger’s theorem gives $\lambda(u,v)\le |F|=\lambda(G)$. Since $\lambda(G)$ is the minimum over all pairs, equality follows.

Otherwise every pair with one endpoint in $A$ and the other in $B$ is adjacent, and $|F|=|A||B|$. Because $G$ is noncomplete, some side $X\in\{A,B\}$ contains a nonadjacent pair $u,v$; let $Y$ be the other side. Write $x=|X|$ and $y=|Y|$. Then $x\ge2$, and the nonadjacency of $u,v$ gives $\deg(u)\le x-2+y$. Also $$ xy-(x-2+y)=(x-1)(y-1)+1\ge1. $$ Thus $\deg(u)<xy=|F|=\lambda(G)$ would contradict the definition of $\lambda(G)$, because deleting the edges incident to $u$ separates $u$ from $v$. More precisely, that deletion shows $\lambda(G)\le\lambda(u,v)\le\deg(u)$, whereas the displayed inequality gives $\deg(u)<\lambda(G)$. Therefore this second case cannot occur. The first case must hold, and it provides the required nonadjacent pair. $\square$

For a nonadjacent pair, internally vertex-disjoint paths are also edge-disjoint. Indeed, if two such paths shared an edge, they would share an endpoint of that edge; since neither path can use the edge $uv$, that shared endpoint would be an internal vertex of both paths. Consequently $\kappa(u,v)\le\lambda(u,v)$. This path comparison is the key step in the first inequality.

Deriving the Inequalities

Theorem: For every finite, nonempty simple graph $G$, $$ \kappa(G)\le\lambda(G)\le\delta(G). $$

Proof. We first handle the cases that do not require a Menger argument. If $G$ is disconnected, our conventions give $\kappa(G)=\lambda(G)=0$, and $\delta(G)\ge0$, so both inequalities hold. If $G=K_1$, then $\kappa(G)=\lambda(G)=\delta(G)=0$ by the stated conventions and the degree definition.

Now suppose $G=K_n$ with $n\ge2$. Our vertex-connectivity convention gives $\kappa(G)=n-1$, and every vertex has degree $n-1$, so $\delta(G)=n-1$. To compute $\lambda(G)$, any edge cut corresponds to a partition of the vertices into nonempty sets of sizes $a$ and $n-a$. The number of crossing edges is $a(n-a)$, and $$ a(n-a)-(n-1)=(a-1)(n-a-1)\ge0. $$ Thus every such cut has at least $n-1$ edges. Isolating one vertex uses exactly $n-1$ edge deletions, so $\lambda(G)=n-1$. The theorem holds with equality for complete graphs.

It remains to consider a connected noncomplete graph. By the lemma, choose nonadjacent $u,v$ with $\lambda(u,v)=\lambda(G)$. Every vertex separator for $u,v$ is a vertex cut of $G$, so its size is at least $\kappa(G)$. The vertex form of Menger’s theorem therefore gives $\kappa(u,v)\ge\kappa(G)$. The path comparison above and the choice of $u,v$ now yield $$ \kappa(G)\le\kappa(u,v)\le\lambda(u,v)=\lambda(G). $$ For the other inequality, choose a vertex $w$ with $\deg(w)=\delta(G)$. Deleting all edges incident to $w$ isolates $w$; since $n\ge2$ and $G$ is connected, at least one other vertex remains. This deletion disconnects $G$, so $\lambda(G)\le\deg(w)=\delta(G)$. Both inequalities follow. $\square$

Worked Examples

Worked Example: A Complete Graph

Let $G=K_4$, with $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$. Compute the three parameters and check the theorem.

Each vertex has degree $3$, so $\delta(G)=3$. By the complete-graph convention, $\kappa(G)=4-1=3$. A cut with one vertex on one side has $1\cdot3=3$ crossing edges; a cut with two vertices on each side has $2\cdot2=4$ crossing edges. These are all possible nontrivial partition sizes, so the minimum edge cut has size $3$, and $\lambda(G)=3$.

Check: $3=\kappa(G)\le\lambda(G)=3\le\delta(G)=3$. Independently, deleting the three edges incident to vertex $1$ isolates it and verifies that an edge cut of size $3$ exists.

Worked Example: A Connected Noncomplete Graph

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24\}$. This is a complete graph on four vertices with edge $34$ omitted.

The degrees are $\deg(1)=3$, $\deg(2)=3$, $\deg(3)=2$, and $\deg(4)=2$. Hence $\delta(G)=2$. Deleting vertex $1$ leaves edges $23,24$, which connect all remaining vertices; deleting vertex $2$ leaves edges $13,14$, also connected. Deleting vertex $3$ leaves the connected triangle on $\{1,2,4\}$, and deleting vertex $4$ leaves the connected triangle on $\{1,2,3\}$. Thus no single vertex disconnects the graph. Deleting $\{1,2\}$ leaves vertices $3,4$ with no edge between them, so $\kappa(G)=2$.

For edge cuts, isolating vertex $3$ removes $13$ and $23$, giving $\lambda(G)\le2$. To check that no smaller cut works, any nontrivial cut is specified by one side of size $1$ or $2$. The four singleton cuts have sizes $3,3,2,2$, respectively. The three distinct partitions into two pairs have crossing-edge counts $4$ for $\{1,2\}\mid\{3,4\}$, $3$ for $\{1,3\}\mid\{2,4\}$, and $3$ for $\{1,4\}\mid\{2,3\}$. Hence $\lambda(G)=2$.

Check: the independently computed parameters give $2=\kappa(G)\le\lambda(G)=2\le\delta(G)=2$.

Worked Example: A Disconnected Graph

Let $G$ have $V=\{a,b,c,d\}$ and $E=\{ab,bc,ca\}$. The vertices $a,b,c$ form a triangle, and $d$ is isolated.

The graph is disconnected, so the conventions give $\kappa(G)=0$ and $\lambda(G)=0$. The degrees are $2,2,2,0$, so $\delta(G)=0$. Thus $0=\kappa(G)\le\lambda(G)=0\le\delta(G)=0$.

Check: no edge deletion is needed to disconnect an already disconnected graph, which is why its global edge connectivity is $0$, not the minimum degree of its nontrivial component.

Why the Conventions Matter

The proof has two distinct ingredients. Menger’s theorem compares path packings with separators for a pair of terminals; the lemma ensures that a pair suitable for vertex Menger’s theorem can be chosen when the whole graph is noncomplete. The second inequality needs no path-packing argument: isolating a minimum-degree vertex is already a certificate that $\lambda(G)\le\delta(G)$, provided the graph is connected and has at least two vertices.

Common pitfall: applying the edge-cut definition literally to $K_1$. One might write, “$\lambda(K_1)$ is the minimum number of edges whose removal disconnects $K_1$,” and then infer that the minimum is $0$. That inference is invalid: $K_1$ has no edge set whose removal disconnects it, since it is already connected and has no edges. The correction is to define $\lambda(K_1)=0$ explicitly by convention. This makes the theorem meaningful for every nonempty graph and agrees with $\delta(K_1)=0$.

Check Your Understanding

Use the definitions and proof above to answer the following questions.

Why does the proof of $\kappa(G)\le\lambda(G)$ choose a nonadjacent pair rather than apply vertex Menger’s theorem to an arbitrary pair?
In the lemma, if every pair crossing the minimum-cut partition is adjacent, why must a noncomplete graph have a nonadjacent pair within one side?
For a connected graph of order at least $2$, explain why removing the edges incident to a minimum-degree vertex disconnects the graph.
Compute $\kappa(G)$, $\lambda(G)$, and $\delta(G)$ for the graph with $V=\{1,2,3\}$ and $E=\{12,23\}$, and verify the inequalities.
Why must the convention $\lambda(K_1)=0$ be stated separately from the edge-deletion definition?