Can there be several minimum node cuts?

Yes. The five-cycle has five different minimum cuts of size 2.

Does passing k = 3 ask the supplied function for all three-vertex cuts?

No. Its documented argument represents the graph's known node connectivity.

Is one minimum cut enough to explain every vulnerability?

No. It provides one smallest separating set and can miss alternative equally small sets and larger failure combinations.

AI Glossary / Graphs and symbolic AI / Intermediate

K-node-cutsets

Definition

K-node-cutsets are sets of k vertices whose removal separates a graph. In the supplied NetworkX reference, the term specifically concerns all minimum-size separating sets: k equals the graph's node connectivity, rather than an arbitrary number of vertices chosen for removal.

What it means

Removing a vertex also removes its incident edges. A node cut therefore models the loss of an entity and all its graph connections, rather than the loss of one relationship alone.

For a connected, noncomplete undirected graph, a minimum node cut is a smallest set whose deletion leaves disconnected remaining vertices. Several different sets can achieve the same smallest size. Finding all of them gives more information than reporting only that size or one example.

Minimum and minimal are different. A minimum cut has the smallest cardinality among all cuts. A minimal cut cannot have any member removed while remaining a cut, but another smaller cut may exist elsewhere. The referenced routine enumerates minimum-size cuts, not every inclusion-minimal cut of every size.

How it works

Establish the graph and the intended meaning of node removal. Determine its node connectivity k, then enumerate separating vertex sets of that size. Each candidate must genuinely separate the remaining graph, and a complete enumeration must avoid both omissions and duplicates.

The supplied function uses a flow-based algorithm attributed to Kanevsky. Its optional k argument is the already-known connectivity of the input graph. It is not a request to list every cut of an arbitrary user-selected size; if omitted, the function computes connectivity.

Distinguish a global cut from a cut separating specified endpoints. Also check input assumptions and conventions for complete, already disconnected or very small graphs. These cases should not be interpreted by casually extending the ordinary picture of two surviving disconnected regions.

Three practical examples

A network-analysis exercise lists all smallest combinations of modeled devices whose loss separates the network.
A graph dashboard compares two designs with the same connectivity value but different sets of vulnerable vertices.
A teaching example contrasts one articulation point with a larger separating set that is minimal but not minimum.

Think of it this way

Think of junctions in a network of walking paths. Closing one junction removes every path segment meeting there. A cutset is a collection of closures that separates the remaining accessible areas.

The smallest number of closures is one question; identifying every equally small combination is another. The analogy covers connectivity only, not path capacity, travel time or the probability that closures occur together.

Worked example

From five minimum pairs to one minimum singleton

Start with the undirected five-cycle A - B - C - D - E - A. Removing any one vertex leaves a connected four-vertex path. Therefore no one-vertex cut exists.

Removing two adjacent vertices also leaves a connected three-vertex path. For example, deleting A and B leaves C - D - E. Removing two nonadjacent vertices disconnects the remaining graph. Deleting A and C leaves isolated B and the edge D - E.

There are ten unordered pairs of vertices in total. Five are adjacent pairs and five are nonadjacent pairs. The minimum cutsets are exactly {A, C}, {A, D}, {B, D}, {B, E} and {C, E}. Thus the connectivity is 2, and there are five distinct minimum-size cuts. The count of cuts is not the connectivity value.

Now add a sixth vertex L connected only to A. Removing A leaves L isolated while B - C - D - E remains connected. No other single vertex disconnects this revised graph, so its unique minimum cutset is {A}, and its connectivity is 1.

The pair {B, D} still disconnects the revised graph: C becomes isolated, while A, E and L stay connected. Neither B nor D alone disconnects it. The pair is therefore minimal, but it is no longer minimum because {A} is smaller. A routine enumerating all minimum cuts of the revised graph should not be described as listing every minimal separating set.

Illustrative case study

The fictional Birch Graphs team compares two network diagrams and reports the same headline connectivity for several candidates. A reviewer asks which actual vertex combinations create the weaknesses, rather than accepting the number alone.

Birch adds a minimum-cutset view and tests it on the five-cycle. After attaching the extra leaf, the team checks that the report changes to the singleton {A}. It retains {B, D} in a separate teaching note about minimality, without mixing it into the minimum-cut output.

This fictional exercise distinguishes the two enumeration tasks. It does not assign failure probabilities or operational priorities.

Common misconceptions and mistakes

k is the number of cutsets returned. It is the number of vertices in each minimum cutset.
All minimum cuts means every separating set. Larger cuts are outside that enumeration.
Minimal and minimum are interchangeable. An irreducible cut can still be larger than another cut.
A node cut is an edge cut with different labels. Removing a node eliminates all its incident connections.

Business use

The concept can help teams identify combinations of modeled dependencies that deserve closer examination. Two graphs with the same connectivity value may concentrate their smallest cuts in different places, which changes the questions a reviewer should ask.

Interpret the result alongside the meaning and quality of the graph. A cut separating a rarely used peripheral node may have different consequences from one dividing major services. Minimum cardinality alone does not measure business impact, restoration difficulty or likelihood. Enumerating many cuts also creates an output and review burden, so the decision should determine how much detail is useful.

Check your understanding

Why is {B, D} minimal but not minimum after L is attached to A?

Answer: Removing B or D alone does not separate the graph, so both are necessary within that pair. However, the single vertex A already forms a smaller cut elsewhere.

Related terms

Maximum Flow
Vertex cut
node connectivity
articulation point
minimum cut
minimal separator
edge cut
graph resilience

Learn next

List all ten pairs in the original five-cycle and check the remaining graph after each deletion. Then repeat the single-vertex checks after adding L. Label cardinality, number of returned sets and inclusion-minimality separately.

Sources

NetworkX defines the supplied enumeration and the meaning of its k parameter: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.connectivity.kcutsets.all_node_cuts.html

Its minimum-node-cut documentation distinguishes global and endpoint-specific questions: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.connectivity.cuts.minimum_node_cut.html

The cycle calculations and Birch Graphs case are original illustrations. Kanevsky's original publisher page was unavailable in this check; the implementation description was reviewed through NetworkX.

Previous: k-nearest neighbors regression Next: K-optimal pattern discovery