Does it need a chosen source and sink?

No. It finds a global minimum over nonempty bipartitions.

Can zero-weight edges be used?

Nonnegative weights include zero, subject to the implementation's other input requirements.

What does NetworkX return?

Its documented function returns the minimum cut value and a pair of vertex lists defining a corresponding partition.

AI Glossary / Graphs and symbolic AI / Intermediate

Stoer-Wagner minimum cut

Definition

The Stoer - Wagner minimum-cut algorithm finds a global minimum edge cut in an undirected graph with nonnegative edge weights. A cut divides the vertices into two nonempty groups, and its value is the sum of the weights of edges crossing between them. The algorithm finds a partition with the smallest such total, without requiring a designated source and destination.

What it means

A cut measures how much connection must be removed to separate one group from the other under the graph's weight model. In an unweighted graph, treating every edge as weight one makes the value the number of crossing edges.
This is a global cut problem, different from finding the cheapest cut that specifically separates two chosen vertices. It is also different from deleting vertices or finding a minimum spanning tree. The returned groups need not have similar sizes. A minimum cut can isolate a single vertex if that produces the smallest crossing weight.

How it works

The algorithm performs successive phases. In each phase, it starts from a vertex and repeatedly adds the outside vertex most strongly connected to the growing set, measured by total edge weight into that set. The final vertex added defines a candidate phase cut.
The last two vertices in the phase are then contracted into a combined vertex, summing the relevant connection weights. The process repeats on the contracted graph, retaining the smallest phase-cut value and enough information to recover its original partition. The exactness guarantee comes from the algorithm's cut-and-contraction argument, not from assuming that any one locally selected phase must already be globally best.

Three practical examples

A network-analysis exercise can locate a partition separated by a small total connection weight.
A graph-based system model can identify a weak connection between groups for further engineering review.
A teaching application can compare a global minimum cut with a cut constrained to separate a particular pair of vertices.

Think of it this way

Think of dividing connected workstations into two groups while counting the total capacity of the links crossing the division. The algorithm seeks the smallest crossing total. The analogy is limited because mathematical edge weights must represent the intended quantity; a low-weight partition is not automatically the most important operational failure scenario.

Worked example

Consider an original undirected graph with vertices A, B, C, and D. Its edges have weights AB = 4, AC = 1, BC = 2, BD = 1, and CD = 5. There is no AD edge.
The partition {A,B} versus {C,D} crosses AC, BC, and BD, giving value 1 + 2 + 1 = 4. Internal edges AB and CD do not contribute to this cut.
Check all distinct nontrivial partitions, counting a partition and its reversed labeling only once. Isolating A gives 5; isolating B gives 7; isolating C gives 8; and isolating D gives 6. The other two balanced partitions, {A,C} versus {B,D} and {A,D} versus {B,C}, each give 11. These seven possibilities establish that four is the global minimum for this small graph.
Now follow a possible Stoer - Wagner phase starting at A. B is added first because its connection weight to A is four, compared with one for C and zero for D. With {A,B} selected, C has total connection weight three, while D has one, so C is added next. D is last, and the phase cut isolates D with value six.
Contract the last pair C and D into a combined vertex CD. Its connection to A is one, and its connection to B is 2 + 1 = 3. The AB edge remains four. In a new phase starting at A, B is selected before CD. The last vertex CD defines a cut of value 1 + 3 = 4, corresponding to the original partition {C,D} versus {A,B}.
The remaining two-vertex phase has cut value five. The minimum across the phase values six, four, and five is four. The first phase alone was not optimal; retaining and comparing phase cuts was essential. The explicit enumeration above independently verifies the result without relying on the phase trace.

Illustrative case study

In a fictional network-modeling project, a team assigns link-capacity weights to an undirected graph and computes its global minimum cut. It discovers that the returned partition separates a small peripheral group.
The team checks whether that group is operationally important and whether the model represents directionality or shared infrastructure accurately. It treats the cut as one structural finding rather than a complete reliability assessment. This fictional case does not claim that minimum-cut value equals a real failure probability.

Common misconceptions and mistakes

A minimum cut is not necessarily a balanced partition, a community division, or a minimum set of failed vertices. Edge weights determine what the cut value means.
Do not apply the stated algorithm directly to negative-weight or directed inputs. Do not confuse global minimum cut with a source - sink minimum cut. Finally, one minimum partition need not be unique; different valid outputs can have the same optimal value. Comparing only the exact vertex grouping can therefore misjudge a correct implementation.

Business use

The method can support structural analysis when an undirected weighted graph faithfully represents the system. It provides an exact answer to a clear mathematical question and an interpretable partition for review.
Validate edge meanings and units before interpreting the result. Check whether the desired question concerns capacity, connection count, a specific pair of endpoints, or balanced groups. These are different objectives. For implementation review, verify that the returned partition covers every vertex exactly once and that the crossing-edge sum matches the reported cut value.

Check your understanding

Why is AB's weight four excluded from the cut {A,B} versus {C,D}?

Answer: Both endpoints of AB lie on the same side. Only edges connecting opposite sides contribute.

Related terms

Weighted graph
Maximum Flow
Partition
Global minimum cut
Edge cut
Graph contraction
Source–sink cut
Network connectivity

Learn next

Next, increase AC's weight from one to three. Recompute all seven cut values rather than updating only the previous winner. The old partition now has value six, and isolating D also has value six. Explain why equal optimum values can correspond to different partitions.

Partition

Sources

Primary sources: NetworkX Stoer–Wagner reference: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.connectivity.stoerwagner.stoer_wagner.html ; implementation source: https://networkx.org/documentation/stable/_modules/networkx/algorithms/connectivity/stoerwagner.html . The four-vertex graph and complete cut enumeration are original.

Previous: Stock series Next: Stop (consonant)