Path-Packings and Separators as Menger Certificates

Two Sides of a Connectivity Certificate

For a specified pair of vertices, a connectivity claim has two parts: how many routes can be kept apart, and how small a deletion can destroy all routes. A family of disjoint paths proves that the pair has at least that much connectivity. A separator proves that it has at most that much. When the two numbers agree, the certificates establish the exact value without requiring us to list every possible path or every possible deletion.

All graphs in this tutorial are finite and simple. Fix distinct vertices \(s,t\) that are not adjacent. An \(s\)-\(t\) path is a sequence of distinct vertices beginning at \(s\) and ending at \(t\), with each consecutive pair joined by an edge. Its internal vertices are all vertices on the path other than \(s\) and \(t\). Paths are internally vertex-disjoint if no internal vertex of one is an internal vertex of another. They are edge-disjoint if no edge belongs to more than one path. Edge-disjoint paths may share internal vertices.

The nonadjacency assumption matters for vertex separators: if \(st\) were an edge, deleting vertices other than \(s,t\) would leave that direct path intact. The vertex-pair version of Menger’s theorem therefore uses a separate convention for adjacent terminals, treated in the later material on adjacent terminal pairs. The edge definitions above do not need this restriction, but our examples use nonadjacent terminals for both kinds of certificate.

Why Matching Certificates Give Exact Values

Proof. First consider the vertex statement. The displayed family of \(k\) internally vertex-disjoint paths proves \(\kappa_G(s,t)\ge k\), by the definition of the maximum. Let \(S\) be a vertex separator. Every one of the \(k\) paths must contain an internal vertex in \(S\); otherwise that path would remain in \(G-S\), contradicting that \(S\) separates \(s\) from \(t\). Since the paths have disjoint internal vertices, the vertices of \(S\) that meet different paths must be distinct. Thus \(|S|\ge k\). If a separator has size \(k\), these bounds give \(\kappa_G(s,t)=k\).

For the edge statement, the \(k\) edge-disjoint paths give \(\lambda_G(s,t)\ge k\). Every edge separator \(F\) must contain at least one edge from each displayed path; otherwise that path survives in \(G-F\). Because the paths are edge-disjoint, these required edges are distinct, so \(|F|\ge k\). If \(|F|=k\), the lower and upper bounds give \(\lambda_G(s,t)=k\). \(\square\)

The theorem gives a practical proof pattern. To show that a value is exactly \(k\), provide \(k\) paths of the required kind and a separator containing \(k\) vertices or edges. The paths and separator need not be uniquely determined. They do need to be checked against the correct notion of disjointness.

This certificate pattern is consistent with the vertex and edge forms of Menger’s theorem, established in the earlier material on Menger’s theorem. Those results say that the maximum number of paths in question equals the minimum size of the corresponding separator. The certificate proof above only needs the direct bounds: paths give a lower bound, and separators give an upper bound.

Worked Vertex Certificates

Worked Edge Certificates

Reading and Checking a Certificate

A certificate is more than a list of routes and a set of the right numerical size. Each object must meet its definition. For a vertex certificate, check that the paths are internally vertex-disjoint and that deleting the proposed vertices really leaves no terminal-to-terminal path. For an edge certificate, check that no path edge is repeated and that deleting the proposed edges really disconnects the terminals.

A useful way to verify a proposed separator is to identify why every possible path must meet it. For example, a set containing all neighbors of \(s\), when \(s\) is not adjacent to \(t\), is a vertex separator; a set containing all edges incident to \(s\) is an edge separator. Other separators can lie farther from the terminal, as \(\{c,d\}\) did in the layered example. In either case, the reasoning must rule out every route, not merely the routes already listed.

These are local statements about the fixed pair \(s,t\). They do not, by themselves, determine the global vertex connectivity \(\kappa(G)\) or global edge connectivity \(\lambda(G)\), which concern the graph as a whole. A certificate for one pair proves the corresponding local value only.

Common Pitfall: Counting the Wrong Kind of Disjointness

In the layered graph of the second example, the paths \(s,a,c,t\) and \(s,b,d,t\) are both internally vertex-disjoint and edge-disjoint. But in other graphs, edge-disjoint paths may share internal vertices, so an edge-path count cannot automatically be used as a vertex-path count. Conversely, paths that share no internal vertices are necessarily edge-disjoint in a simple graph, but the two notions have different separator bounds.

There is also a common error in the upper-bound argument. In the layered example, suppose someone proposes \(S=\{a,c\}\) as a separator and concludes that \(\kappa_G(s,t)\le 2\). This set has size \(2\), but it is not a separator: after deleting \(a,c\), the path \(s,b,d,t\) remains. The correction is to test the proposed deletion against all paths; \(S=\{c,d\}\) works because every route into \(t\) must use one of those vertices. A set of the desired size is not a certificate unless it actually disconnects the terminals.