pith. sign in

arxiv: 2604.07115 · v1 · submitted 2026-04-08 · 🧮 math.CO · math.MG

Smooth Graphs

Bo\v{s}tjan Bre\v{s}ar , Manoj Changat , Prasanth G. Narasimha-Shenoi , Bruno J. Schmidt , Peter F. Stadler This is my paper

Pith reviewed 2026-05-10 18:46 UTC · model grok-4.3

classification 🧮 math.CO math.MG
keywords smooth graphsPtolemaic graphsgraph metricsfive-point conditionmedian graphsl1-graphsforbidden subgraphsisometric subgraphs
0
0 comments X

The pith

Smooth graphs among Ptolemaic graphs are exactly the K1,1,3-free Ptolemaic graphs.

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

The paper studies smoothness for graph metrics, defined by a five-point condition that extends the original notion from step systems on graphs. This property is preserved under isometric subgraphs, Cartesian and strong products, and gated amalgams, so it holds for all median graphs, many related classes, and all l1-graphs. Induced copies of K2,3 or K1,1,3 destroy smoothness. The central result classifies smooth graphs inside the Ptolemaic graphs by showing they are exactly the members that contain no induced K1,1,3.

Core claim

Smoothness, defined via a five-point condition on distances, is a property preserved by isometric embeddings, products, and amalgams, making many structured graph classes smooth, but forbidden by induced K2,3 and K1,1,3; among Ptolemaic graphs, smoothness holds precisely for the K1,1,3-free members of the class.

What carries the argument

The five-point condition on distances that defines smoothness, together with the forbidden induced subgraph K1,1,3 inside the Ptolemaic graphs.

If this is right

  • Median graphs and many of their generalizations are smooth.
  • All l1-graphs are smooth.
  • Smoothness is preserved by isometric subgraphs, Cartesian and strong graph products, and gated amalgams.
  • An induced K2,3 or K1,1,3 is incompatible with smoothness.
  • Within the Ptolemaic graphs, smoothness is equivalent to being free of induced K1,1,3.

Where Pith is reading between the lines

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

  • The forbidden-subgraph characterization supplies a direct test for smoothness inside the Ptolemaic class.
  • The same five-point condition may link smoothness to convexity properties of point shadows in other distance spaces.
  • Similar preservation and obstruction results could be examined for non-connected graphs or for infinite graphs.

Load-bearing premise

The five-point condition is the correct generalization of smoothness from step systems to metrics on finite connected graphs.

What would settle it

Discovery of a Ptolemaic graph that contains an induced K1,1,3 yet satisfies the five-point condition, or a K1,1,3-free Ptolemaic graph that fails the five-point condition.

read the original abstract

The notion of smoothness was introduced originally in the context of step systems on connected graphs. Smoothness turns out to be a very general property of metrics defined by a five-point condition. Restricted to graphs, it is closely related to the convexity of point-shadows. We show that smoothness is preserved by isometric subgraphs, both Cartesian and strong graph products, and gated amalgams. As a consequence, median graphs and many of their generalizations are smooth. We also show that l1-graphs are smooth. On the other hand, an induced K2,3 or K1,1,3 is incompatible with smoothness. Finally, we characterize smooth graphs among the Ptolemaic graphs as precisely the K1,1,3-free Ptolemaic graphs.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript defines smoothness of graphs via a five-point condition on their shortest-path metrics. It proves preservation of smoothness under isometric subgraphs, Cartesian and strong products, and gated amalgams, shows that any induced K_{2,3} or K_{1,1,3} violates the condition, and concludes that the smooth Ptolemaic graphs are exactly the K_{1,1,3}-free Ptolemaic graphs. It further notes that l_1-graphs and many generalizations of median graphs are smooth.

Significance. If the central claims hold, the preservation theorems supply a robust toolkit for constructing smooth graphs from known classes, while the forbidden-subgraph characterization cleanly locates smoothness inside the well-studied Ptolemaic graphs. The explicit link between the five-point condition and convexity of point-shadows, together with the concrete incompatibility results for K_{2,3} and K_{1,1,3}, gives the work concrete structural value for metric graph theory.

minor comments (3)
  1. [Abstract] The abstract states that smoothness is 'closely related to the convexity of point-shadows'; a one-sentence definition or reference to the relevant prior definition would help readers who have not encountered the term.
  2. [Characterization section] The proof that Ptolemaic graphs are K_{2,3}-free is invoked as a standard fact because they are chordal; a brief citation or one-line reminder of the chordal characterization would make the argument self-contained.
  3. [Definition section] The five-point condition is stated for arbitrary metrics but then specialized to graph distances; an explicit remark confirming that the condition reduces correctly when the metric is the graph distance would remove any ambiguity for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report accurately captures the main contributions of the manuscript regarding the five-point condition for smoothness, its preservation properties, and the characterization among Ptolemaic graphs.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines smoothness directly via the five-point condition on graph metrics and derives all claims from this definition using standard graph-theoretic arguments: preservation under isometric subgraphs, Cartesian/strong products, and gated amalgams; explicit verification that induced K_{2,3} and K_{1,1,3} violate the condition; and the observation that Ptolemaic graphs are already K_{2,3}-free. The characterization of smooth Ptolemaic graphs as precisely the K_{1,1,3}-free ones follows immediately from these independent steps without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations. The derivation chain is self-contained and does not invoke unverified prior results by the same authors as the sole justification for the central theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the prior definition of smoothness and standard assumptions of graph theory; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • domain assumption Graphs under consideration are finite, undirected, and connected.
    Standard background assumption for metric studies on graphs.
  • domain assumption Smoothness is defined via the five-point condition introduced in earlier work on step systems.
    The central property is imported from prior literature.

pith-pipeline@v0.9.0 · 5439 in / 1316 out tokens · 58151 ms · 2026-05-10T18:46:10.374797+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    6, 701–714

    Hans-J¨ urgen Bandelt and Victor Chepoi,Decomposition andℓ 1-embedding of weakly median graphs, European Journal of Combinatorics21(2000), no. 6, 701–714

    work page 2000

  2. [2]

    Math.453(2008), 49–86

    Hans-J¨ urgen Bandelt and Victor Chepoi,Metric graph theory and geometry: a survey, Contemp. Math.453(2008), 49–86

    work page 2008

  3. [3]

    Math.62(1986), 245–260

    Hans-J¨ urgen Bandelt and Henry Martyn Mulder,Pseudo-modular graphs, Discr. Math.62(1986), 245–260

    work page 1986

  4. [4]

    Boˇ stjan Breˇ sar,Partial Hamming graphs and expansion procedures, Discrete Math.237(2001), 13–27

    work page 2001

  5. [5]

    Boˇ stjan Breˇ sar, Sandi Klavˇ zar, and RisteˇSkrekovski,Quasi-median graphs, their generalizations, and tree-like equalities, European Journal of Combinatorics24 (2003), 557–572

    work page 2003

  6. [6]

    Math.243(2013), 127–167

    Boˇ stjan Breˇ sar, Jeremie Chalopin, Victor Chepoi, Tanja Gologranc, and Damian Osajda,Bucolic complexes, Adv. Math.243(2013), 127–167

    work page 2013

  7. [7]

    Boˇ stjan Breˇ sar,Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory23(2003), no. 2, 215–225

    work page 2003

  8. [8]

    268, American Mathematical Society, 2020

    J´ er´ emie Chalopin, Victor Chepoi, Hiroshi Hirai, and Damian Osajda,Weakly modular graphs and nonpositive curvature, Memoirs of the Americal Mathemati- cal Society, vol. 268, American Mathematical Society, 2020

    work page 2020

  9. [9]

    Chavara, M

    Manoj Changat, John J. Chavara, M. R. Chitra, Joseph Mathew, and Peter F. Stadler,Step systems on graphs, Vietnam J. Math. (2026), in press

    work page 2026

  10. [10]

    Math.226(2001), 107–141

    Marc Chastand,Fiber-complemented graphs – I: structure and invariant sub- graphs, Discr. Math.226(2001), 107–141

    work page 2001

  11. [11]

    Victor Chepoi,Isometric subgraphs of Hamming graphs andd-convexity, Cybern Syst Anal24(1988), 6–11

    work page 1988

  12. [12]

    Geometry50 (1994), no

    ,Separation of two convex sets in convexity structures, J. Geometry50 (1994), no. 1-2, 30–51

    work page 1994

  13. [13]

    Report 2405.07512, arXiv, 2024

    ,Separation axiomS 3 for geodesic convexity in graphs, Tech. Report 2405.07512, arXiv, 2024

    work page arXiv 2024

  14. [14]

    Victor Chepoi and Damian Osajda,Dismantlability of weakly systolic complexes and applications, Trans. Amer. Math. Soc.367(2015), 1247–1272

    work page 2015

  15. [15]

    Chepoi,Classification of graphs by means of metric triangles, Metody Diskret

    Victor D. Chepoi,Classification of graphs by means of metric triangles, Metody Diskret. Analiz.49(1989), 75–93, Russian. 22

    work page 1989

  16. [16]

    F. R. K. Chung, R. L. Graham, and M. E. Saks,A dynamic location problem for graphs, Combinatorica9(1989), 111–131

    work page 1989

  17. [17]

    E. W. Dijkstra,A note on two problems in connexion with graphs, Numer. Math. 1(1959), 269–271

    work page 1959

  18. [18]

    Combinatorial Theory Ser

    D ˇZ Djokovi´ c,Distance-preserving subgraphs of hypercubes, J. Combinatorial Theory Ser. B14(1973), 263–267

    work page 1973

  19. [19]

    Andreas W M Dress and Rudolf Scharlau,Gated sets in metric spaces, Aequa- tiones mathematicae34(1987), 112–120

    work page 1987

  20. [20]

    A. J. Goldman and C. J. Witzgall,A localization theorem for optimal facility placement, Transportation Sci.4(1970), 406–409

    work page 1970

  21. [21]

    2, CRC press Boca Raton, 2011

    Richard H Hammack, Wilfried Imrich, Sandi Klavˇ zar, Wilfried Imrich, and Sandi Klavˇ zar,Handbook of product graphs, vol. 2, CRC press Boca Raton, 2011

    work page 2011

  22. [22]

    Pavol Hell and Ivan Rival,Absolute retracts and varieties of reflexive graphs, Canad. J. Math.39(1987), 544–567

    work page 1987

  23. [23]

    Graph Theory5 (1981), no

    Edward Howorka,A characterization of ptolemaic graphs, J. Graph Theory5 (1981), no. 3, 323–331

    work page 1981

  24. [24]

    Wilfried Imrich and Sandi Klavˇ zar,Retracts of strong products of graphs, Discrete Mathematics109(1992), 147–154

    work page 1992

  25. [25]

    Combin.19(1998), 677–685

    ,A convexity lemma and expansion procedures for bipartite graphs, European J. Combin.19(1998), 677–685

    work page 1998

  26. [26]

    Wilfried Imrich, Sandi Klavˇ zar, and Aleksander Vesel,A characterization of halved cubes, Ars Combinatoria48(1998), 27–32

    work page 1998

  27. [27]

    Math.57(1986), 175–226

    El Mostapha Jawhari, Driss Misane, and Maurice Pouzet,Retracts: graphs and ordered sets from the metric point of view, Contemp. Math.57(1986), 175–226

    work page 1986

  28. [28]

    Math.17(1965), 342–346

    David C Kay and Gary Chartrand,A characterization of certain Ptolemaic graphs, Canadian J. Math.17(1965), 342–346

    work page 1965

  29. [29]

    McKee,Clique graph representations of ptolemaic graphs, Disc

    Terry A. McKee,Clique graph representations of ptolemaic graphs, Disc. Math. Graph Theory30(2010), no. 4, 651–661

    work page 2010

  30. [30]

    Marina Moscarini,On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, Discr. Appl. Math.283(2020), 142– 152

    work page 2020

  31. [31]

    H. M. Mulder,The interval function of a graph, Math. Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, NL, 1980

    work page 1980

  32. [32]

    H. M. Mulder and L. Nebesk´ y,Modular and median signpost systems and their underlying graphs, Discuss. Math. Graph Theory23(2003), 309–324

    work page 2003

  33. [33]

    Centre Tracts, vol

    Henry Martyn Mulder,The interval function of a graph, Math. Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, NL, 1980

    work page 1980

  34. [34]

    Henry Martyn Mulder and Ladislav Nebesk´ y,Axiomatic characterization of the interval function of a graph, Eur. J. Comb.30(2009), no. 5, 1172–1185

    work page 2009

  35. [35]

    1, 173–178

    Ladislav Nebesk´ y,A characterization of the interval function of a connected graph, Czechoslovak Mathematical Journal44(1994), no. 1, 173–178

    work page 1994

  36. [36]

    J.47 (1997), no

    ,Geodesics and steps in a connected graph, Czechoslovak Math. J.47 (1997), no. 122, 149–161

    work page 1997

  37. [37]

    J.50(2000), 121–133

    ,A theorem for an axiomatic approach to metric properties of graphs, Czechoslovak Math. J.50(2000), 121–133. 23

    work page 2000

  38. [38]

    3, 635–642

    ,A characterization of the interval function of a (finite or infinite) connected graph, Czechoslovak Mathematical Journal51(2001), no. 3, 635–642

    work page 2001

  39. [39]

    J.54(2004), 445–456

    ,On properties of a graph that depend on its distance function, Czechoslo- vak Math. J.54(2004), 445–456

    work page 2004

  40. [40]

    J.55 (2005), no

    ,On signpost systems and connected graphs, Czechoslovak Math. J.55 (2005), no. 2, 283–293

    work page 2005

  41. [41]

    Richard Nowakowski and Ivan Rival,The smallest graph variety containing all paths, Discrete Mathematics43(1983), 223–234

    work page 1983

  42. [42]

    Shpectorov,On scale embeddings of graphs into hypercubes, Eur J Combin.14 (1993), 117–130

    S. Shpectorov,On scale embeddings of graphs into hypercubes, Eur J Combin.14 (1993), 117–130

    work page 1993

  43. [43]

    50, Elsevier, Amsterdam, 1993

    Marcel L J van De Vel,Theory of convex structures, North Holland Mathematical Library, vol. 50, Elsevier, Amsterdam, 1993

    work page 1993

  44. [44]

    2, 197–218

    Elke Wilkeit,The retracts of Hamming graphs, Discrete Math.102(1992), no. 2, 197–218. 24

    work page 1992