Is a Gomory-Hu tree a subset of the original graph's edges?

Not necessarily. It is a derived tree over the same vertices.

How is a pair's cut value read?

Find the unique tree path between the pair and take its minimum edge weight.

Does the tree preserve every graph property?

No. It preserves the specified minimum-cut information, not arbitrary distances, routes, or adjacency relationships.

AI Glossary / Graphs and symbolic AI / Intermediate

Gomory-Hu Tree

Definition

A Gomory-Hu tree is a weighted tree that compactly represents the minimum cut values between every pair of vertices in an undirected capacitated graph. For any two vertices, the smallest edge weight on their unique tree path equals their minimum cut value in the original graph. The tree preserves this cut information, not the original network's full structure.

What it means

A cut separates a graph's vertices into two groups. Its capacity is the sum of capacities of original edges crossing between the groups. A minimum s-t cut has the smallest such capacity among partitions that place s and t on opposite sides.
Computing a separate cut for every pair requires many queries. A Gomory-Hu tree stores the answers through only one fewer tree edge than the number of vertices. Its edges are a representation of cut relationships and need not correspond to physical connections in the original network. It is therefore different from a shortest-path tree or a minimum spanning tree.

How it works

A construction performs a sequence of minimum-cut computations and updates a tree structure that organizes the resulting partitions. The standard approach needs n - 1 such computations for n vertices, rather than separately solving all n(n - 1)/2 unordered pairs.
Once the tree is built, inspect the path between a queried pair and take the minimum edge weight. Removing a minimum-weight edge on that path partitions the tree into two components that give a corresponding minimum cut partition in the original graph. To identify the actual cut edges, return to the original graph and collect edges crossing that partition.

Three practical examples

A network-analysis exercise answers repeated pairwise separation-capacity questions from a compact tree.
A resilience study explores which vertex groups are separated by low-capacity cuts in a stated undirected model.
A graph-algorithm benchmark compares all-pairs cut queries against direct minimum-cut calculations on small test instances.

Think of it this way

Think of an index that summarizes the weakest separation between every pair of locations. The index lets you answer a particular question without reproducing the whole network. The analogy is limited because a tree edge can summarize several original edges, and its weight is a cut capacity rather than a physical link's length or reliability probability.

Worked example

Take an undirected triangle with capacities AB = 3, BC = 2, and AC = 1. To separate A from B, partition {A} from {B, C} for capacity 3 + 1 = 4, or partition {A, C} from {B} for capacity 3 + 2 = 5. The minimum A-B cut value is 4.
For A-C, the two relevant cuts have capacities 4 and 3, so the minimum is 3. For B-C, they have capacities 5 and 3, so the minimum is also 3.
A valid Gomory-Hu tree has edges AB with weight 4 and BC with weight 3. Its A-C path contains weights 4 and 3; the minimum is 3, matching the original cut value. Removing tree edge BC separates {C} from {A, B}. In the original triangle, that partition cuts AC and BC, with total capacity 1 + 2 = 3. Notice that the tree edge weight 4 on AB differs from the original edge capacity 3.

Illustrative case study

In a fictional infrastructure-modeling class, the Aspen team uses a Gomory-Hu tree to summarize a small undirected network. A participant initially interprets the tree as a proposed physical redesign and assumes omitted original edges have been removed.
The team labels the tree as a cut representation and displays each selected partition on the original network. It checks a few pairwise values against direct computations. The invented case illustrates interpretation and verification, not a real engineering recommendation or a claim that cut capacity captures every kind of service disruption.

Common misconceptions and mistakes

Do not add the weights along the tree path to answer a minimum-cut query; take the smallest weight. Do not use shortest-path distance as a substitute for cut capacity. A network with short routes can still have a low-capacity separating cut.
The standard Gomory-Hu construction here concerns undirected graphs. The cited NetworkX function rejects directed input. It also treats a missing named capacity attribute as infinite, so omitted data must not be mistaken for unit capacity. Different valid trees can represent the same pairwise cut values; the representation need not be unique.

Business use

The tree is useful when many minimum-cut queries are needed for one fixed undirected capacity model. It can support exploratory analysis and help explain separation bottlenecks across many pairs.
For a business or engineering interpretation, define exactly what capacity measures. A cut calculation does not automatically model time-varying demand, directional restrictions, correlated failures, or restoration procedures. If capacities change, the old tree may no longer answer the new problem correctly. Preserve the original graph and its capacity assumptions alongside the compact representation.

Check your understanding

In the triangle example, should the A-C cut value be 4 + 3 = 7?

Answer: No. The Gomory-Hu query takes the minimum path-edge weight, which is 3. The corresponding original cut separates C and crosses edges of capacities 1 and 2.

Related terms

Maximum Flow
Undirected graph
Minimum cut
cut capacity
weighted tree
all-pairs query
graph partition
NetworkX

Learn next

Learn next about the max-flow/min-cut theorem. Verify all three pairwise cut values in the triangle by enumerating separating partitions. Then change AC's capacity and recompute the values to see why a previously built tree should not be reused without checking the changed model.

Sources

NetworkX official Gomory-Hu tree documentation, including construction count and cut retrieval: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.gomory_hu_tree.html

Previous: Golomb coding Next: Gompertz distribution