A Characterization of Geodetic Graphs in Terms of their Embedded Even Graphs

Carlos E. Frasser

arxiv: 2601.17077 · v1 · submitted 2026-01-23 · 💻 cs.DM · math.CO

A Characterization of Geodetic Graphs in Terms of their Embedded Even Graphs

Carlos E. Frasser This is my paper

Pith reviewed 2026-05-16 12:03 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords geodetic graphsembedded even graphsbigeodetic graphsgraph characterizationeven cycles

0 comments

The pith

Geodetic graphs are built precisely from bigeodetic embedded even graphs.

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

The paper addresses the open classification problem for geodetic graphs by supplying a structural description in terms of their embedded even graphs. It states necessary and sufficient conditions that remove nongeodecity between every pair of opposite vertices in an even cycle. It then proves that every embedded even graph belonging to a geodetic graph is itself bigeodetic. The resulting claim is that bigeodetic graphs constitute the basic building blocks from which all geodetic graphs are assembled.

Core claim

The central claim is that a graph is geodetic precisely when each of its embedded even graphs satisfies the bigeodecity property, which is secured by local conditions eliminating nongeodecity of C-opposite vertices in every even cycle.

What carries the argument

Embedded even graphs (the even cycles contained in the host graph) equipped with the bigeodecity property that enforces the required distance uniqueness.

If this is right

Any geodetic graph decomposes into bigeodetic embedded even graphs.
Generation and enumeration of geodetic graphs reduce to the corresponding tasks for bigeodetic graphs.
Distance-uniqueness properties propagate directly from the even subgraphs to the host graph.

Where Pith is reading between the lines

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

The characterization may yield a practical recognition procedure for geodetic graphs.
It supplies a route to compare geodetic graphs with other distance-based classes through their shared even-cycle structure.

Load-bearing premise

Local conditions on opposite vertices inside every embedded even cycle together with bigeodecity are sufficient to guarantee the global geodetic property of the whole graph.

What would settle it

A single geodetic graph whose embedded even graph fails to be bigeodetic.

read the original abstract

The problem of finding the general classification of geodetic graphs is still open. We believe that one of the obstacles to attain this goal is that geodetic graphs lack a structural description. In other words, their fundamental properties have not yet been established in terms of the description of the complete graphs, paths and cycles contained within them. The absence of this information makes their generation and enumeration (as inherent parts of their general classification) a difficult task. This paper examines the structural qualities of geodetic graphs using their so-called embedded even graphs. To this effect, the necessary and sufficient conditions for eliminating the nongeodecity of each pair of C-opposite vertices in an even cycle C have been formulated, while the bigeodecity of the embedded even graphs of a geodetic graph has been established. In a sense, this allows us to arrive at the conclusion that the basic building blocks of geodetic graphs are precisely this class of bigeodetic ones.

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 gives nec+suff conditions on even cycles plus a bigeodecity result for embedded even graphs, but the step from those local fixes to a global geodetic property is not yet shown to hold without gaps.

read the letter

The main contribution here is the explicit formulation of necessary and sufficient conditions that remove nongeodecity between C-opposite vertices on even cycles, together with the proof that every geodetic graph has bigeodetic embedded even graphs. This framing lets the authors conclude that bigeodetic graphs are the basic building blocks. That is new relative to the cited literature and gives a concrete structural handle on an open classification problem. The bigeodecity claim itself looks clean and rests on standard definitions rather than circular reasoning. The local conditions on cycles are stated clearly enough that they could be checked on small examples. The soft spot is the jump to the global claim. The paper needs to show, not just assert, that satisfying the local conditions on every embedded even graph forces unique shortest paths between all vertex pairs, including pairs whose shortest paths cross several cycles. If that propagation step is only sketched, the characterization remains incomplete. No other major gaps appear in the abstract or the stated results. This is for readers already working on geodetic graphs or structural decompositions. It is worth sending to peer review because it directly attacks the open problem with usable conditions; referees can test the propagation argument and ask for examples that confirm the global property.

Referee Report

1 major / 1 minor

Summary. The paper claims to formulate necessary and sufficient conditions for eliminating nongeodecity between C-opposite vertices on even cycles, proves that every geodetic graph has bigeodetic embedded even graphs, and concludes that bigeodetic graphs are the basic building blocks of geodetic graphs, thereby offering a structural characterization of geodetic graphs in terms of their embedded even graphs.

Significance. If the central claims hold, the work would supply a long-missing structural decomposition of geodetic graphs via their embedded even graphs, directly addressing the open classification problem by identifying bigeodetic components as fundamental units. This could enable systematic generation and enumeration, which the abstract notes are currently difficult due to the lack of such descriptions.

major comments (1)

[Abstract and main conclusion] The transition from the local nec+suff conditions on even cycles and the bigeodecity of embedded even graphs to the global claim that these properties characterize geodetic graphs (i.e., ensure unique shortest paths between every pair of vertices) lacks an explicit argument. No demonstration is given that the local fixes propagate to pairs whose geodesics traverse multiple cycles or are not captured by a single even cycle, which is load-bearing for the characterization and the 'building blocks' conclusion.

minor comments (1)

[Abstract] The abstract announces the nec+suff conditions and the bigeodecity result but neither states the conditions explicitly nor supplies verification examples or proof sketches, which hinders immediate assessment of the claims.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address the major comment below and will revise the manuscript accordingly to strengthen the link between local conditions and the global characterization.

read point-by-point responses

Referee: [Abstract and main conclusion] The transition from the local nec+suff conditions on even cycles and the bigeodecity of embedded even graphs to the global claim that these properties characterize geodetic graphs (i.e., ensure unique shortest paths between every pair of vertices) lacks an explicit argument. No demonstration is given that the local fixes propagate to pairs whose geodesics traverse multiple cycles or are not captured by a single even cycle, which is load-bearing for the characterization and the 'building blocks' conclusion.

Authors: We agree that an explicit propagation argument is needed to connect the local necessary and sufficient conditions on even cycles (and the established bigeodecity of embedded even graphs) to the global uniqueness of shortest paths. In the revised manuscript we will insert a new subsection (in the main results) containing a theorem and proof showing that, for an arbitrary vertex pair, any candidate shortest path decomposes into segments lying within embedded even graphs; bigeodecity within each such graph together with the cycle-level conditions rules out alternative routes, including those crossing multiple cycles. This will rigorously justify the structural characterization and the claim that bigeodetic graphs are the fundamental building blocks. revision: yes

Circularity Check

0 steps flagged

No significant circularity; characterization uses independent local-to-global implications

full rationale

The derivation formulates necessary and sufficient conditions on even cycles to eliminate nongeodecity for C-opposite vertices and separately proves that geodetic graphs induce bigeodetic embedded even graphs. These steps rely on standard graph-theoretic definitions of geodesics, cycles, and bigeodecity rather than any quantity defined in terms of the target global property. The conclusion that bigeodetic graphs serve as building blocks follows directly from the stated implications without reducing the global geodetic property to a fit, self-definition, or self-citation chain. No load-bearing step equates the result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Only the abstract is available, so the ledger is inferred from mentioned concepts. No numerical free parameters are stated. The work relies on standard graph-theory background and introduces two new descriptive entities without independent evidence supplied in the abstract.

axioms (1)

standard math Standard definitions of geodetic graphs, even cycles, and shortest-path uniqueness in undirected graphs.
The paper presupposes the usual combinatorial definitions of these objects.

invented entities (2)

embedded even graph no independent evidence
purpose: Structural descriptor that captures the even cycles inside a geodetic graph.
Introduced as the central object for the characterization.
bigeodetic graph no independent evidence
purpose: Stronger property that the embedded even graphs of a geodetic graph are claimed to satisfy.
Defined within the paper as the basic building block.

pith-pipeline@v0.9.0 · 5457 in / 1399 out tokens · 50931 ms · 2026-05-16T12:03:22.752120+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2 ... the chord system of H eliminates the nongeodecity of all pairs of C-opposite vertices ... if and only if ... Every cycle consisting of an arc and a chord has odd length, |C1^2|=...=|C|=2L

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.