Elegant vertex labelings with prime numbers

Thierry Gensane

arxiv: 1907.01249 · v1 · pith:F6TG7GN2new · submitted 2019-07-02 · 🧮 math.CO

Elegant vertex labelings with prime numbers

Thierry Gensane This is my paper

Pith reviewed 2026-05-25 11:13 UTC · model grok-4.3

classification 🧮 math.CO

keywords elegant labelingprime vertex labelingpath graphsgraceful labelingodd primeseven differences

0 comments

The pith

Every path can be labeled with the first n odd primes so its edge differences are exactly the first n-1 even numbers.

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

The paper defines an elegant labeling of a tree on n vertices as an assignment of the first n odd primes to the vertices such that the absolute differences on the edges are precisely the numbers 2, 4, ..., 2n-2. It conjectures that this property holds for every path graph. The authors supply a search algorithm that constructs such labelings for every path with up to 3500 vertices. A sympathetic reader would care because the result would give a concrete, number-theoretic version of graceful labeling that works uniformly for all paths.

Core claim

The authors conjecture that each path is elegant: there exists an ordering of the first n odd primes on the vertices of the path such that the n-1 edge differences are exactly the set of the first n-1 even positive integers. They exhibit an algorithm that produces such orderings for every n up to 3500.

What carries the argument

Elegant labeling: assignment of the first n odd primes to vertices of a tree so that the absolute differences on edges equal exactly {2, 4, ..., 2n-2}.

If this is right

All paths would possess a prime-based analog of graceful labeling.
The first n odd primes can always be arranged so their consecutive differences cover each even integer up to 2n-2 exactly once.
The algorithm supplies an explicit construction for every path of length at most 3499.
The conjecture would unify the difference condition with the distribution of small primes.

Where Pith is reading between the lines

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

If the conjecture holds, it would suggest that the gaps between successive odd primes are sufficiently flexible to realize any prescribed set of even differences of the right size.
One could test whether similar labelings exist for other trees beyond paths or for label sets other than the initial odd primes.
A proof might connect to known results on prime gaps or to constructive methods for sequencing integers with prescribed differences.

Load-bearing premise

The computational search procedure always succeeds in locating a valid ordering of the primes for any tested path length and correctly verifies that the differences match the required even numbers.

What would settle it

Existence of an integer n > 3500 for which no ordering of the first n odd primes yields exactly the differences 2 through 2n-2 on a path, or discovery of an undetected error in the verification for some n ≤ 3500.

read the original abstract

We consider graph labelings with an assignment of odd prime numbers to the vertices. Similarly to graceful graphs, a labeling is said to be elegant if the absolute differences between the labels of adjacent vertices describe exactly the first even numbers. The labels of an elegant tree with $n$ vertices are the first $n$ odd prime numbers and we want that the resulting edge labels are exactly the first even numbers up to $2n-2$. We conjecture that each path is elegant and we give the algorithm with which we got elegant paths of $n$ primes for all $n$ up to $n=3500$.

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 defines elegant prime labelings on paths and conjectures they always exist, with an algorithm that works through n=3500 but no general proof.

read the letter

The main point is a conjecture that every path on n vertices admits a labeling with the first n odd primes such that the absolute differences on the edges are exactly the first n-1 even numbers. The authors supply a search algorithm and report that it finds such labelings for every n up to 3500. That computational range is the concrete contribution here. It extends the graceful labeling framework by swapping consecutive integers for odd primes while keeping the difference condition on even numbers, and the algorithm appears to be a direct backtrack or permutation search that succeeds without reported failures in the tested range. This gives honest, reproducible evidence for the existential claim on those instances. The obvious limitation is the absence of any proof or structural argument that would cover arbitrary n. The paper does not explain why the conjecture should hold beyond the computation, nor does it analyze the runtime or failure modes for larger n. If the search becomes intractable or a counterexample appears later, the current evidence would not catch it. The work is aimed at people already interested in graph labelings and prime sequences; it adds a specific open question with supporting data rather than a resolved theorem. A combinatorics journal that handles conjectures with computational backing could usefully send it to referees, who might assess the algorithm's reliability or suggest proof directions. I would engage with it at that level.

Referee Report

2 major / 2 minor

Summary. The paper defines elegant labelings of paths on n vertices by assigning the first n odd primes to vertices such that the absolute differences on the n-1 edges are exactly the even numbers 2, 4, ..., 2(n-1). It conjectures that every path admits such a labeling and reports a search algorithm that constructs them for every n ≤ 3500.

Significance. If the conjecture holds, it would supply a prime-number analogue of the graceful-labeling conjecture for paths (already known to be true). The explicit algorithm together with exhaustive verification up to n=3500 supplies concrete, reproducible evidence that can be checked independently and extended; this computational contribution is a clear strength of the manuscript.

major comments (2)

[Abstract] Abstract: the conjecture is asserted for arbitrary n, yet the only support supplied is computational success up to n=3500; because no general proof, reduction, or obstruction analysis is given, the central existential claim for all n remains open.
[Algorithm description] The algorithm section: the search procedure is described at a high level but without pseudocode, termination guarantees, or an explicit verification step that confirms the produced differences are precisely {2,4,...,2n-2} with no omissions or repetitions; this verification step is load-bearing for the reported computational evidence.

minor comments (2)

A small explicit example (e.g., the labeling for n=4 or n=5) would make the definition immediately verifiable.
The manuscript would benefit from citing the graceful-labeling literature and other prime-labeling papers to situate the new notion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We address the two major comments point by point below.

read point-by-point responses

Referee: [Abstract] Abstract: the conjecture is asserted for arbitrary n, yet the only support supplied is computational success up to n=3500; because no general proof, reduction, or obstruction analysis is given, the central existential claim for all n remains open.

Authors: The manuscript presents a conjecture, not a theorem. The abstract states the conjecture and reports the computational verification up to n=3500; it does not claim a general proof. Because the work is explicitly conjectural, the absence of a proof, reduction, or obstruction analysis is expected and accurately reflected in the current text. No change to the abstract is required. revision: no
Referee: [Algorithm description] The algorithm section: the search procedure is described at a high level but without pseudocode, termination guarantees, or an explicit verification step that confirms the produced differences are precisely {2,4,...,2n-2} with no omissions or repetitions; this verification step is load-bearing for the reported computational evidence.

Authors: We agree that the algorithm description would benefit from greater explicitness. In the revised version we will add (i) pseudocode for the backtracking search, (ii) a statement that the procedure terminates for every finite n because the search space is finite, and (iii) an explicit verification routine that, after each successful labeling, confirms the absolute differences on the edges are exactly the set {2,4,...,2(n-1)} with no omissions or repetitions. revision: yes

Circularity Check

0 steps flagged

No circularity; conjecture rests on explicit search algorithm

full rationale

The paper advances an existential conjecture (every path admits an elegant prime labeling) backed by direct computational search that enumerates permutations of the first n odd primes and verifies the edge-difference condition against the first n-1 even numbers. No equations, fitted parameters, or self-citations are used to derive the labelings; the reported success up to n=3500 is obtained by running the stated algorithm on external prime lists. No load-bearing step reduces the claim to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies entirely on standard axioms of number theory (odd primes differ by even amounts) and graph theory (path graphs and absolute differences). No free parameters are fitted and no new entities are postulated; the contribution is the conjecture plus computational verification.

axioms (2)

standard math Odd primes greater than 2 differ by even positive integers.
This guarantees that all edge labels produced by vertex differences are even numbers, satisfying the elegant condition definition.
domain assumption The set of absolute differences on a path must be exactly the distinct even numbers from 2 to 2(n-1).
This is the explicit requirement in the elegant labeling definition given in the abstract.

pith-pipeline@v0.9.0 · 5612 in / 1529 out tokens · 72175 ms · 2026-05-25T11:13:29.931480+00:00 · methodology

Elegant vertex labelings with prime numbers

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)