{"id":"arxiv/2604.18400","url":"https://arxiv.org/abs/2604.18400","tags":["math.GN"],"score":0,"title":"The Gomory-Hu inequality and trees","domain":"math.GN","source":"arxiv","authors":["Oleksiy Dovgoshey","Olga Rovenska"],"reviews":0,"subject":"math.GN","summary":"Let $G=(V,E)$ be a finite connected graph with vertex set $V$ and edge set $E$, and let $U(G)$ be the set of all ultrametric spaces $(V,d_l)$ generated by vertex labelings $l\\colon V \\to \\mathbb R^+$. We prove that the inequality $$ |D(V)| \\le |E| + 1 $$ holds for all $(V,d_l) \\in U(G)$, where $D(V)$ is the distance set of $(V,d_l)$. The necessary and sufficient conditions under which the above inequality turns to an equality are found. Moreover, we prove that each connected graph with non-negative vertex labeling generates a pseudoultrametric space and find some sufficient conditions under…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-20","reactions":{}}