Gomory-Hu Tree

Imagine a road network with capacities on every lane. You want to know: if a flood cuts the city in two, which partition minimizes the total disrupted flow? Now imagine someone asks you that question for every pair of neighbourhoods simultaneously.

In a graph with n nodes, there are n(n−1)/2 ordered pairs — and computing each pair's max-flow from scratch would cost at least $n^{2}$ max-flow runs. In 1961, Ralph Gomory and T. C. Hu found a far better way.

Their insight: build a weighted tree on the same n nodes using only n−1 max-flow computations. This Gomory-Hu tree has a remarkable property — the minimum-weight edge on the unique path between any two nodes equals the max-flow between them in the original graph. All n(n−1)/2 answers, compressed into n−1 edges.

This is not an approximation. The tree is exact, and querying it takes only $O(n)$ time — a linear scan along the path. It is one of the most elegant data-structure results in combinatorial optimization, sitting at the intersection of max-flow theory and spanning trees.

The demo below has a fixed 5-node flow network (left panel) with capacities on each edge. The Gomory-Hu tree built from it is shown on the right. Select a source and a target and the demo will highlight the tree path and report the minimum edge weight on that path — which equals the max-flow between those nodes in the original network.

<p class="hint">{{hint}}</p>
<div class="panels">
  <div class="panel">
    <div class="panel-title">{{panel_net}}</div>
    <svg id="net-svg" width="220" height="220" viewBox="0 0 220 220"></svg>
  </div>
  <div class="panel">
    <div class="panel-title">{{panel_tree}}</div>
    <svg id="tree-svg" width="220" height="220" viewBox="0 0 220 220"></svg>
  </div>
</div>
<div class="controls">
  <label>{{lbl_source}} <select id="src"></select></label>
  <label>{{lbl_target}} <select id="tgt"></select></label>
  <button id="query" type="button">{{btn_query}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .87rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panels { display: flex; gap: 10px; flex-wrap: wrap; }
.panel { flex: 1 1 200px; }
.panel-title { font-size: .75rem; font-weight: 700; letter-spacing: .04em;
               text-transform: uppercase; color: #1d3557; margin-bottom: 4px; }
svg { background: #f0f4f8; border-radius: 10px; display: block; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin: .6rem 0 .3rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .3rem; }
select { font: inherit; padding: .22rem .4rem; border: 1px solid #bcc0c6; border-radius: 6px; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: .93rem; font-weight: 600; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.idle { color: #555; }

// Code not found

Notice that the tree has only 4 edges for 5 nodes, yet it answers all 10 pairwise flow questions instantly. The bottleneck edge on the tree path is always the answer — this is the Gomory-Hu guarantee.

The Gomory-Hu tree is a solved, polynomial-time result — not NP-hard, not open. Here is the full picture:

• Naive baseline: n(n−1)/2 max-flow runs — one per pair. For n = 100 that is 4950 max-flow calls.
• Gomory-Hu construction: exactly n−1 max-flow computations, proved sufficient by induction on the tree structure. For n = 100 that is 99 calls — a 50× reduction.
• Query time: $O(n)$ — find the unique tree path between two nodes (BFS or DFS) and return the minimum edge weight on it.
• Total cost: (n−1) × T(max-flow), where T(max-flow) is the cost of a single max-flow run (e.g. $O(V \cdot E)$ with Dinic's algorithm).

Why it works. The key theorem (Gomory & Hu, 1961) states: for any edge (u, v) in the tree with weight w, removing that edge partitions the tree into two parts S and V\S, and this partition is a minimum s-t cut in the original graph with capacity w. Every tree edge encodes both the max-flow value and a witness cut.

In 1990, Dan Gusfield gave an even simpler algorithm that builds an equivalent structure (cut-equivalent tree) using the same n−1 max-flow calls but without requiring augmenting-path bookkeeping — making implementation straightforward.

Contrast this with max-flow itself, which is also polynomial but has seen decades of refinement. The Gomory-Hu tree adds a structural layer on top: once the tree is built, the expensive per-pair computation is replaced by a cheap tree traversal.

Any system that needs all-pairs flow or cut information benefits from the Gomory-Hu tree:

• Network reliability: engineers ask "what is the worst-case failure mode between every pair of data centres?" The Gomory-Hu tree answers all pairs at the cost of n−1 flow runs, then stores the answers compactly.
• Hierarchical clustering: the tree naturally defines a dendrogram — cutting its minimum-weight edge partitions the graph into the two groups with the smallest max-flow, which is the tightest bottleneck. This is used in community detection on social graphs.
• Image segmentation: pixel graphs are huge, but the Gomory-Hu tree lets algorithms find all-pairs min-cuts without quadratic recomputation — speeding up interactive segmentation tools.
• VLSI design: checking connectivity requirements across chip regions uses all-pairs cut queries answered by the tree.
• Competitive programming: problems that ask "for each query (s, t), what is the maximum flow?" are solved in $O(n \log n)$ build + $O(n)$ per query using the Gomory-Hu tree.

The underlying idea — reduce quadratic queries to linear tree traversals — also inspired related structures like the Cactus representation of all minimum cuts (Dinits, Karzanov, Lomonosov, 1976), which extends the tree to capture all min-cut partitions, not just one per pair.

The Gomory-Hu tree is a reminder that structure, not brute force, is usually the key to efficiency. Computing all n(n−1)/2 pairwise max-flows independently seems to demand quadratic work — yet n−1 carefully chosen max-flow runs are enough, and the results fit in a single spanning tree.

Every edge in that tree is both a value and a proof: the minimum weight on the tree path between s and t is the exact max-flow, and the partition induced by removing that edge is a valid min-cut. No approximation, no heuristic.

If you have enjoyed this result, you will find related elegance in max-flow theory and in the minimum spanning tree — another case where a tree encodes global optimality far more compactly than expected.