# No nice generalization of Gomory-Hu tree

Gomory-Hu tree of a graph $G$ is a weighted graph $H$ on the same set of vertices. It has the two nice properties.

- It is a tree.
- For every $s,t$, there exist a min-$st$-cut in $H$ that is also a min-$st$-cut in $G$.

We could ask for a generalization. Given a graph $G$, can we find some *nice* graph $H$ such that

For every $S,T$ such that $1≤∣S∣,∣T∣≤k$ and $S∩T=∅$, there is a min-$ST$-cut in $H$ that is a min-$ST$-cut in $G$.

We recover Gomory-Hu tree when $k=1$. There were some consideration of a problem similar to this [1].

There are various useful definition of *nice* , for example
sparse or bounded treewidth. Likely none of them would apply, because we
can show that for $k=2$, there are graphs
where $H$ is almost the complete
graph.

Let $G$ be the complete graph on $n$ vertices, and each edge has capacity $1$. Let $f(S)$ be the sum of the capacity of edges going across $S$. There is a unique $ST$-min cut for every $∣T∣=1$ and $∣S∣=2$. Hence this shows that $f({v})=n−1$ for every $v∈V$. If $∣S∣=∣T∣=2$, there are exactly two min $ST$-cuts, either $S$ or $T$ in $G$. Assume that $T$ is not a min $ST$-cut in $H$, then $S$ has to be the min $ST$-cut in $H$. Therefore for all ${s_{1},s_{2}}$ such that $s_{1},s_{2}∈T$, we have $f({s_{1},s_{2}})=2n−4$. Because $f({s_{1}})=f({s_{2}})=n−1$, the edge between $s_{1}$ and $s_{2}$ has capacity $1$. The complete graph on $V∖T$ has to be a subgraph of $H$.

# References

**Tight Bounds for Gomory-Hu-like Cut Counting**, ArXiv e-Prints. (2015).