Turning Vertex Restrictions into Capacity Restrictions
To find several paths between two vertices that do not share internal vertices, one can replace the restriction on shared vertices by a capacity rule. Each nonterminal vertex is represented by an input and an output, with a unit-capacity directed edge between them. Any route through that vertex must use the edge, so at most one unit of flow can pass through it. This construction is called vertex splitting.
Throughout, \(G=(V,E)\) is a finite simple undirected graph, and \(s,t\in V\) are distinct terminals. A path is a sequence of distinct vertices with consecutive vertices adjacent. An \(s\)-\(t\) path is internally vertex-disjoint from another if the two paths have no common vertices except possibly \(s\) and \(t\). A path consisting of the edge \(st\), when that edge exists, has no internal vertices.
The superscript “\(-\)” denotes the input side of a split vertex and “\(+\)” its output side. Thus an original edge \(uv\) is represented by an arc from the output side of one endpoint to the input side of the other. All capacities are nonnegative integers. We use \(n\) as a sufficiently large finite capacity: an internally vertex-disjoint path family has at most \(n-1\) members, since its paths must use distinct first edges out of \(s\). The special capacity \(1\) on \(st\) prevents the direct path from being counted more than once.
How Paths Pass Through the Split Network
An original path \(s,v_1,\ldots,v_k,t\), with all \(v_i\) nonterminal, becomes the directed path that follows the corresponding original-edge arcs and, at each \(v_i\), traverses \(v_i^-\to v_i^+\). For example, the original path \(s,a,b,t\) becomes \(s\to a^-\to a^+\to b^-\to b^+\to t\). Conversely, a directed \(s\)-\(t\) path in the network must pass through the split arc whenever it enters a nonterminal vertex, so it translates back to a path in \(G\).
Proof. First take \(q\) pairwise internally vertex-disjoint \(s\)-\(t\) paths in \(G\). Send one unit of flow along the corresponding directed path for each original path. At any nonterminal vertex \(v\), at most one of the original paths uses \(v\), so the total flow through \(v^-\to v^+\) is at most its capacity \(1\). The original-edge arcs also have enough capacity: at most \(q\le n-1\) paths are being routed, and no original edge can be used by two paths if it has a nonterminal endpoint, since that would make them share that endpoint. The edge \(st\) can occur only as the direct path, at most once, and its arc has capacity \(1\). The resulting flow is feasible and has value \(q\).
Now take an integral flow of value \(q\). We can extract \(q\) unit \(s\)-\(t\) paths from it. To justify this, consider the directed arcs carrying positive flow. If there were no positive-flow path from \(s\) to \(t\), let \(R\) be the vertices reachable from \(s\) using positive-flow arcs. Then \(s\in R\), \(t\notin R\), and no positive flow leaves \(R\). Flow conservation at vertices other than \(s,t\) implies that the net flow leaving \(R\) is the value \(q\), contradicting the absence of positive flow leaving \(R\). So there is a positive-flow \(s\)-\(t\) path. Choose one with no repeated network vertices and subtract one unit of flow along it. The remaining flow is nonnegative and integral, still satisfies conservation, and has value \(q-1\). Repeating this argument produces \(q\) unit paths.
Each extracted path that passes through a nonterminal vertex \(v\) uses \(v^-\to v^+\). Since that arc has capacity \(1\), no two extracted paths can use \(v\). Translating the paths back to \(G\) therefore gives \(q\) internally vertex-disjoint paths. These two constructions show that the largest path-family size equals the largest flow value. The standard augmenting-path result for integral capacities guarantees that a maximum flow can be taken integral. \(\square\)
This theorem explains the use of the construction: vertex constraints become ordinary arc-capacity constraints. The network can then be studied using the augmenting-path methods for flows. The next tutorial translates cuts in the split network into vertex separators; the present focus is the path representation.
Worked Constructions
Worked Example: Two Routes and a Direct Edge
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt,st\}\). The graph has the three \(s\)-\(t\) paths \(s,a,t\), \(s,b,t\), and \(s,t\). They are pairwise internally vertex-disjoint: the first two have distinct internal vertices, and the direct path has none.
Here \(n=4\). The split network has vertices \(s,t,a^-,a^+,b^-,b^+\), and unit-capacity arcs \(a^-\to a^+\) and \(b^-\to b^+\). The arcs representing \(sa,at,sb,bt\) have capacity \(4\), and the arc \(s\to t\) has capacity \(1\). The three paths in the network are:
- \(s\to a^-\to a^+\to t\), carrying one unit;
- \(s\to b^-\to b^+\to t\), carrying one unit;
- \(s\to t\), carrying one unit.
The total flow value is \(1+1+1=3\). This is maximum: the original vertex \(s\) has degree \(3\), and distinct internally vertex-disjoint paths must use distinct first edges out of \(s\). Thus there can be at most \(3\) such paths. The construction attains that bound, so the maximum path count and maximum flow value are both \(3\).
Worked Example: A Shared Internal Bottleneck
Let \(V=\{s,a,b,x,t\}\) and \(E=\{sa,ax,sb,bx,xt\}\). There are two routes from \(s\) toward \(x\), but both routes then pass through \(x\) to reach \(t\). In the split network, \(x\) becomes \(x^-,x^+\), joined by the unit-capacity arc \(x^-\to x^+\).
One unit can be sent along \(s\to a^-\to a^+\to x^-\to x^+\to t\). Its flow value is \(1\), and it respects every capacity: it uses each of the split arcs at \(a\) and \(x\) once. The corresponding original path is \(s,a,x,t\).
No flow of value \(2\) is possible, because every \(s\)-\(t\) path in the split network must use \(x^-\to x^+\), whose capacity is \(1\). Equivalently, every original \(s\)-\(t\) path uses the internal vertex \(x\), so two such paths cannot be internally vertex-disjoint. Hence the maximum is exactly \(1\). The second route \(s,b,x,t\) does not create a second internally disjoint path: it still uses \(x\).
Worked Example: Tracing Two Augmentations
Let \(V=\{s,a,b,c,d,t\}\) and \(E=\{sa,ac,ct,sb,bd,dt\}\). The two routes \(s,a,c,t\) and \(s,b,d,t\) have no common internal vertices. Here \(n=6\), so each arc representing an original edge has capacity \(6\); the split arcs \(a^-\to a^+\), \(b^-\to b^+\), \(c^-\to c^+\), and \(d^-\to d^+\) each have capacity \(1\). Starting from zero flow, use the augmenting-path procedure:
| Augmentation | Directed path in the split network | Added flow | Total flow |
|---|---|---|---|
| 1 | \(s,a^-,a^+,c^-,c^+,t\) | \(1\) | \(1\) |
| 2 | \(s,b^-,b^+,d^-,d^+,t\) | \(1\) | \(2\) |
Each augmentation is limited to \(1\) by the unit capacities on the split arcs it uses. After the second augmentation, the total is \(1+1=2\). This is maximum: \(s\) has just two incident edges, \(sa\) and \(sb\), and distinct internally vertex-disjoint paths must start with different edges. Thus no such family can contain more than two paths. The flow and the original paths both attain that bound.
Why the Terminals Are Not Split
The unit capacity is meant to restrict how many paths use an internal vertex. The terminals are allowed to be shared by every path in the family, so their passage must not be limited to one unit. Keeping \(s\) and \(t\) unsplit expresses this distinction directly. The direct edge \(st\) is a special case: it has no internal vertex to impose a unit bottleneck, so its representing arc is assigned capacity \(1\) to ensure that the single edge in a simple graph cannot be counted as multiple paths.
Common mistake. Suppose the graph has \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt\}\). There are two internally vertex-disjoint paths, \(s,a,t\) and \(s,b,t\). If one incorrectly splits \(s\) and gives \(s^-\to s^+\) capacity \(1\), every route must use that single arc, so the computed flow is at most \(1\). That is a false bottleneck: \(s\) is a shared terminal, not a shared internal vertex. Keep \(s\) and \(t\) unsplit; then the two unit-capacity internal arcs, \(a^-\to a^+\) and \(b^-\to b^+\), correctly allow two paths.
Another useful check is to trace a route through each split vertex in order. If a purported network path enters \(v^-\), it must cross \(v^-\to v^+\) before leaving on an arc representing an original edge. That is precisely where the unit capacity enforces the restriction. Conversely, a capacity placed on an original-edge arc is not the device that prevents internal vertices from being shared; it is the split arc that does that.
Check Your Understanding
For each question, distinguish restrictions on internal vertices from restrictions on the terminals.
- For \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt\}\), list the split-network arcs and capacities when \(n=4\).
- Why must an integral flow path that visits \(v\) use the arc \(v^-\to v^+\)?
- If every \(s\)-\(t\) path in a graph uses the same nonterminal vertex \(x\), what feature of the split network bounds the flow value by \(1\)?
- Why is a capacity of \(1\) assigned to the arc representing \(st\), even though neither terminal is split?
- Give an upper bound on the number of internally vertex-disjoint \(s\)-\(t\) paths in terms of \(\deg(s)\), and explain why the paths must respect that bound.