Menger's Theorem for Adjacent Terminal Pairs

Why Adjacent Terminals Need a Separate Formulation

Menger’s theorem compares the largest number of disjoint paths between two terminals with the smallest separator between them. When the terminals $s$ and $t$ are adjacent, the edge $st$ is already an $s$-$t$ path. That path can be used alongside other paths, but it cannot be blocked by deleting vertices other than $s$ and $t$. The right approach is to separate the direct path from the alternate paths by first deleting the edge $st$.

All graphs in this tutorial are finite and simple. A path has no repeated vertices. Paths are edge-disjoint if no edge belongs to two of them; they are internally vertex-disjoint if no internal vertex of one belongs to another. The terminals themselves may be shared. An edge cut separating $s$ from $t$ is a set of edges whose deletion leaves no $s$-$t$ path. A vertex separator for nonadjacent terminals is a set $S\subseteq V\setminus\{s,t\}$ whose deletion leaves no $s$-$t$ path. The empty set is allowed as a separator when there was no such path to begin with.

Definition: Let $G$ contain the edge $st$, and let $H=G-st$, meaning that $H$ has the same vertices as $G$ and all the same edges except $st$. Write $p_e(H;s,t)$ for the maximum number of pairwise edge-disjoint $s$-$t$ paths in $H$, and $p_v(H;s,t)$ for the maximum number of pairwise internally vertex-disjoint $s$-$t$ paths in $H$. Write $\lambda_H(s,t)$ for the minimum size of an edge cut separating $s,t$ in $H$, and $\kappa_H(s,t)$ for the minimum size of a vertex separator in $H$.

If $s,t$ are disconnected in $H$, both path-packing numbers are zero, and both minimum separator sizes are zero. Otherwise, the earlier edge and vertex forms of Menger’s theorem apply to $H$, where $s,t$ are nonadjacent. Those theorems state, respectively, that the maximum number of edge-disjoint paths equals the minimum edge-cut size, and that the maximum number of internally vertex-disjoint paths equals the minimum vertex-separator size. Their proofs by augmenting paths and vertex splitting belong to the earlier material on Menger’s theorem.

The Adjacent-Terminal Formulas

Theorem: If $st\in E(G)$ and $H=G-st$, then $$ \begin{aligned} \text{maximum edge-disjoint }s\text{-}t\text{ paths in }G &=1+\lambda_H(s,t),\\ \text{maximum internally vertex-disjoint }s\text{-}t\text{ paths in }G &=1+\kappa_H(s,t). \end{aligned} $$ Equivalently, these numbers are $1+p_e(H;s,t)$ and $1+p_v(H;s,t)$, respectively.

Proof. For edge-disjoint paths, the one-edge path $st$ uses only the edge $st$, which is absent from $H$. It can therefore be added to any edge-disjoint collection of $s$-$t$ paths in $H$. Conversely, in any edge-disjoint collection in $G$, at most one path can use the edge $st$. If a path uses $st$, it must be exactly the one-edge path: a simple path from $s$ to $t$ that uses $st$ has reached its terminal $t$ immediately after traversing that edge, and cannot continue and still be a path ending at $t$. Removing this direct path leaves a collection of paths in $H$. If no path in the collection uses $st$, the whole collection lies in $H$, and adding the direct path increases its size by one. Thus the maximum in $G$ is exactly $1+p_e(H;s,t)$. By edge Menger applied to $H$, $p_e(H;s,t)=\lambda_H(s,t)$.

For internally vertex-disjoint paths, the direct path $st$ has no internal vertices. It can be added to any internally vertex-disjoint collection in $H$. In the other direction, from any such collection in $G$, remove the direct path if it is present; all remaining paths lie in $H$. If it is absent, all paths already lie in $H$. The largest possible collection therefore has size exactly $1+p_v(H;s,t)$. Since $s,t$ are nonadjacent in $H$, vertex Menger gives $p_v(H;s,t)=\kappa_H(s,t)$. This also covers the case when $H$ has no $s$-$t$ path: then the two packing numbers in $H$ and the two minimum separator sizes there are all zero, leaving just the direct path in $G$. $\square$

The added $1$ has a different separator interpretation in each formula. For edges, every cut separating $s$ and $t$ in $G$ must contain $st$. For vertices, no set avoiding $s,t$ can separate them in $G$, because the edge $st$ remains. The vertex-separator count in the theorem refers to alternate paths in $G-st$, not to a vertex separator in $G$.

Worked Example: Two Alternate Routes with Different Internal Vertices

Let $G=(V,E)$, where $V=\{s,t,a,b,c\}$ and $E=\{st,sa,at,sc,cb,bt,ab\}$. Delete $st$ to obtain $H$, with edges $sa,at,sc,cb,bt,ab$.

In $H$, the paths $s,a,t$ and $s,c,b,t$ are internally vertex-disjoint: their internal-vertex sets are $\{a\}$ and $\{c,b\}$. Thus $p_v(H;s,t)\ge2$. Deleting $\{a,b\}$ from $H$ leaves no $s$-$t$ path: the only edge from $s$ to the rest that remains is $sc$, and $c$ has no remaining route onward to $t$. Hence $\kappa_H(s,t)\le2$. By vertex Menger, or by these two bounds, $p_v(H;s,t)=\kappa_H(s,t)=2$. The adjacent-terminal formula gives $1+2=3$ internally vertex-disjoint paths in $G$: $s,t$, $s,a,t$, and $s,c,b,t$.

For edge-disjoint paths in $H$, the same two alternate paths are edge-disjoint. The two edges $sa$ and $sc$ form an edge cut: every path from $s$ must begin with one of them. Thus $p_e(H;s,t)=\lambda_H(s,t)=2$, and $G$ has $1+2=3$ edge-disjoint paths as well.

Check: the three displayed paths in $G$ use pairwise disjoint edge sets, and their internal vertices are disjoint. No fourth edge-disjoint or internally vertex-disjoint path can exist, because deleting $sa,sc$ in $H$ leaves no alternate path and $st$ contributes only one path. The additional edge $ab$ creates further simple routes, such as $s,a,b,t$, but does not increase either packing number.

Vertex Splitting and the Capacity Bound

The vertex-splitting construction turns an internal-vertex restriction into a cut calculation. Apply it to $H=G-st$, not to $G$: otherwise the direct edge would remain a route that no internal split vertex can block. For each internal vertex $v\in V\setminus\{s,t\}$, create two vertices $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$, joined by a directed arc $v_{\mathrm{in}}v_{\mathrm{out}}$ of capacity $1$. Keep $s,t$ unsplit. Replace each undirected edge $uv$ of $H$ by directed arcs in both directions, with capacity $M$, where $M$ is a positive integer. Arcs incident with $s$ or $t$ are attached to the appropriate split copy of the internal endpoint.

A directed $s$-$t$ path in this network represents a path in $H$. It pays capacity $1$ for each internal vertex it uses. In a packing, capacity $1$ on the split arc prevents two paths from sharing that internal vertex. The arcs representing original edges must not become the limiting resource; this is why they receive the larger capacity $M$.

Proposition: If $n=|V(G)|$ and $M>n-2$, a minimum $s$-$t$ cut in the split network crosses no capacity-$M$ arc. Its capacity is the size of a vertex separator in $H$, and the minimum cut capacity equals $\kappa_H(s,t)$.

Proof. If $n=2$, there are no internal vertices and $H$ has no edges, so the split network has no $s$-$t$ route; the empty cut has capacity zero, and the assertion holds. Suppose $n\ge3$. Consider the cut whose source side contains $s$ and every $v_{\mathrm{in}}$, and whose sink side contains $t$ and every $v_{\mathrm{out}}$. No capacity-$M$ arc goes from the source side to the sink side: arcs representing edges between internal vertices go from an out-copy to an in-copy, and so point from the sink side to the source side; arcs incident with $s$ or $t$ also do not cross in the source-to-sink direction. The only crossing arcs are the $n-2$ split arcs, so this cut has capacity $n-2$. Therefore a minimum cut has capacity at most $n-2<M$, and cannot cross a capacity-$M$ arc.

Let $C$ be a minimum cut and let $S$ consist of the internal vertices whose split arcs cross $C$. If there were an $s$-$t$ path in $H-S$, it would give a directed $s$-$t$ path in the split network. Every directed path from the source side of a cut to its sink side must cross a cut arc. The path cannot cross a capacity-$M$ arc, by the first part of the proof; it must therefore cross a split arc belonging to a vertex of $S$. But the path lies in $H-S$, so it uses no such split arc. This contradiction proves that $S$ separates $s,t$ in $H$. The cut capacity is exactly $|S|$, since its crossing arcs are precisely those unit-capacity split arcs. Hence $\kappa_H(s,t)\le |C|$.

Conversely, let $S$ be any vertex separator in $H$. Deleting the split arcs for vertices of $S$ destroys every directed $s$-$t$ path in the split network, because every such path would otherwise correspond to a path in $H-S$. The reachable vertices from $s$ after these arcs are deleted define a cut whose crossing arcs are among those deleted split arcs, so its capacity is at most $|S|$. Taking a minimum over separators gives a cut of capacity at most $\kappa_H(s,t)$. Together with $\kappa_H(s,t)\le |C|$, this proves that the minimum cut capacity equals $\kappa_H(s,t)$, and its cut arcs correspond to a separator of that size. $\square$

The bound on $M$ matters. An arbitrary cut might block a route by crossing a capacity-$M$ arc that represents an original edge, rather than a split arc that represents a vertex. The proof only concludes that a minimum cut uses split arcs, because the explicit cut of capacity $n-2$ is cheaper than any cut crossing an $M$-arc when $M>n-2$.

Worked Example: The Split-Graph Cut

Use the graph in the first example. It has $n=5$, so choose $M=4$, which satisfies $4>5-2=3$. After deleting $st$, the internal vertices are $a,b,c$. The split arcs $a_{\mathrm{in}}a_{\mathrm{out}}, b_{\mathrm{in}}b_{\mathrm{out}}, c_{\mathrm{in}}c_{\mathrm{out}}$ each have capacity $1$; all arcs representing edges of $H$ have capacity $4$.

The set $\{a,b\}$ separates $s,t$ in $H$, so cutting the two split arcs for $a,b$ gives a cut of capacity $1+1=2$. The proposition guarantees that a minimum cut crosses no capacity-$4$ arc. Its crossing arcs therefore correspond to a vertex separator of size equal to the minimum cut capacity. Since the separator $\{a,b\}$ has size $2$, and the two internally disjoint paths $s,a,t$ and $s,c,b,t$ require any separator to meet both, the minimum cut has capacity $2$.

Check: the alternate paths $s,a,t$ and $s,c,b,t$ use different internal vertices, so a separator needs at least two vertices. The set $\{a,b\}$ has two vertices and disconnects $s,t$ in $H$. Thus $\kappa_H(s,t)=2$, matching the cut capacity $2$, which is less than $M=4$.

Worked Example: Only the Direct Path

Let $G$ have $V=\{s,t,x\}$ and $E=\{st,sx\}$. Then $H=G-st$ has only the edge $sx$, so $t$ is isolated in $H$. There are no alternate $s$-$t$ paths: $p_e(H;s,t)=p_v(H;s,t)=0$. The empty set separates $s,t$ in $H$, so $\lambda_H(s,t)=\kappa_H(s,t)=0$. The theorem gives one edge-disjoint path and one internally vertex-disjoint path in $G$, namely $s,t$.

Check: the only edge of $G$ joining $s$ to $t$ is $st$, and the vertex $x$ is a dead end at $s$. Thus neither a second edge-disjoint path nor a second internally vertex-disjoint path exists. In $G$ itself, deleting any set of vertices avoiding $s,t$ leaves the edge $st$, so there is no vertex separator of the terminals in the original graph.

Common Pitfalls and the Practical Meaning

Do not claim that a vertex separator in $G$ handles adjacent terminals. For example, if $st\in E(G)$, deleting all vertices other than $s,t$ still leaves $st$. The correction is to delete $st$ first and ask for a separator of the remaining routes.

Do not confuse an edge cut in $G$ with the alternate-path cut in $H$. In a simple graph, every edge cut separating $s,t$ in $G$ contains $st$. For any partition of the vertices with $s$ on one side and $t$ on the other, the cut edges in $G$ consist of $st$ together with the crossing edges of $H$. Thus the minimum edge-cut size in $G$ is $1+\lambda_H(s,t)$, in agreement with the edge-disjoint path formula.

Do not describe a short list of routes as exhaustive without checking every path. In the first example, $s,a,t$ and $s,c,b,t$ are useful disjoint routes, but they are not all the simple routes: $s,a,b,t$ is another, as is $s,c,b,a,t$. A packing proof needs only to exhibit the paths used; an upper bound needs a separator or cut that accounts for every possible route.

The adjacent-terminal case is useful whenever a network has a direct connection as well as indirect routes. The direct connection contributes one path to either packing count, while the resilience of the alternate routes is measured separately: by an edge cut for edge-disjoint paths, or by a vertex separator for internally disjoint paths. Keeping those roles separate prevents the direct edge from being mistaken for a path that a vertex deletion can eliminate.

Check Your Understanding

In each question, distinguish the direct edge from the paths in the graph with that edge removed.

Suppose $G$ contains $st$, and $G-st$ has exactly one $s$-$t$ path. What are the maximum numbers of edge-disjoint and internally vertex-disjoint $s$-$t$ paths in $G$?
Explain why the empty set is a valid separator in $G-st$ when $s,t$ are already disconnected there.
In a vertex-splitting construction on a graph of order $n$, why does choosing $M>n-2$ ensure a minimum cut cannot cross a capacity-$M$ arc?
Give an example of two edge-disjoint paths that are not internally vertex-disjoint, and explain why edge-disjoint and internally vertex-disjoint counts need not agree.
Why does a vertex separator avoiding $s,t$ fail to separate adjacent terminals in the original graph $G$?

Menger's Theorem for Adjacent Terminal Pairs

What You'll Learn