Paths and Separators for a Specified Pair
To understand how strongly two vertices are connected, it helps to look at two complementary objects: routes that avoid sharing internal vertices, and sets of vertices whose removal destroys every route between the pair. These objects answer different questions. A collection of disjoint paths exhibits multiple ways to travel between two terminals; a separator identifies a bottleneck that all such travel must pass through.
Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. If \(P\) is an \(s\)-\(t\) path, its internal vertices are its vertices other than \(s\) and \(t\). Two \(s\)-\(t\) paths are internally vertex-disjoint if their sets of internal vertices are disjoint. They may share the endpoints \(s\) and \(t\).
A separator removes vertices, not edges. A set \(S\) is a separator precisely when every \(s\)-\(t\) path meets \(S\): deleting \(S\) destroys a path exactly when at least one of its vertices is deleted. In particular, if \(s\) and \(t\) are already disconnected, the empty set is a separator. We exclude the terminals themselves from separators so that the question concerns internal bottlenecks.
There are two useful ways to compare separators. A separator is inclusion-minimal if none of its proper subsets is a separator. It is a minimum separator if its cardinality is as small as possible among all separators for the pair. An inclusion-minimal separator need not be minimum: minimality compares subsets, while minimum size compares cardinalities across all separators.
A Basic Relationship
Proof. Suppose first that \(S\) is a separator. If some \(s\)-\(t\) path contained no vertex of \(S\), all its vertices and edges would remain in \(G-S\), so it would still be an \(s\)-\(t\) path there. This contradicts the definition of separator. Conversely, suppose every \(s\)-\(t\) path contains a vertex of \(S\). Any path in \(G-S\) would also be a path in \(G\) avoiding \(S\), contradicting that supposition. Thus \(G-S\) has no \(s\)-\(t\) path, and \(S\) is a separator. \(\square\)
Proof. Let the paths be \(P_1,\dots,P_k\), and let \(S\) be any \(s\)-\(t\) separator. By the preceding proposition, each \(P_i\) contains a vertex of \(S\). Since \(s\) and \(t\) are excluded from \(S\), this vertex must be internal to \(P_i\). The paths have disjoint internal vertex sets, so the vertices of \(S\) chosen from the \(k\) paths must be distinct. Therefore \(|S|\ge k\). The nonadjacency assumption ensures there is no direct \(s\)-\(t\) edge, whose path has no internal vertex for a separator to meet. \(\square\)
The converse statement for nonadjacent vertices is the vertex form of Menger’s theorem: the maximum number of pairwise internally vertex-disjoint \(s\)-\(t\) paths equals the minimum size of an \(s\)-\(t\) vertex separator. Its proof is given later in the course. The proposition above is the direction that follows directly by counting: each disjoint path needs a different separator vertex.
Finding Separators in Explicit Graphs
Worked Example: Two Routes Through Two Internal Vertices
Let \(G=(V,E)\), where \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt,ab\}\). For the pair \(s,t\), find internally disjoint paths and a minimum separator.
The paths \(P_1=(s,a,t)\) and \(P_2=(s,b,t)\) are both present: their consecutive pairs \(sa,at\) and \(sb,bt\) are edges. Their internal vertex sets are \(\{a\}\) and \(\{b\}\), whose intersection is empty. Thus these are two internally vertex-disjoint paths.
Now test the possible single-vertex separators. The only vertices allowed in a separator are \(a\) and \(b\). Deleting \(a\) leaves \(P_2=(s,b,t)\), so \(\{a\}\) is not a separator. Deleting \(b\) leaves \(P_1=(s,a,t)\), so \(\{b\}\) is not a separator. Deleting both \(a\) and \(b\) leaves only \(s\) and \(t\), with no edge \(st\), so \(\{a,b\}\) is a separator. The empty set is not a separator because \(P_1\) remains.
Therefore the minimum separator has size \(2\), and the two displayed paths match that size. This verifies the path-separator relationship directly in this graph. The additional edge \(ab\) does not create a smaller separator: after deleting either one of \(a,b\), the other still supplies a route between \(s\) and \(t\).
Check: \(s\) and \(t\) are nonadjacent, and the paths have distinct internal vertices. Every separator must meet both paths, so it needs at least \(2\) vertices; \(\{a,b\}\) has exactly \(2\) and does separate them.
Worked Example: Several Separators, but Not All Are Minimum
Let \(G=(V,E)\), where \(V=\{s,a,b,c,t\}\) and \(E=\{sa,at,sb,bc,ct\}\). Determine the \(s\)-\(t\) paths and compare some separators.
The only \(s\)-\(t\) paths are \(P_1=(s,a,t)\) and \(P_2=(s,b,c,t)\). Indeed, from \(s\) the first step must go to \(a\) or \(b\). From \(a\) the only next step toward \(t\) is \(t\); from \(b\) it is \(c\), and from \(c\) it is \(t\). The internal vertex sets are \(\{a\}\) and \(\{b,c\}\), so these two paths are internally vertex-disjoint.
To block \(P_1\), a separator must contain \(a\). To block \(P_2\), it must contain \(b\) or \(c\). Thus \(\{a,b\}\) and \(\{a,c\}\) are separators. Each has size \(2\), and neither single vertex can block both paths, so both are minimum separators. In particular, deleting \(a\) and \(b\) blocks the first path at \(a\) and the second at \(b\).
The set \(\{a,b,c\}\) is also a separator, but it is not inclusion-minimal, because its proper subset \(\{a,b\}\) is already a separator. It is therefore not minimum either: it has size \(3\), whereas \(\{a,b\}\) has size \(2\). This distinction matters when a question asks for “a minimal separator” rather than “a minimum separator.”
Check: each of the two internally disjoint paths needs a distinct vertex in any separator. Hence every separator has size at least \(2\). The sets \(\{a,b\}\) and \(\{a,c\}\) have size \(2\), and the path-by-path test confirms each one blocks both routes.
Worked Example: A Pair Already Disconnected
Let \(G=(V,E)\), where \(V=\{s,a,t,u,v\}\) and \(E=\{sa,uv\}\). For the specified pair \(s,t\), determine whether a separator is needed.
The only edge incident with \(s\) is \(sa\), and \(t\) has no incident edges. Consequently, there is no \(s\)-\(t\) path. The empty set is a separator: deleting no vertices already leaves \(s\) and \(t\) disconnected. There are \(0\) \(s\)-\(t\) paths, so there is no nonempty family of internally disjoint \(s\)-\(t\) paths.
Check: The edge \(uv\) lies in a separate component and cannot connect \(s\) to \(t\). The empty set has size \(0\), and no set can have smaller size, so it is a minimum separator under the stated convention.
Why Adjacent Terminals Need Care
The requirement \(S\subseteq V(G)\setminus\{s,t\}\) has a consequence for adjacent terminals. If \(st\in E(G)\), then the one-edge path \((s,t)\) remains after deleting any permitted set \(S\), because neither endpoint can be removed and the edge is not incident with a deleted vertex. Thus no such \(S\) separates adjacent \(s,t\). This is not a failure of the path-separator definition; it is a reason that vertex-separator statements and Menger’s theorem require careful endpoint conventions.
Worked Example: The Direct Edge Cannot Be Blocked Internally
Let \(G=(V,E)\), where \(V=\{s,t,a\}\) and \(E=\{st,sa,at\}\). The terminals \(s,t\) are adjacent, and there is also a path through \(a\).
The paths \((s,t)\) and \((s,a,t)\) are internally vertex-disjoint: the first has no internal vertices, and the second has internal vertex set \(\{a\}\). The only allowed nonempty candidate separator is \(\{a\}\), but deleting \(a\) leaves the edge \(st\), so \(\{a\}\) is not a separator. The empty set also leaves both paths. Hence there is no separator that excludes the terminals.
Check: The direct path uses the edge \(st\) and no internal vertex. Every permitted vertex deletion leaves that path intact, so no set of internal vertices can meet every \(s\)-\(t\) path.
Common Pitfalls
Counting paths is not the same as counting edges. Internally vertex-disjoint paths may share endpoints, but they cannot share any internal vertex. In the second example, the paths \((s,a,t)\) and \((s,b,c,t)\) qualify because \(\{a\}\cap\{b,c\}=\varnothing\). Two paths that both pass through \(a\) would not qualify, even if they used different edges near \(a\).
A separator must block every path. In the first example, \(\{a\}\) blocks \(P_1\), but it does not separate \(s\) from \(t\), because \(P_2\) remains. A set that interrupts one route is not necessarily a separator.
Do not use the nonadjacent-pair conclusion for an adjacent pair. A common incorrect calculation in the last example is: “There are two internally disjoint paths, so deleting one internal vertex, namely \(a\), separates \(s\) and \(t\).” The correction is to check all paths after deletion: \(G-\{a\}\) still contains \((s,t)\). The direct path has no internal vertex, so no separator excluding \(s,t\) can hit it.
For a nonadjacent pair, the counting proposition gives a reliable check: if you exhibit \(k\) internally vertex-disjoint paths, a separator must have at least \(k\) vertices. To establish that a proposed set is a separator, however, you must also show that it blocks every path, not just the paths you happened to exhibit.
Check Your Understanding
For each question, keep the specified pair and the rule excluding its endpoints from a separator in view.
- In the graph with \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt\}\), give two internally vertex-disjoint \(s\)-\(t\) paths and identify a minimum separator.
- In the graph with \(V=\{s,a,b,c,t\}\) and \(E=\{sa,at,sb,bc,ct\}\), explain why \(\{a,c\}\) is a separator and why no single vertex is a separator.
- State the difference between an inclusion-minimal separator and a minimum separator.
- Prove that if there are three pairwise internally vertex-disjoint \(s\)-\(t\) paths and \(s,t\) are nonadjacent, every \(s\)-\(t\) separator has at least three vertices.
- If \(st\) is an edge, explain why no separator contained in \(V(G)\setminus\{s,t\}\) can separate \(s\) from \(t\).