Hu-Gomory trees and Optimum Communication tree

Question

It is known that that can be several trees in a graph that follow the conditions of "Cut-tree" (also called Hu-Gomory tree).

For example (https://stackoverflow.com/questions/25297470/igraphs-gomory-hu-tree-not-working) In V={1,2,3}, E={{1,2},{2,3},{1,3}}, w({1,2}) = w({2,3})=1, w({1,3}) =0, all 3 possible spanning trees may are legal cut-trees.

In an article from 1974 it is stated that Hu-Gomory tree is an optimal communication tree https://epubs.siam.org/doi/pdf/10.1137/0203015 in the case of all distances equal to 1.

But in the graph i showed, only ({1,2},{2,3}) is optimal communication tree (with sum communication of 2), and other trees with sum communication of 3. How is this possible? Am i missing something?

Thanks

Answer 1

Taking the definition of a cut-tree from the linked paper (page 190, just before Lemma 1), or equivalently, the definition of a Gomory-Hu tree from Wikipedia, it appears that the answer in the linked stackoverflow answer is not correct. For your example, using the Wikipedia notation, $\lambda_{12}=\lambda_{13}=\lambda_{23}=1$. Now take the tree $T$ with edges $\{1,2\}$ and $\{1,3\}$. For $s=1$ and $t=2$, the $s$-$t$-path in $T$ contains only the edge $e=\{1,2\}$ which induces the cut $(S_e,T_e)$ with $S_e=\{1,3\}$ and $T_e=\{2\}$. The capacity of this cut is $2$ which is not equal to $\lambda_{12}=1$, and therefore $T$ is not a Gomory-Hu-tree. The same argument applies to the tree with edges $\{1,3\}$ and $\{2,3\}$, so for your example $\{\{1,2\},\{2,3\}\}$ is indeed the unique Gomory-Hu tree.