A non-existence result for vertex-girth-regular graphs
Pith reviewed 2026-05-09 21:59 UTC · model grok-4.3
The pith
No vertex-girth-regular graphs of girth 5 exist when the number of 5-cycles per vertex is within (k-1)/2 of the known upper bound.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every integer k ≥ 3 and every integer ε satisfying 0 < ε ≤ (k-1)/2, there does not exist a vgr(n,k,5, k(k-1)^2/2 - ε)-graph.
What carries the argument
The vgr condition (every vertex incident with exactly λ girth cycles) together with double counting of paths of length 2 that close into 5-cycles, which produces a contradiction when λ is assumed to equal the Moore-type upper bound minus a small ε.
If this is right
- For girth 5 the largest possible λ in any vgr graph must lie at least (k-1)/2 below the upper bound.
- Any (k,5)-cage must therefore realize a strictly smaller uniform cycle count than the bound permits.
- The same counting argument that produces the contradiction for small ε can be reused to obtain further lower bounds on the deficit from the maximum.
- Searches for cages of girth 5 are now restricted to graphs whose cycle distribution is measurably less uniform than the near-bound case.
Where Pith is reading between the lines
- The gap below the bound may be forced by the global topology of any girth-5 graph rather than by local counting alone.
- The result suggests that achieving the absolute maximum λ would require additional symmetry assumptions beyond regularity and fixed girth.
- The completed picture for odd girths indicates that even-girth cases may need separate techniques because the path-closing arguments differ in parity.
Load-bearing premise
The known upper bound on the number of girth cycles per vertex is taken as an absolute maximum that no graph can exceed.
What would settle it
Exhibiting a k-regular graph of girth 5 in which each vertex lies on exactly k(k-1)^2/2 - ε five-cycles for some k ≥ 3 and 0 < ε ≤ (k-1)/2 would disprove the claimed non-existence.
Figures
read the original abstract
A $k$-regular graph of girth $g$ is called vertex-girth-regular if every vertex is contained in the same number of cycles of length $g$. For integers $n, k, g$ and $\lambda$, we denote such a graph on $n$ vertices in which every vertex lies on exactly $\lambda$ cycles of length $g$ by a $\text{vgr}(n,k,g,\lambda)$-graph. It is well-known that any vertex-girth-regular graph satisfies $\lambda \le \frac{k(k-1)^{\left\lfloor \frac{g}{2} \right\rfloor}}{2}$. Graphs for which $\lambda$ is close to this bound are of particular interest in connection with the cage problem, since requiring many girth cycles through every vertex is a natural way to isolate highly structured candidates for small regular graphs of prescribed girth. In this paper, we prove that for every $k\ge 3$ and every integer $0< \varepsilon \leq \frac{k-1}{2}$, there does not exist a $\text{vgr}(n,k,5,\frac{k(k-1)^2}{2}-\varepsilon)$-graph. Previous non-existence results had already settled all odd girths at least $7$ and very recently also girth $3$, leaving girth $5$ as the only girth for which no non-trivial non-existence result was known. Thus, our result resolves the final remaining case and completes the picture for odd girths.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves a non-existence result for vertex-girth-regular graphs: for every integer k ≥ 3 and every integer ε with 0 < ε ≤ (k-1)/2, no vgr(n,k,5, k(k-1)^2/2 - ε)-graph exists. The argument uses double counting of 5-cycles and walks in a k-regular graph of girth 5 (where any two vertices share at most one common neighbor) together with the vgr condition that λ is constant, to show that λ must attain the full Moore-type upper bound or drop by at least (k-1)/2 + 1. This completes the non-existence picture for all odd girths.
Significance. If the result holds, it is significant for the cage problem and the study of highly structured regular graphs, as it rules out graphs whose λ lies in a specific gap below the known upper bound k(k-1)^2/2 without attaining the bound. The purely combinatorial proof (no vertex-transitivity, connectivity, or spectral assumptions required) supplies a clean integrality/parity obstruction and is a strength of the work.
minor comments (3)
- [Introduction] The introduction should explicitly cite the prior non-existence results for odd girths ≥7 and for girth 3 that are referenced in the abstract.
- [Section 1] The notation vgr(n,k,g,λ) is introduced in the abstract but would benefit from a formal definition in the first section before the main theorem is stated.
- [Proof of Theorem 1.1] A brief remark on whether the counting argument extends immediately to disconnected graphs (where λ constancy must still hold vertex-wise) would improve clarity.
Simulated Author's Rebuttal
We thank the referee for their positive evaluation of our manuscript, accurate summary of the main result, and recommendation for minor revision. We are pleased that the work is recognized as completing the non-existence picture for vertex-girth-regular graphs of all odd girths via a purely combinatorial argument.
Circularity Check
No circularity: self-contained combinatorial non-existence proof
full rationale
The paper establishes a non-existence theorem for vgr(n,k,5, bound-ε) graphs by double-counting 5-cycles and walks in k-regular girth-5 graphs where λ is constant. It invokes the standard external Moore-type upper bound λ ≤ k(k-1)^2/2 as a known fact (not derived here) and shows via integrality/parity that λ cannot lie in the open interval (bound - (k-1)/2, bound). All steps follow directly from the definitions of regularity, girth (at most one common neighbor), and constant λ; no parameters are fitted, no self-citations are load-bearing for the central claim, and the bound is treated as independent prior knowledge. The derivation is therefore self-contained and does not reduce to its inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Any vertex-girth-regular graph satisfies λ ≤ k(k-1)^floor(g/2)/2
Reference graph
Works this paper leans on
- [1]
- [2]
- [3]
-
[4]
G. Exoo and R. Jajcay. Dynamic cage survey.Electronic Journal of Combinatorics, DS16–Jul, 2012
work page 2012
-
[5]
J. Goedgebeur and J. Jooken. Exhaustive generation of edge-girth-regular graphs.Ex- perimental Mathematics, pages 1–13, 2025
work page 2025
- [6]
-
[7]
D. Holt and G. Royle. A census of small transitive groups and vertex-transitive graphs. Journal of Symbolic Computation, 101:51–60, 2020
work page 2020
- [8]
- [9]
- [10]
- [11]
-
[12]
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A new series of dense graphs of high girth.Bulletin of the American Mathematical Society, 32(1):73–79, 1995
work page 1995
-
[13]
T. Pisanski, D. Maruˇ siˇ c, P. Potoˇ cnik, A. Orbani´ c, B. Horvat, and P. Lukˇ siˇ c. The Encyclopedia of Graphs. URL:http://atlas.gregas.eu(accessed 2026-04-04)
work page 2026
-
[14]
P. Potoˇ cnik, P. Spiga, and G. Verret. Cubic vertex-transitive graphs on up to 1280 vertices.Journal of Symbolic Computation, 50:465–477, 2013
work page 2013
-
[15]
P. Potoˇ cnik, P. Spiga, and G. Verret. Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs.Journal of Combinatorial Theory, Series B, 111:148–180, 2015
work page 2015
-
[16]
P. Potoˇ cnik and J. Vidali. Girth-regular graphs.Ars Mathematica Contemporanea, pages 349–368, 2019
work page 2019
-
[17]
H. Sachs. Regular graphs with given girth and restricted circuits.Journal of the London Mathematical Society, 1(1):423–429, 1963. 13
work page 1963
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.