Gomory-Hu Tree is a representation of graph and it is mainly used for analyzing Max-Flow or Min-Cut problems.

#### Definition:

For a undirected graph , we say tree is a gomory-hu tree of G if

- (
*flow equivalence*) For every pair , value of max flow in G is equal to in T. - (
*Cut property*) Suppose is the minimum weight among all edges on path from s to t, then we find a min cut of the original graph where is connected component in T after removing edge (u,v).

#### Existence and related theorems:

Basically, we construct a algorithm which gives desirable tree. Details could be found here.

#### Application:

Gomory-Hu tree is a beautiful and powerful representation of a graph. Many problems related to min cut or max flow could be solved perfectly by it.

- Find global minimum cut set, namely min cut set with smallest value among all possible min cut sets.
- Given a matrix , determine if there exists a graph such that value of min cut is .
- Minimum k-cut problem (Gomory-Hu tree induces an approximated solution).