Property

Tree edge (u,v) with weight w → cut of graph splitting u from v has value w. All pairs of vertices: minimum cut = min edge on tree path.

Advertisement

Construction

Iterative: pick any two vertices s, t. Compute min s-t cut. Contract each side, recurse. N-1 max-flow calls total.

Advertisement

Complexity

(N-1) × T(max-flow). For dense graphs O(N × V³) via naive flow.

Applications

Network reliability across all pairs. Multi-commodity flow lower bounds. Cluster analysis.