pith. sign in

arxiv: 2202.13844 · v4 · submitted 2022-02-28 · 💻 cs.DM · math.CO

All Graphs with at most 8 nodes are 2-interval-PCGs

Tiziana Calamoneri , Angelo Monti , Fabrizio Petroni This is my paper

Pith reviewed 2026-05-24 11:55 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords 2-interval-PCGtree representationgraph distancesmall graphsinterval graphs
0
0 comments X

The pith

Every graph with at most 8 nodes admits a 2-interval-PCG representation.

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

The paper proves that any graph on eight or fewer vertices can be expressed using a weighted tree and two intervals on the real line, where edges correspond exactly to leaf pairs whose weighted distance falls inside one of the intervals. This builds on the known fact that some graphs require more than two intervals, with the smallest known example having 135 vertices. Establishing the property for small orders helps locate the threshold where graphs first escape the 2-interval-PCG class. A reader would care because the result reduces the search space for counterexamples from all graphs to those with nine or more vertices.

Core claim

All graphs G with |V(G)| ≤ 8 are 2-interval-PCGs, meaning for each such G there exist a weighted tree T and two disjoint intervals I1, I2 on the non-negative reals such that vertices of G correspond to leaves of T and uv is an edge in G if and only if the distance between the corresponding leaves lies in I1 or I2.

What carries the argument

The 2-interval-PCG representation consisting of an edge-weighted tree T whose leaves are labeled by the graph vertices together with two disjoint intervals that encode the adjacency condition via leaf distances.

If this is right

  • The smallest possible order of a graph that is not a 2-interval-PCG is at least 9.
  • This constitutes a step toward identifying the exact minimal n for which a non-2-interval-PCG on n nodes exists.
  • Any future search for the smallest counterexample can restrict attention to graphs with 9 or more vertices.

Where Pith is reading between the lines

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

  • If the construction method scales, larger graphs might still be representable until some structural obstruction appears around the known 135-vertex bound.
  • Enumerating all non-isomorphic graphs on 9 vertices and testing for 2-interval-PCG representability would be a direct next computational step.
  • Similar exhaustive verification could be applied to other bounded-interval PCG variants to map their representability thresholds.

Load-bearing premise

That every one of the finitely many non-isomorphic graphs on at most 8 vertices possesses some weighted tree and pair of intervals reproducing its edge set exactly.

What would settle it

Exhibit even one graph on 8 or fewer vertices together with a proof that no weighted tree and two intervals can realize it as a 2-interval-PCG.

Figures

Figures reproduced from arXiv: 2202.13844 by Angelo Monti, Fabrizio Petroni, Tiziana Calamoneri.

Figure 1
Figure 1. Figure 1: The seven graphs with 8 nodes that are not PCGs. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The seven witness complete binary trees with 8 leaves and the [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The seven witness caterpillars with 8 leaves and the corresponding [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original abstract

A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.

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

1 major / 1 minor

Summary. The manuscript claims to prove that every graph on at most 8 vertices is a 2-interval-PCG: for each such G there exist a weighted tree T with non-negative edge weights and two intervals I1, I2 on the non-negative reals such that uv is an edge of G if and only if the leaf-to-leaf distance in T lies in I1 ∪ I2.

Significance. If the claim holds, it improves the known lower bound on the smallest order of a graph outside the 2-interval-PCG class from 135 to 9. This supplies a concrete incremental step toward determining the exact threshold at which non-2-interval-PCGs first appear.

major comments (1)
  1. [Abstract] Abstract (final paragraph): the existence claim for all 12 346 non-isomorphic graphs on 8 vertices is asserted, yet the manuscript supplies neither explicit constructions of T and the intervals nor any description of the enumeration algorithm, search-space pruning, or verification procedure. Because the result is purely existential and rests on exhaustive coverage, the absence of these details renders the central claim unverifiable from the text.
minor comments (1)
  1. [Abstract] The notation 'G = k-interval-PCG (T, I1, …, Ik)' is non-standard and should be replaced by a clearer predicate such as 'G is realized by (T, I1, …, Ik)'.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the need for greater transparency regarding the computational verification of our claim. We will revise the manuscript accordingly to address this point.

read point-by-point responses

  1. Referee: [Abstract] Abstract (final paragraph): the existence claim for all 12 346 non-isomorphic graphs on 8 vertices is asserted, yet the manuscript supplies neither explicit constructions of T and the intervals nor any description of the enumeration algorithm, search-space pruning, or verification procedure. Because the result is purely existential and rests on exhaustive coverage, the absence of these details renders the central claim unverifiable from the text.

    Authors: We agree that the manuscript as submitted does not include a description of the enumeration procedure, search-space pruning, or verification algorithm used to establish the claim for all 12346 non-isomorphic graphs on 8 vertices. In the revised version we will insert a dedicated subsection (likely in the Methods or a new Computational Verification section) that outlines: (i) the source and generation of the complete set of non-isomorphic 8-vertex graphs, (ii) the high-level algorithm employed to search for 2-interval-PCG representations (including the representation of the weighted tree T and the two intervals), (iii) any pruning or bounding techniques applied to make the exhaustive search feasible, and (iv) the verification steps confirming that every graph admits at least one valid representation. This addition will render the existential claim verifiable from the text without altering the mathematical result itself. revision: yes

Circularity Check

0 steps flagged

Existence proof by exhaustive case analysis or enumeration; no fitted parameters, self-definitional reductions, or load-bearing self-citations.

full rationale

The paper states an existence claim: every graph on ≤8 vertices admits a weighted tree T and two intervals I1,I2 such that edges are exactly those whose leaf distances fall in I1∪I2. The abstract and provided text contain no equations, no fitted quantities renamed as predictions, and no invocation of prior self-authored uniqueness theorems. The central result is a direct verification statement rather than a derivation that reduces to its own inputs by construction. No steps match any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of weighted-tree distances and interval membership; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard properties of edge-weighted trees and the real line (non-negative distances, interval membership).
    Invoked by the definition of k-interval-PCG given in the abstract.

pith-pipeline@v0.9.0 · 5698 in / 1140 out tokens · 44009 ms · 2026-05-24T11:55:11.562807+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Ahmed, M

    S. Ahmed, M. S. Rahman, Multi-interval pairwise compatibility graphs, Proc. Theory and Applications of Models of Computation (TAMC 2017) Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 71–84

    work page 2017

  2. [2]

    N. A. Azam, A. Shurbevski, H. Nagamochi, A method for enumerating pairwise compatibility graphs with a given number of vertices, Discrete Applied Mathematics 303 (2021) 171–185

    work page 2021

  3. [3]

    N. A. Azam, A. Shurbevski, H. Nagamochi, On the enumeration of min- imal non-pairwise compatibility graphs, Journal of Combinatorial Opti- mization (Sep. 2021)

    work page 2021

  4. [4]

    Calamoneri, A

    T. Calamoneri, A. Frangioni, B. Sinaimeri, Pairwise compatibility graphs of caterpillars, The Computer Journal 57 (11) (2013) 1616–1623

    work page 2013

  5. [5]

    Calamoneri, D

    T. Calamoneri, D. Frascaria, B. Sinaimeri, All graphs with at most seven vertices are pairwise compatibility graphs, The Computer Journal 56 (7) (2012) 882–886. 8

    work page 2012

  6. [6]

    Calamoneri, E

    T. Calamoneri, E. Montefusco, R. Petreschi, B. Sinaimeri, Exploring pair- wise compatibility graphs, Theor. Comput. Sci. 468 (2013) 23–36

    work page 2013

  7. [7]

    Calamoneri, M

    T. Calamoneri, M. Lafond, A. Monti, B. Sinaimeri, On generalizations of pairwise compatibility graphs, manuscript (2022)

    work page 2022

  8. [8]

    Calamoneri, B

    T. Calamoneri, B. Sinaimeri, Pairwise compatibility graphs: A survey, SIAM Review 58 (3) (2016) 445–460

    work page 2016

  9. [9]

    Durocher, D

    S. Durocher, D. Mondal, M. S. Rahman, On graphs that are not PCGs, Theoretical Computer Science 571 (2015) 78—87

    work page 2015

  10. [10]

    Kearney, J

    P. Kearney, J. I. Munro, D. Phillips, Efficient generation of uniform sam- ples from phylogenetic trees, Proc. Workshop on Algorithms in Bioinfor- matics (WABI 2003) Lecture Notes in Computer Science, Springer Berlin Heidel-berg, 2003, pp. 177–189

    work page 2003

  11. [11]

    Mehnaz, M

    S. Mehnaz, M. S. Rahman, Pairwise compatibility graphs revisited, Proc. International Conference on Informatics, Electronics and Vision (ICIEV 2013), IEEE, 2013

    work page 2013

  12. [12]

    Phillips, Uniform sampling from phylogenetic trees, Master’s thesis, University of Waterloo, Canada (2002)

    D. Phillips, Uniform sampling from phylogenetic trees, Master’s thesis, University of Waterloo, Canada (2002)

    work page 2002

  13. [13]

    M. S. Rahman, S. Ahmed, A survey on pairwise compatibility graphs, AKCE International Journal of Graphs and Combinatorics 17 (3) (2020) 788–795

    work page 2020

  14. [14]

    M. N. Yanhaona, M. S. Bayzid, M. S. Rahman, Discovering pair- wise compatibility graphs, Proc. International Computing and Combina- torics Conference (COCOON 2010), Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010, pp. 399–408. 9

    work page 2010