The real world

From a graph invariant to an operational diagnostic

Published: 16 Aug 2026

The bidirectional mandatory core is a mathematical invariant, but its value is practical. It distinguishes what one optimisation run happens to select from what every optimal separator is forced to select.

That distinction can change how a network is monitored, redesigned or explained. It can also be misused. A graph result is only as sound as the model that produced it, and mandatory membership answers a narrower question than “What is the most important component?”

The diagnostic output #

For terminal regions A and B, a useful analysis reports more than one set:

Output	Question answered
`κ(A, B)`	How many internal vertices are needed to stop all movement from `A` to `B`?
`M(A, B)`	Which vertices occur in every smallest complete forward separation?
`κ(B, A)`	How many internal vertices are needed in the reverse direction?
`M(B, A)`	Which vertices occur in every smallest complete reverse separation?
`M↔(A, B)`	Which vertices are mandatory across all minimum cuts in both directions?
`I(A, B)`	Which removable internal vertices does every forward route traverse?

The connectivity values describe the size of an optimal disruption. The mandatory cores describe agreement among all optimal disruptions. Path intersection answers the separate question of compulsory passage.

A good report keeps all three ideas visible. If M(A,B) = {h} and κ(A,B) = 1, then h is a one-vertex separator from A to B. If M(A,B) = {h} and κ(A,B) = 4, removing h leaves forward connectivity exactly three, so forward routes remain. For a bidirectional core, report κ(A,B) and κ(B,A) separately: a vertex can be a one-vertex separator in one direction but not the other. Assuming a forward path exists, M(A,B) = ∅ with κ(A,B) = 1 means that at least two distinct one-vertex cuts can each stop the forward movement.

Building the graph #

Real systems do not arrive as vertices and edges. They must be translated.

State the movement #

Decide what an edge means. Depending on the domain, it might mean:

a person is permitted to move between locations;
a packet can be forwarded;
a request can invoke a service;
an attacker can move between states;
a case can pass between organisational roles;
material, energy or information can move between biological components.

Mixing meanings produces a graph that no theorem can rescue.

Choose terminal regions #

The core is relative to A and B. In a security model, A might be exposed entry states and B a protected data store. In transport, they might be two districts. In software, they might be client entry points and a business capability.

A vertex can be mandatory for one terminal pair and irrelevant for another. There is no context-free mandatory core of an entire graph.

Choose the resolution #

A service may be represented as one vertex or unfolded into load balancers, processes, queues and databases. A railway station may be one vertex or a collection of platforms, passages and control systems. The heart may be one organ-level vertex or several chamber-level vertices.^[5]

Contraction can manufacture a singleton by hiding internal alternatives. Refinement can replace that singleton with a mandatory subsystem—or make it disappear.

Define removal #

Removing a vertex must have a domain meaning. It may represent failure, closure, quarantine, revocation, maintenance or deliberate intervention. These are not interchangeable.

The unweighted theory assigns every removal a cost of one. If closing a minor station and disabling a national identity provider have radically different costs, minimum cardinality is not the right objective. Use a weighted extension or report the limitation.

Protect the rest #

Terminal regions are normally protected. Other vertices may need protection too: external actors, abstract environment nodes, stage interfaces or components outside the analyst's control. Failing to mark them can create mathematically valid but operationally meaningless cuts.

Software and service architecture #

Represent services, queues, gateways, databases and external dependencies as vertices. A directed edge means that one component can call or depend on another. Choose client-facing entry points as A and a business capability as B.

The forward core then answers:

Which components occur in every smallest complete set of service removals that disconnects clients from this capability?

This is different from asking which services receive the most calls. A low-volume coordination service can be structurally mandatory, while a high-volume cache can have several substitutes.

The reverse model may represent acknowledgements, callbacks, replication or result delivery. If forward requests and reverse results follow different dependency chains, comparing M(A, B) with M(B, A) makes that asymmetry explicit.

Distributed-system practice already treats accidental concentration with care. Google’s Site Reliability Engineering material, for example, notes that implementing coordination through a single process creates a single point of failure and discusses replicated consensus services as an alternative.^[3] Mandatory-core analysis generalises the diagnostic: a component can be forced across every minimum multi-component disruption even when it is not a one-component failure point.

A design review pattern #

For each critical capability:

Compute the forward and reverse connectivities.
Record every mandatory-core vertex.
Remove each core vertex in a staging model and recompute connectivity.
Ask whether an added independent path increases κ or merely changes which cuts are optimal.
Repeat after expanding coarse service vertices into their internal architecture.

Under the parallel-composition theorem, components add their connectivities and preserve their mandatory contributions when they share only protected terminals, have disjoint removable interiors and have no cross-interior edges. Under the protected series-composition theorem, pairwise-disjoint stages with protected interfaces and complete compatible bridges are controlled by the unique strict bottleneck stage; tied bottlenecks remove global agreement.

Cybersecurity and access control #

A security graph can represent hosts, identities, trust zones, credentials or attacker states. Directed edges represent permitted communication or feasible state transitions. Possible entry states form A; protected resources form B.

The forward mandatory core identifies controls or states contained in every minimum-cardinality isolation strategy. The reverse core can model exfiltration, command channels or another explicitly defined reverse movement.

This aligns naturally with segmentation analysis. NIST's zero-trust architecture moves attention away from implicit trust based on network location and toward explicit protection of resources, users and sessions.^[1] CISA describes microsegmentation as a way to reduce attack surface, limit lateral movement and improve visibility across smaller groups of resources.^[2]

The graph invariant does not certify a zero-trust architecture by itself. It can support narrower questions:

Which enforcement locations are shared by every minimum isolation plan?
Do ingress and egress have the same mandatory controls?
Does a proposed connection remove one optimal cut while leaving another equally small cut?
If segmentation only removes permitted edges, does it decrease connectivity or leave it unchanged, and how does it change the core? If the redesign also adds controls, vertices or paths, analyse that larger graph separately.

The gateway trap #

Suppose a designer wants every request to pass through an authentication gateway. Mandatory membership is not enough.

                   ┌──▶ gateway h ─────────▶─┐
entry states ──────┤                         ├──▶ protected resource
                   └──▶ control x ─▶ y ─────▶┘

The minimum cuts are {h, x} and {h, y}. The gateway h belongs to every minimum cut, but the lower route bypasses it completely.

To prove universal enforcement, compute path intersection or dominators and verify that every allowed route traverses the policy enforcement point. Use the mandatory core for a different claim: h is unavoidable across every smallest complete isolation strategy.

Security reviews often need both results:

path intersection for enforcement coverage;
mandatory-cut intersection for optimal isolation structure.

Confusing them can turn a correct theorem into a dangerous assurance.

Transport networks #

Vertices can represent stations, junctions, terminals or regions; edges represent permitted movement. Direction matters because one-way streets, turn restrictions, express services and time-dependent schedules make the reverse journey structurally different.

For an origin region A and destination region B, the mandatory core identifies locations shared by every smallest complete vertex-disruption plan. It does not identify the busiest station, the location with the greatest passenger count or the asset whose closure causes the largest economic loss. Those may all be worthwhile analyses, but they optimise different quantities.

Transportation agencies already distinguish critical-asset identification from countermeasure selection and cost. The US Federal Highway Administration describes vulnerability assessment as a process that considers assets such as bridges, tunnels, roadways and operations facilities, then develops and costs possible countermeasures.^[4] A mandatory-core calculation can contribute a precise structural layer to such a broader assessment; it cannot replace demand, safety, cost or recovery modelling.

A responsible transport model should test several variants:

peak and off-peak edge sets;
normal operation and planned closures;
passenger movement and vehicle movement;
station-level and platform-level resolution;
directed and deliberately symmetrised graphs.

If a singleton survives all reasonable variants, it is more robust than a singleton appearing only in one convenient abstraction.

Organisational workflows #

Represent roles, queues, review stages or states as vertices. An edge means that a case can legally move from one state to another. The terminal regions might be initial requests and completed outcomes.

The forward mandatory core can reveal a role or stage present in every smallest complete process interruption. The reverse direction might represent appeals, rollbacks, refunds or incident escalation—but only if those movements genuinely belong in the same model.

This analysis can support:

continuity planning;
delegation design;
separation-of-duties reviews;
identification of approval bottlenecks;
comparison of formal and observed workflows.

Human organisations require special caution. Informal workarounds, discretionary decisions and emergency procedures are edges whether or not the official process diagram shows them. A core computed from policy documentation may describe the policy, not actual practice.

The result should therefore be presented as conditional:

Under the recorded workflow and the chosen meaning of interruption, every minimum separation contains this role.

That is strong enough to be useful and modest enough to be true.

Biological and physiological models #

Biological networks can represent organs, anatomical structures, reactions, regulatory states or information flow. The heart example from before illustrates both the appeal and the danger.

At organ scale, one heart vertex lies between systemic and pulmonary circulation in both directions. At chamber scale, the vertex separates into right- and left-side structures. At finer scales, valves, vessels, pressure gradients and timing enter the model.

A mandatory biological vertex is therefore mandatory in a chosen abstraction. It is not automatically:

the sole causal driver of the process;
the only clinically important component;
independently removable in a real organism;
evidence that all physical material follows the graph's idealised routes.

The most informative use may be model comparison. Compute the core at several plausible scales. Persistence supports robustness; change reveals which abstractions created the conclusion.

Optimiser's answer #

A minimum-cut algorithm normally returns one optimum. If several optima exist, implementation details decide which one appears first.

Suppose the returned cut is {h, x}. Without additional analysis, a report might imply that x is privileged. But if the full family is

{{h, x}, {h, y}, {h, z}}, then only h survives every optimum.

An explainable result separates three layers:

Layer	Example statement
One solution	“The solver returned `{h, x}`.”
All-solutions agreement	“Every optimum contains `h`.”
Model scope	“This holds for the recorded directed graph, protected terminals and unit removal costs.”

The mandatory core supplies the second layer. The modelling record supplies the third.

Reading the result operationally #

Different combinations of connectivity and core size suggest different next questions.

Observation	Interpretation	Next question
Small `κ`, empty `M`	Few removals stop movement, but optimal choices are substitutable	Are the alternatives exposed to a common failure mode?
Small `κ`, singleton `M`	Every smallest disruption includes one component	Can its role be diversified or removed from the bottleneck?
Large `κ`, small `M`	Many independent routes exist, yet optima still agree on a few vertices	Why do all optimal cuts spend part of their budget there?
`M(A,B) ≠ M(B,A)`	The two directions have different structural constraints	Are the direction-specific models accurate?
Non-singleton `M↔`	A subsystem, not one vertex, is structurally identified	Should it be monitored and redesigned as a unit?
Core changes under refinement	The conclusion depends on modelling scale	Which resolution matches the operational decision?

Monitoring a mandatory vertex is sensible, but not sufficient. The minimum cuts containing it also matter. If every optimum contains h plus one of twenty interchangeable branch vertices, protecting only h leaves the rest of the separator structure unexplored.

Stress-test the model #

Before acting on a core, vary the assumptions.

Change terminal regions #

Compute cores for several business-relevant pairs rather than one convenient pair. A service mandatory for checkout may not be mandatory for browsing.

Change graph resolution #

Expand each core vertex into its internal subgraph. Recompute. A coarse singleton may become an internal pair, an empty core or another singleton.

Change direction #

Never infer the reverse result from the forward one. Compute both.

Change cost #

Unit cardinality asks for the fewest vertices. A weighted model asks for the least total cost. Intersecting all minimum-cost cuts gives a weighted mandatory core, which may differ completely from the unweighted one.

Change certainty #

Edges inferred from incomplete inventories should be marked. Recompute under plausible additions and removals. The edge-addition theorem says the core can only grow while κ stays fixed, but κ itself may change.

Look beyond exact optima #

Exact intersections can be brittle when several separator costs are close. A near-optimal analysis asks which vertices occur in every cut within a chosen tolerance of the optimum. The tolerance is a domain decision, not a graph-theoretic constant.

A practical analysis record #

For reproducibility, store these items with every result:

The graph version and provenance of every edge.
The meanings of vertices, edges and direction.
Terminal and protected vertex sets.
Removal costs and whether they are uniform.
κ, one example minimum cut and the mandatory core in each direction.
Path-intersection results when compulsory passage matters.
Sensitivity results across alternative scales and edge sets.
The operational claim the analysis is allowed to support.

This record prevents a structural certificate from drifting into a universal claim about importance.

The useful narrowness of the method #

Mandatory-core analysis does not replace centrality, capacity planning, reliability probabilities, simulation, threat modelling or domain expertise. It contributes one unusually clean fact:

These vertices survive disagreement among every optimal separator allowed by this model.

That fact is useful precisely because it is narrow. It can reveal a shared ingredient hidden by solver tie-breaking. It can distinguish directional constraints. It can expose when a supposed central point is replaceable—and when a quiet component is structurally forced.

The practical discipline is to preserve the qualifiers: the chosen graph, terminal regions, direction, resolution, protected vertices and removal costs. When the conclusion survives reasonable changes to those choices, the result becomes more than an artefact of one diagram. It becomes evidence of a persistent structural feature.