Two Certificates for a Path-Packing Calculation
For a specified pair of vertices, the key calculation is often not simply to find a path, but to determine how many routes can be used without sharing internal vertices. A second task is to find a small set of vertices whose deletion blocks every route between the pair. These two objects provide complementary checks: paths show that many routes are possible, while a separator shows that no more are possible.
Throughout, graphs are finite and simple. Fix distinct, nonadjacent vertices \(s,t\) of a graph \(G=(V,E)\). A path is a sequence of distinct vertices with consecutive vertices adjacent. The internal vertices of an \(s\)-\(t\) path are all its vertices except \(s\) and \(t\). A family of \(s\)-\(t\) paths is internally vertex-disjoint if every two paths in the family have no common internal vertex. They may share the endpoints \(s,t\).
For a nonadjacent pair \(s,t\), the vertex form of Menger’s theorem says that the maximum number of internally vertex-disjoint \(s\)-\(t\) paths equals the minimum size of an \(s\)-\(t\) vertex separator. This is the standard result proved in the earlier material on vertex Menger, including the endpoint conventions for the theorem. Here we use it as a guide for computation: exhibit paths for a lower bound, then exhibit a separator for an upper bound.
How to Check a Proposed Answer
A list of paths alone does not prove maximality. Nor does a separator alone show that its size is the answer. The efficient check is to verify both objects and compare their sizes. For a path family, list the internal vertices of every path and check that these lists are pairwise disjoint. For a separator, delete its vertices and verify that no route from \(s\) to \(t\) remains.
Proof. Every path in \(\mathcal P\) must meet \(S\) internally. Otherwise that path would still be present after deleting \(S\), contrary to the definition of separator. Choose, for each path, one of its internal vertices in \(S\). No two paths can be assigned the same vertex, because the paths are internally vertex-disjoint. This gives an injection from \(\mathcal P\) into \(S\), so \(|\mathcal P|\le |S|\). \(\square\)
Proof. The paths show that the maximum number is at least \(k\). The proposition shows that every internally vertex-disjoint path family has size at most \(|S|=k\). Thus the maximum is exactly \(k\). The same paths and proposition show that every separator has size at least \(k\), while the exhibited \(S\) has size \(k\). Therefore the minimum separator size is \(k\) as well. \(\square\)
Worked Calculations
Worked Example: Two Routes Through Two Different Vertices
Let \(V=\{s,t,a,b\}\) and \(E=\{sa,at,sb,bt\}\). The terminals \(s,t\) are nonadjacent. Find the maximum number of internally vertex-disjoint \(s\)-\(t\) paths and a minimum separator.
First list the routes through the two intermediate vertices. The path \(P_1=s,a,t\) has internal vertex set \(\{a\}\), and \(P_2=s,b,t\) has internal vertex set \(\{b\}\). Since \(\{a\}\cap\{b\}=\varnothing\), these two paths are internally vertex-disjoint. Thus the maximum is at least \(2\).
| Step | Check | Result |
|---|---|---|
| 1. Construct paths | \(P_1=s,a,t\); \(P_2=s,b,t\) | Two candidate paths |
| 2. Compare interiors | \(\{a\}\cap\{b\}=\varnothing\) | Both paths can be used |
| 3. Test a separator | Delete \(S=\{a,b\}\) | No edge or path remains from \(s\) to \(t\) |
Deleting \(a\) and \(b\) removes all four edges, so \(S=\{a,b\}\) is a separator. Its size is \(2\), matching the two paths. By the certificate corollary, the maximum number of internally vertex-disjoint paths is \(2\), and the minimum separator size is \(2\).
Check: the internal-vertex count is \(1+1=2\) distinct vertices for the two displayed paths, and \(|S|=|\{a,b\}|=2\). A larger path family would require more vertices in the separator than it contains, contradicting the proposition.
Worked Example: Three Routes in a Complete Bipartite Graph
Let \(V=\{s,t,a,b,c\}\) and \(E=\{sa,at,sb,bt,sc,ct\}\). This is \(K_{2,3}\), with parts \(\{s,t\}\) and \(\{a,b,c\}\). The terminals \(s,t\) are nonadjacent. Compute the path maximum and a minimum separator.
There are three displayed paths: \(P_a=s,a,t\), \(P_b=s,b,t\), and \(P_c=s,c,t\). Their internal vertex sets are \(\{a\}\), \(\{b\}\), and \(\{c\}\). These sets are pairwise disjoint, so the three paths form an internally vertex-disjoint family.
| Step | Candidate or test | Result |
|---|---|---|
| 1. Use the first middle vertex | \(s,a,t\), interior \(\{a\}\) | One path |
| 2. Use a different middle vertex | \(s,b,t\), interior \(\{b\}\) | Two disjoint paths |
| 3. Use the remaining middle vertex | \(s,c,t\), interior \(\{c\}\) | Three disjoint paths |
| 4. Delete all middle vertices | \(S=\{a,b,c\}\) | \(s\) and \(t\) are disconnected |
After deleting \(S\), the only vertices left are \(s,t\), and \(st\notin E\), so no \(s\)-\(t\) path remains. The path family has size \(3\), and the separator has size \(|S|=|\{a,b,c\}|=3\). Hence the exact maximum and minimum are both \(3\).
Check: each displayed path uses one of the three internal vertices, and no two use the same one. Deleting precisely those three vertices removes all six edges listed in the graph, confirming that the proposed set really is a separator.
Worked Example: Three Neighbors Do Not Guarantee Three Disjoint Paths
Let \(V=\{s,t,a,b,c,x,y\}\) and \(E=\{sa,sb,sc,ax,ay,bx,by,cx,cy,xt,yt\}\). The terminals \(s,t\) are nonadjacent. Although \(s\) has three neighbors, determine the maximum number of internally vertex-disjoint paths.
Two paths can be chosen as \(P_1=s,a,x,t\) and \(P_2=s,b,y,t\). Their internal vertex sets are \(\{a,x\}\) and \(\{b,y\}\), which are disjoint. Therefore at least two paths are possible.
| Step | Check | Result |
|---|---|---|
| 1. First route | \(s,a,x,t\), interior \(\{a,x\}\) | Valid path |
| 2. Second route | \(s,b,y,t\), interior \(\{b,y\}\) | Interior disjoint from the first |
| 3. Test the bottleneck | Delete \(S=\{x,y\}\) | \(t\) has no remaining incident edge |
The set \(S=\{x,y\}\) is a separator: the only edges incident with \(t\) are \(xt\) and \(yt\), and both disappear when \(x,y\) are deleted. Thus the exhibited two paths and separator of size \(|S|=|\{x,y\}|=2\) certify that the maximum is exactly \(2\), despite the three edges leaving \(s\).
Check: after deleting \(x,y\), the remaining vertices are \(s,t,a,b,c\); none of the listed edges joins \(t\) to any of them. The surviving two paths use distinct internal vertices, so both sides of the certificate have size \(2\).
A tempting but incorrect third path is \(s,c,x,t\). It cannot be added to \(P_1\), because both paths use the internal vertex \(x\). For instance, the three paths \(s,a,x,t\), \(s,b,x,t\), and \(s,c,y,t\) are not internally vertex-disjoint: the first two share \(x\). The correction is to check the entire internal-vertex set of each path, not just its first step from \(s\).
Common Pitfalls and a Reliable Routine
Counting paths that share internal vertices. Distinct sequences of vertices need not be internally vertex-disjoint. In the last example, choosing different first neighbors \(a,b,c\) does not suffice: two routes can still merge at \(x\). Write down each path’s full interior and compare those sets.
Deleting a terminal is not allowed. A set containing \(s\) or \(t\) does not count as an \(s\)-\(t\) vertex separator under the convention used here. For example, \(\{s\}\) is not a valid one-vertex separator simply because deleting it removes every path starting at \(s\). A valid separator must be contained in \(V\setminus\{s,t\}\).
A path family is a lower bound, not an upper bound. Finding two internally disjoint paths proves only that at least two exist. To prove the maximum is two, also find a separator of size two, or otherwise establish an upper bound. Matching path and separator sizes give a concise certificate that can be checked directly.
For a small graph and nonadjacent terminals, use this routine:
- Write down candidate \(s\)-\(t\) paths and list each path’s internal vertices.
- Keep a family only when those internal-vertex sets are pairwise disjoint.
- Look for a set of nonterminal vertices whose deletion leaves no \(s\)-\(t\) path.
- Check deletion in the graph itself: verify that every possible route is blocked, not merely that one chosen route is blocked.
- Compare the path count with the separator size. Equality certifies both optima by Menger’s theorem and the proposition above.
Check Your Understanding
For each question, state the internal vertices or deleted set explicitly, and explain how your check supports the conclusion.
- In the graph \(V=\{s,t,a,b,c\}\), \(E=\{sa,at,sb,bt,sc,ct\}\), give three internally vertex-disjoint paths and a separator of the same size.
- Explain why a family of four internally vertex-disjoint paths cannot coexist with a separator of size three.
- In the last worked example, why does deleting \(\{x,y\}\) separate \(s\) from \(t\), even though \(s\) remains connected to some of \(a,b,c\)?
- Give a concrete pair of paths with different first internal vertices that nevertheless fail to be internally vertex-disjoint.
- Why must an \(s\)-\(t\) vertex separator exclude \(s\) and \(t\) in these calculations?