The mathematics

Minimum vertex cuts, composition and an exact max-flow algorithm

Published: 16 Aug 2026

Exploring the idea further leads us to an interesting observation:

When several equally economical ways exist to separate two regions of a directed network, some vertices are forced to occur in all of them.

Setting and conventions #

Let G = (V, E) be a finite directed graph. Let A and B be nonempty, disjoint subsets of V. They are the terminal regions.

An A-to-B path begins at a vertex in A and ends at a vertex in B. Vertices outside A ∪ B that occur internally may be removed; every terminal vertex in A ∪ B is protected, even if it occurs internally on a path.

An A-to-B vertex cut is a set X ⊆ V − (A ∪ B) such that G − X contains no directed path from A to B.

Define the directed internal vertex connectivity

κG(A, B) = min {|X| : X is an A-to-B vertex cut in G}.

When the graph is clear, we write κ(A, B). Let C(A, B) be the family of all cuts whose size is exactly κ(A, B).

Two boundary conventions matter:

If no A-to-B path exists, ∅ is the unique minimum cut, κ(A, B) = 0, and the mandatory core is empty.
If an A-to-B path contains no removable internal vertex—for example, a direct protected edge—no finite internal vertex cut exists.

Unless stated otherwise, the results below concern a direction in which at least one path and a finite internal cut exist.

Minimum is not minimal #

A cut is minimal when none of its own vertices can be removed while leaving it a cut. It is minimum when no smaller cut exists anywhere in the graph.

Every minimum cut is minimal. A minimal cut can nevertheless be much larger than the optimum. The mandatory core uses minimum cuts because arbitrary excess vertices would otherwise contaminate the intersection.

Mandatory cores #

The forward mandatory core is

M(A, B) = ⋂ {X : X ∈ C(A, B)}.

It contains exactly the internal vertices present in every minimum A-to-B cut.

The reverse core is computed independently as M(B, A). The bidirectional mandatory core is

M↔(A, B) = M(A, B) ∩ M(B, A).

Although the two directional problems can be different, the bidirectional result is symmetric:

M↔(A, B) = M↔(B, A).

The definition immediately gives three outcomes:

M↔(A, B) = ∅: no vertex is forced across all minimum cuts in both directions;
M↔(A, B) = {h}: one vertex is structurally identifiable;
|M↔(A, B)| > 1: the graph identifies a mandatory subsystem.

Canonicality #

Once G, A and B are fixed, the core is fixed. An isomorphism preserving directed edges and terminal regions maps paths to paths, minimum cuts to minimum cuts and their intersection to the corresponding intersection.

Consequently, if M↔(A, B) = {h}, every automorphism preserving the terminal regions must fix h. The vertex is selected by the graph rather than a tie-breaking rule.

Paths and separators #

Let I(A, B) be the set of removable internal vertices that occur on every directed path from A to B.

Assuming at least one path exists,

κ(A, B) = 1 if and only if I(A, B) ≠ ∅.

Indeed, a common internal vertex is a one-vertex cut. Conversely, if {v} is a cut, every path must contain v.

When κ(A, B) = 1, the complete family of minimum cuts is

C(A, B) = {{v} : v ∈ I(A, B)}.

Therefore:

if I(A, B) = {h}, then M(A, B) = {h};
if I(A, B) contains two or more vertices, then M(A, B) = ∅.

The directed chain

A → v → w → B

has I(A, B) = {v, w}, but its minimum cuts are {v} and {w}. Their intersection is empty.

The reverse phenomenon is also possible:

         ┌──▶ h ──────────▶─┐
A ───────┤                  ├────▶ B
         └──▶ x ──▶ y ─────▶┘

Here κ(A, B) = 2, the minimum cuts are {h, x} and {h, y}, and M(A, B) = {h} even though the lower path avoids h.

Dominator theory studies vertices lying on every path from a distinguished source.^[3] Mandatory-core membership studies vertices lying in every minimum separator. Neither notion contains the other in general.

Basic properties #

Core size and uniqueness #

|M(A, B)| ≤ κ(A, B),

with equality if and only if the minimum A-to-B cut is unique.

Proof. The core is contained in every minimum cut, and each minimum cut has κ(A, B) vertices. This proves the inequality. If equality holds, the core already fills every minimum cut, so every minimum cut equals the core. Conversely, the intersection of a one-member family is that member. ∎

Connectivity drop #

If v ∈ M(A, B), then κ(A, B; G − v) = κ(A, B; G) − 1

Proof. Write κ = κ(A, B; G). Every minimum cut X contains v, so X − {v} cuts G − v and has size κ − 1.

Conversely, if Y cuts G − v, then Y ∪ {v} cuts G. Hence |Y| + 1 ≥ κ, so |Y| ≥ κ − 1. The upper and lower bounds agree.

For v ∈ M↔(A, B), the one-unit drop occurs independently in both directions.

The converse is false in general. A vertex can lower connectivity by one while alternative minimum cuts avoid it. If the minimum cut is unique, however, the converse does hold.

Edge-addition monotonicity #

Let G′ be obtained from G by adding directed edges. If

κG′(A, B) = κG(A, B) then MG(A, B) ⊆ MG′(A, B)

Proof. Every cut of G′ is also a cut of G, because it blocks a superset of the original paths. Equality of the optimum values makes every minimum cut of G′ a minimum cut of G. Thus CG′(A, B) ⊆ CG(A, B). Intersecting the smaller family can only preserve or enlarge the intersection.

The same conclusion holds bidirectionally when both connectivity values remain fixed.

Menger duality #

The directed vertex form of Menger's theorem connects cuts with independent paths. Under the internal-separator convention,

The minimum number of removable internal vertices needed to block every A-to-B path equals the maximum number of A-to-B paths that can coexist without sharing removable internal vertices.

For the two-branch graph above, the paths A → h → B and A → x → y → B are internally disjoint. Every cut must hit each path, so at least two vertices are necessary. The cuts {h, x} and {h, y} show that two are sufficient.

Maximum path families #

If v ∈ M(A, B), every maximum family of κ(A, B) internally vertex-disjoint A-to-B paths contains v on exactly one path.

Proof. Internal disjointness lets v occur on at most one path. Suppose a maximum family avoids it. Choose any minimum cut X. The κ(A, B) vertices of X must hit the same number of disjoint paths. Because v ∈ X hits none of them, only κ(A, B) − 1 vertices remain to hit κ(A, B) disjoint paths, which is impossible.

The converse again fails. A vertex can appear in every maximum path family without belonging to every minimum cut.

Three explicit outcomes #

Empty bidirectional core #

Take separate forward and reverse branches:

A → x₁ → B       B → y₁ → A
A → x₂ → B       B → y₂ → A

The unique forward minimum cut is {x₁, x₂} and the unique reverse minimum cut is {y₁, y₂}. Their intersection is empty.

Singleton bidirectional core #

Make the two-branch graph containing h, x and y bidirectional by reversing every displayed edge as well. In either direction, the minimum cuts are {h, x} and {h, y}. Therefore

M↔(A, B) = {h}.

Non-singleton bidirectional core #

Take two parallel bidirectional branches:

A ↔ p ↔ B
A ↔ q ↔ B

Both branches must be cut in either direction. The unique minimum cut is {p, q}, so

M↔(A, B) = {p, q}.

Parallel composition #

Suppose G₁ and G₂ share only the protected terminal vertices A ∪ B. Their removable interiors are disjoint, and there are no edges directly joining one interior to the other. Let G = G₁ ∪ G₂. Assume a finite internal cut exists in each component.

Parallel-composition theorem #

κG(A, B) = κG₁(A, B) + κG₂(A, B)

and

MG(A, B) = MG₁(A, B) ∪ MG₂(A, B).

Proof. A global cut must block the paths in each component. Because their removable interiors are disjoint, its two pieces have total size at least the sum of the component connectivities.

Conversely, the union of one minimum cut from each component blocks the entire graph and has exactly that size. Every global minimum cut therefore has the form X₁ ∪ X₂, where each Xᵢ is a component minimum cut. A vertex from Gᵢ appears in every union exactly when it appears in every choice of Xᵢ.

Applying the theorem in reverse and using disjoint interiors gives

M↔G(A, B) = M↔G₁(A, B) ∪ M↔G₂(A, B).

Parallel components preserve and combine their mandatory contributions.

Protected series composition #

Series composition needs stronger assumptions. Without them, an intermediate interface vertex may become an unintended one-vertex cut, or surviving paths in adjacent stages may fail to connect.

Let G₁, …, Gm be stages with pairwise disjoint vertex sets. Stage i has protected entry vertices Aᵢ and protected exit vertices Bᵢ. Add every directed bridge from Bᵢ to Aᵢ₊₁. All entry and exit vertices remain protected, including the intermediate interfaces.

Assume each stage has an entry-to-exit path and a finite positive internal cut. Define

kᵢ = κGᵢ(Aᵢ, Bᵢ) and k* = minᵢ kᵢ.

Protected series-composition theorem #

The connectivity of the full chain from A₁ to Bm is k*.

If a unique stage j has kⱼ = k*, every global minimum cut lies in Gⱼ, and

MG(A₁, Bm) = MGⱼ(Aⱼ, Bⱼ).

If two or more stages attain k*, then MG(A₁, Bm) = ∅.

Proof. Suppose a global cut fails to separate every stage. Choose a surviving entry-to-exit path in each stage. Complete bridges allow the chosen paths to be concatenated, contradicting global separation. Every global cut must therefore cut at least one stage and has size at least k*.

A minimum cut inside any stage attaining k* blocks the chain, proving equality. With one strict bottleneck, a global minimum cut has no capacity left for vertices outside that stage. With a tie, minimum cuts can be chosen in two disjoint stages, so their global intersection is empty.

For a two-way chain, add every reverse bridge from Aᵢ₊₁ to Bᵢ. Define the directional stage connectivities

kᵢ+ = κGᵢ(Aᵢ, Bᵢ) and kᵢ− = κGᵢ(Bᵢ, Aᵢ).

The forward core is controlled by the unique stage minimizing kᵢ+; a tie makes it empty. The reverse core is controlled by the unique stage minimizing kᵢ−; a tie makes it empty. Consequently, the global bidirectional core survives only when the same stage is the unique strict bottleneck in both directions. It then equals that stage's bidirectional core.

Computing the core #

The definition appears to require listing every minimum cut, a family that may be very large. The lattice structure of minimum cuts makes enumeration unnecessary.^[1]^[2]

Node splitting #

Let n be the number of removable vertices and choose L = n + 1.

Construct a capacitated network:

Replace each graph vertex v by v-in and v-out.
Add v-in → v-out with capacity 1 when v is removable and capacity L when it is protected.
Replace every graph edge u → w by u-out → w-in with capacity L.
Connect a super-source s to a-in for each a ∈ A, with capacity L.
Connect b-out to a super-sink t for each b ∈ B, with capacity L.

Because a finite internal cut uses at most n removable vertices, its value is below L. A minimum finite cut therefore crosses only capacity-one split edges, and each crossed split edge represents one removed graph vertex. The minimum flow-cut value is exactly κ(A, B).

The residual criterion #

Compute one maximum s-to-t flow and let R be its residual graph. Define:

S−: the residual vertices reachable from s;
S+: the residual vertices that cannot reach t.

The source sides of all minimum cuts form a lattice whose smallest and largest elements are S− and S+:

S− ⊆ S ⊆ S+

for every minimum-cut source side S.

A removable graph vertex v belongs to every minimum A-to-B cut exactly when

v-in ∈ S− and v-out ∉ S+.

The first condition places v-in on the source side of every minimum cut. The second places v-out on the sink side of every minimum cut. Every minimum cut must consequently cross v-in → v-out.

This yields the algorithm:

Build the split network.
Compute one maximum flow.
Search the residual graph forward from s to obtain S−.
Search backward from t to find the vertices that can reach t, then take the complement to obtain S+.
Return the vertices whose split edges satisfy the criterion.

The graph searches are linear after the flow computation. One maximum flow determines M(A, B). A second flow in the reverse direction determines M(B, A), and their intersection gives M↔(A, B).

A simpler membership test is useful for verification: raise the capacity of one vertex's split edge from 1 to L and recompute the optimum. The value increases exactly when every original minimum cut used that vertex. Repeating this for every vertex is slower but conceptually direct.

The result #

The mandatory core is an all-optima invariant. It separates the arbitrary part of one solver result from the part shared by every optimal result.

When M↔(A, B) = {h}, the conclusion is exact:

every minimum A-to-B cut contains h;
every minimum B-to-A cut contains h;
removing h decreases both directional connectivities by one;
every maximum internally disjoint path family in either direction uses h exactly once.

Nothing in the theorem says that h maximizes traffic, betweenness, geographical centrality or any other ranking. The conclusion is narrower: optimal separator structure forces agreement on h.