Endpoint Conventions in Vertex Menger

Why Endpoint Conventions Matter

Vertex Menger’s theorem relates two ways of measuring how well-connected a pair of vertices is: the number of internally vertex-disjoint paths between them and the size of a vertex set that separates them. The endpoints require special care. A separator is not allowed to contain either endpoint, and the theorem’s standard form assumes the endpoints are nonadjacent. These are not cosmetic restrictions: if either convention is ignored, the separator side of the comparison can become meaningless.

All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. An \(s\)-\(t\) path has first vertex \(s\) and last vertex \(t\); its internal vertices are all the vertices on the path other than \(s\) and \(t\). A family of \(s\)-\(t\) paths is internally vertex-disjoint if distinct paths in the family have no common internal vertex. They may share the endpoints. Paths in a family are distinct.

Here \(G-S\) means the graph obtained by deleting the vertices in \(S\) and all edges incident with them. The definition requires that both terminals remain in the graph: saying they are in different components is only meaningful when neither has been deleted. When \(s,t\) are nonadjacent, the set \(V(G)\setminus\{s,t\}\) is a separator, since every \(s\)-\(t\) path, if one exists, must have an internal vertex. Thus, for nonadjacent terminals, a minimum separator exists even if no path exists; in that disconnected case its size is zero.

The Standard Nonadjacent Form

The theorem is about paths whose only permitted common vertices are their endpoints, compared with sets that disconnect those endpoints while leaving them present. The nonadjacency condition ensures that deleting internal vertices can actually destroy every path. It also ensures that every path under consideration has at least one internal vertex.

Proof. If \(s\) is allowed in a separator, take \(S=\{s\}\). Deleting \(S\) deletes \(s\) itself, so the pair of terminals is no longer present. A convention that treats this as “separating” the pair gives a separator of size one in every graph. The same issue arises with \(S=\{t\}\). Such a set does not measure how many internal vertices must be removed to disconnect two surviving terminals, so the vertex-separator definition excludes both endpoints. \(\square\)

This exclusion also explains why a separator is not simply any vertex set that meets every \(s\)-\(t\) path. Under the convention above, the terminals are never candidates for deletion. For nonadjacent \(s,t\), a set of internal vertices that meets every \(s\)-\(t\) path disconnects them, and conversely a separator meets every such path: a path avoiding the separator would remain in \(G-S\) and connect the terminals.

What Changes When the Terminals Are Adjacent?

Suppose \(st\in E(G)\). The one-edge path \(s,t\) has no internal vertices. Deleting vertices other than \(s,t\) cannot remove that edge, so it cannot disconnect \(s\) from \(t\). In particular, there is no \(s\)-\(t\) vertex separator in \(G\) under the stated definition. The minimum separator size in the nonadjacent form of the theorem is therefore not defined for this pair.

Proof. Let \(S\subseteq V(G)\setminus\{s,t\}\) be any set. Since neither endpoint is deleted, and the edge \(st\) has no other vertices, the edge remains in \(G-S\). Thus \(s\) and \(t\) are still adjacent in \(G-S\), so they lie in the same component. No such \(S\) separates them. \(\square\)

The usual way to handle an adjacent pair is to remove the edge \(st\) first. Write \(G'=G-st\). In \(G'\), the terminals are nonadjacent, so the nonadjacent form of vertex Menger applies. Its separators are subsets of \(V(G)\setminus\{s,t\}\); they separate \(s,t\) in \(G'\), not in the original graph \(G\). The direct edge is then accounted for separately as one path.

Proof. Let \(q\) be the maximum number of internally vertex-disjoint \(s\)-\(t\) paths in \(G-st\). Take a family of \(q\) such paths and add the one-edge path \(s,t\). The added path has no internal vertices, so it is internally disjoint from every path in the family. This gives \(q+1\) internally disjoint paths in \(G\).

For the reverse inequality, consider any internally vertex-disjoint path family in \(G\). It can contain the one-edge path at most once. Every other \(s\)-\(t\) path avoids the edge \(st\): a simple \(s\)-\(t\) path containing that edge must be the one-edge path, since visiting the edge as part of a longer simple path would repeat an endpoint. Thus, after discarding the direct path if it is present, the remaining family is a family in \(G-st\) and has size at most \(q\). The original family therefore has size at most \(q+1\). Combining the two inequalities proves the proposition. \(\square\)

Since \(s,t\) are nonadjacent in \(G-st\), vertex Menger in that graph identifies \(q\) with the minimum size of a separator there. Consequently, the adjacent-pair comparison uses one additional path for the edge \(st\), while the separator is measured after that edge has been removed. It would be incorrect to search for a separator in the original graph.

Worked Examples

Common Mistake and a Practical Checklist

Wrong calculation: For the graph with \(V=\{s,t\}\) and \(E=\{st\}\), one might claim that \(\{s\}\) is a separator of size \(1\), because deleting \(s\) leaves no \(s\)-\(t\) path. This does not satisfy the definition: after deleting \(s\), the terminal \(s\) is absent, so the pair has not been separated while both endpoints remain.

Correction: No separator exists in the original graph under the endpoint-excluding convention, because the edge \(st\) survives every permitted deletion. Delete \(st\) first; then the empty set separates the terminals in \(G-st\), and the direct edge contributes one path when the original graph is considered again.

Before applying vertex Menger to a pair \(s,t\), check the following:

• The terminals are distinct.
• A separator is a subset of \(V(G)\setminus\{s,t\}\), so both terminals remain after deletion.
• If \(s\) and \(t\) are nonadjacent, use the standard equality between the maximum internally disjoint path count and the minimum separator size.
• If \(s\) and \(t\) are adjacent, do not search for a separator in \(G\). Remove \(st\), apply the nonadjacent convention in \(G-st\), and account for the direct path separately.
• If the terminals are disconnected in the graph being considered, the empty set is a separator and the path count is zero.