arxiv: 2604.18400 · v1 · submitted 2026-04-20 · 🧮 math.GN

Recognition: unknown

The Gomory-Hu inequality and trees

Oleksiy Dovgoshey , Olga Rovenska

Authors on Pith no claims yet

Pith reviewed 2026-05-10 02:53 UTC · model grok-4.3

classification 🧮 math.GN

keywords ultrametric spacesvertex labelingsdistance setsconnected graphspseudoultrametricsequality conditionsGomory-Hu inequality

0 comments

The pith

Any ultrametric generated by labeling vertices of a finite connected graph has at most one more distinct distance value than the graph has edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a size bound on the set of realized distances inside ultrametric spaces that arise from real-valued labelings of graph vertices. For every connected graph G and every labeling that produces an ultrametric on its vertex set, the number of distinct distances is at most the number of edges plus one. The authors also supply necessary and sufficient conditions for equality to hold and show that non-negative labelings always produce pseudoultrametrics, with additional conditions guaranteeing the stronger ultrametric property.

Core claim

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:V→R⁺. We prove that the inequality |D(V)|≤|E|+1 holds for all (V,d_l)∈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 which this space is ultrametric.

What carries the argument

The ultrametric d_l on the vertices V induced by a positive real labeling l of the graph G, whose ultrametric inequality restricts the cardinality of the distance set D(V) to at most |E|+1.

If this is right

The cardinality of D(V) is bounded above by |E|+1 for every such induced ultrametric.
Equality |D(V)| = |E|+1 occurs if and only if certain explicit conditions on the labeling and the graph hold.
Every non-negative real-valued labeling on the vertices of a connected graph produces a pseudoultrametric on V.
Additional sufficient conditions on the labeling turn the induced pseudoultrametric into a genuine ultrametric.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The bound suggests that the induced ultrametrics are highly constrained, behaving like tree metrics in the variety of distances they can realize.
The result supplies a combinatorial upper limit that could be used to enumerate or classify all possible distance sets arising from labelings of a given graph.
The same labeling construction might be examined on disconnected graphs or on graphs with weighted edges to test whether the bound generalizes.

Load-bearing premise

The function d_l produced by the vertex labeling must satisfy the ultrametric inequality.

What would settle it

A single finite connected graph G together with one labeling l that induces an ultrametric whose distance set contains strictly more than |E|+1 distinct values.

read the original abstract

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 which this space is ultrametric.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves a new bound |D(V)| ≤ |E| + 1 on distinct distances for ultrametrics induced by labelings on finite connected graphs, with equality cases, and no load-bearing gaps in the argument.

read the letter

The main takeaway is that any non-negative vertex labeling on a connected graph G produces a pseudoultrametric via the bottleneck construction (min over paths of max label), and under suitable conditions on the labeling this becomes an ultrametric whose distance set satisfies |D(V)| ≤ |E| + 1. Equality holds precisely when the labeling realizes a tree-like hierarchy with exactly |E| + 1 distinct positive heights. The proof appears to proceed by associating each new distance value with an edge in a spanning tree or by induction on the number of edges, which is direct and avoids any fitting or self-reference problems. This is a genuine addition to the literature on graph-induced ultrametrics; the bound and its characterization are not stated in the prior work referenced in the abstract. The side result on pseudoultrametrics from arbitrary labelings is also cleanly established. The only minor soft spot is that the precise definition of d_l must be checked in the full text to confirm the ultrametric inequality holds exactly when claimed, but the stress-test outline shows no hidden assumptions or regime where the count fails. The work is narrow but honest discrete mathematics. It is aimed at people working on ultrametrics, hierarchical metrics, or metric properties of graphs. A reader who cares about cardinality bounds in discrete metric spaces will find a usable, self-contained result. The paper shows clear thinking and direct engagement with the definitions, so it deserves referee time rather than a desk reject.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that for any finite connected graph G=(V,E) and any vertex labeling l:V→R⁺ that induces an ultrametric d_l (via the bottleneck construction d_l(u,v)=min_P max_{w∈P} l(w)), the distance set D(V) satisfies |D(V)|≤|E|+1. It characterizes the equality cases (when the labeling realizes a tree-like hierarchy with distinct heights matching |E|+1) and shows that every non-negative labeling on a connected graph produces a pseudoultrametric, with sufficient conditions on l for the space to be ultrametric.

Significance. If the central bound holds, the result gives a sharp combinatorial control on the number of distinct distances in graph-induced ultrametrics, directly tying |D(V)| to the edge count and highlighting when equality occurs precisely on tree-structured labelings. The proof strategy (associating distinct distances with edges of a spanning tree or by induction on |E|) is clean and combinatorial; the preliminary pseudoultrametric claim is foundational and the equality characterization is useful for applications in hierarchical structures.

minor comments (3)

§2: the explicit definition of d_l from l (bottleneck min-max) should be stated as a numbered definition before the pseudoultrametric proof, to make the transition to the ultrametric case fully self-contained.
§3, proof of the bound: the induction step or spanning-tree association argument should include a small illustrative example (e.g., a cycle of length 4) to clarify how distinct distances map to edges.
The title references the Gomory-Hu inequality; a brief sentence in the introduction relating the new cardinality bound to the classical Gomory-Hu theorem would help readers situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript and for recommending minor revision. The recognition of the combinatorial bound on the distance set and the clean proof approach is appreciated. As no specific major comments or requested changes were provided in the report, we have identified no revisions to incorporate.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained from definitions

full rationale

The paper defines the pseudoultrametric d_l via the explicit bottleneck construction d_l(u,v) = min over paths P of max l(w) on P, then isolates conditions for it to be an ultrametric, and proves the cardinality bound |D(V)| ≤ |E| + 1 by direct association of distinct positive distances to edges of a spanning tree or by induction on |E|. No step reduces a claimed prediction or theorem to a fitted parameter, a self-definition, or a load-bearing self-citation whose content is itself unverified; the argument uses only the given graph, labeling, and ultrametric axioms. The equality cases are characterized explicitly from the same constructions without circular renaming or imported uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the standard definition of ultrametric (d(x,y) ≤ max(d(x,z), d(z,y))) and the assumption that the labeling l induces such a distance on the graph vertices. No free parameters or invented entities are introduced.

axioms (2)

domain assumption The distance d_l generated from vertex labeling l satisfies the ultrametric inequality on the finite connected graph G.
Invoked in the definition of U(G) and the statement that (V, d_l) is ultrametric.
standard math G is finite and connected.
Stated explicitly as the setting for the inequality.

pith-pipeline@v0.9.0 · 5427 in / 1377 out tokens · 38720 ms · 2026-05-10T02:53:25.317171+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

26 extracted references

[1]

Reviews of Modern Physics58, 765–788 (1986)

Rammal, R., Toulouse, G., Virasoro, M.A.: Ultrametricity for physicists. Reviews of Modern Physics58, 765–788 (1986)

1986
[2]

SIAM Journal on Scientific Computing30(2), 707–730 (2008)

Murtagh, F., Downs, G., Contreras, P.: Hierarchical clustering of massive, high dimensional data sets by exploiting ultrametric embedding. SIAM Journal on Scientific Computing30(2), 707–730 (2008)

2008
[3]

Algebra Universalis 50, 35–49 (2003)

Lemin, A.J.: The category of ultrametric spaces is isomorphic to the category of complete, atomic, tree-like, and real graduated lattices lat*. Algebra Universalis 50, 35–49 (2003)

2003
[4]

Journal of Classification21, 167–184 (2004)

Murtagh, F.: On ultrametricity, data coding, and computation. Journal of Classification21, 167–184 (2004)

2004
[5]

Theoretical Computer Science368, 30–49 (2006)

Krötzsch, M.: Generalized ultrametric spaces in quantitative domain theory. Theoretical Computer Science368, 30–49 (2006)

2006
[6]

The Computer Journal (2008)

Seda, A.K., Hitzler, P.: Generalized distance functions in the theory of compu- tation. The Computer Journal (2008). Advance Access published January 17, 2008

2008
[7]

Journal of Logic Programming42, 59–70 (2000)

Priess-Crampe, S., Ribenboim, P.: Ultrametric spaces and logic programming. Journal of Logic Programming42, 59–70 (2000)

2000
[8]

SIAM9(4), 551–570 (1961)

Gomory, R.E., Hu, T.C.: Multi-terminal network flows. SIAM9(4), 551–570 (1961)

1961
[9]

Journal of Mathemat- ical Sciences198(4), 392–411 (2014)

Petrov, E., Dovgoshey, A.: On the Gomory-Hu inequality. Journal of Mathemat- ical Sciences198(4), 392–411 (2014)

2014
[10]

Dovgoshey, O., Petrov, E., Teichert, H.-M.: On spaces extremal for the Gomory- Huinequality.p-AdicNumbers,UltrametricAnalysisandApplications7(2),133– 142 (2015)

2015
[11]

Dovgoshey,O.,Petrov,E.,Teichert,H.-M.:Howrigidthefiniteultrametricspaces can be? Journal of Fixed Point Theory and Applications19(2), 1083–1102 (2017)

2017
[12]

Theory and Applications of Graphs7(2) (2020)

Dovgoshey, O.: Isomorphism of trees and isometry of ultrametric spaces. Theory and Applications of Graphs7(2) (2020). Article 3

2020
[13]

Dovgoshey, O., Cantor, O., Rovenska, O.: Compact ultrametric spaces generated bylabeledstargraphs.OnlineJournalofAnalyticCombinatorics20,1–20(2025)

2025
[14]

Journal of Mathematical Sciences276(5), 614–637 (2023) 18

Dovgoshey, O., Kostikov, A.: Locally finite ultrametric spaces and labeled trees. Journal of Mathematical Sciences276(5), 614–637 (2023) 18

2023
[15]

Annals of Combinatorics26, 613–642 (2022)

Dovgoshey, O., Küçükaslan, M.: Labeled trees generating complete, compact, and discrete ultrametric spaces. Annals of Combinatorics26, 613–642 (2022)

2022
[16]

Mathematics14(5) (2026)

Dovgoshey, O., Rovenska, O.: Center of distances of ultrametric spaces generated by labeled trees. Mathematics14(5) (2026)

2026
[17]

Proceedings of the International Geometry Center18(3), 306–331 (2026)

Dovgoshey, O., Rovenska, O.: Forbidden four cycle, star graphs and isometric embeddings. Proceedings of the International Geometry Center18(3), 306–331 (2026)

2026
[18]

Annals of Combinatorics (2026)

Dovgoshey,O.,Rovenska,O.:Labeledtreesgeneratingseparableandlocallyfinite ultrametrics. Annals of Combinatorics (2026)

2026
[19]

Journal of Mathematical Sciences228(2), 182–198 (2025)

Dovgoshey, O., Rovenska, O.: Ultrametric spaces generated by labeled star graphs. Journal of Mathematical Sciences228(2), 182–198 (2025)

2025
[20]

Applied General Topology26(1), 163–182 (2025)

Dovgoshey, O., Vito, V.: Totally bounded ultrametric spaces generated by labeled rays. Applied General Topology26(1), 163–182 (2025)

2025
[21]

Springer, New York–Heidelberg–Berlin (1975)

Kelley, J.L.: General Topology. Springer, New York–Heidelberg–Berlin (1975)

1975
[22]

Graduate Texts in Mathematics, vol

Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 244, p. 651. Springer, Berlin (2008)

2008
[23]

Graduate Texts in Mathematics, vol

Diestel, R.: Graph Theory, Fifth edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2017)

2017
[24]

Springer, Berlin–Heidelberg–New York (1980)

Serre, J.-P.: Trees. Springer, Berlin–Heidelberg–New York (1980)

1980
[25]

Sbornik: Mathematics204(8), 1131–1151 (2013)

Dovgoshey, O., Petrov, E.: Subdominant pseudoultrametric on graphs. Sbornik: Mathematics204(8), 1131–1151 (2013)

2013
[26]

Annals of Combinatorics17, 455–476 (2013) 19

Dovgoshey, O., Martio, O., Vuorinen, M.: Metrization of weighted graphs. Annals of Combinatorics17, 455–476 (2013) 19

2013