{"id":"add75a55-12c5-4440-97f1-1d2ef3deba58","arxiv_id":"2411.19023","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces the extremal problem for k-regular graphs of girth g without (g+1)-cycles, proves a Moore-type lower bound, and determines eight exact smallest orders by exhaustive search.","lead":"This paper studies the smallest k-regular graphs of girth g that contain no cycles of length g+1. It proves new lower bounds, computes several exact smallest orders, and proposes an exhaustive generation algorithm for these graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact values in Table 2 for n(3,9,10)=76 and other larger entries rest solely on Algorithm 1's completeness and termination, independently verified only for the four smallest cases.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing concern: the exact values in Table 2 depend on Algorithm 1 being a complete exhaustive generator that terminated as reported, with independent verification only for the four smallest cases. My stress-test of the mathematical core (Theorem 1, Proposition 3, Proposition 4) found no internal inconsistency; the proofs are careful and the double-counting arguments are valid. The abstract's monotonicity claim is indeed false as stated (e.g., n(3,3,4)=10 while n(3,4,5)≤6, since K_{3,3} has girth 4 and no 5-cycles), but this is a separate, easily correctable overstatement that does not undermine the computational results. The central risk is that the larger exact values — especially n(3,9,10)=76 — rest on a single implementation and supercomputer run. The paper's own Section 5.4 limits independent confirmation to orders at most 36, leaving the more demanding cases unverified. This warrants keeping the CONDITIONAL verdict: the mathematical framework appears sound, but the exactness of the larger entries should be confirmed by an independent exhaustive search or a formal completeness certificate before full acceptance.","tokens_in":14927,"tokens_out":15647,"duration_ms":131351,"concrete_test":"Run an independent exhaustive generator (e.g., GENREG or snarkhunter) to enumerate all cubic graphs of girth 9 on 74 vertices (and on 72), and test each for absence of 10-cycles. If any (3,9,10)-graph is found, then n(3,9,10) ≤ 74, contradicting the Table 2 value of 76. This directly checks the unverified part of the algorithm's exhaustive search.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central computational claim is that Table 2 gives exact values of n(k,g,g+1) for eight parameter pairs. These exactness statements require Algorithm 1 to be a complete exhaustive generator and to have terminated for all orders below the listed values. The mathematical lower bounds (Propositions 3 and 4) are sound, but they do not by themselves rule out intermediate orders such as n=72 or 74 for (3,9,10); those exclusions come only from the algorithm's reported run. Section 5.4 independently verifies only n(3,3,4)=10, n(3,5,6)=18, n(3,7,8)=36, and n(4,3,4)=15. The remaining entries — especially n(3,9,10)=76, n(4,5,6)=45, n(5,3,4)=26, and n(6,3,4)=34 — have no independent confirmation. A subtle bug in the canonical-form pruning (nauty) or in the eligible-edge pruning could discard a partial graph that is completable to a valid (k,g,g+1)-graph, which would make the reported exact value an upper bound only. The paper does not provide per-case termination certificates, timing logs, or a second implementation. Thus the exactness of the larger values is the most load-bearing assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies k-regular graphs of girth g that contain no cycles of length g+1, denoted (k,g,g+1)-graphs, and investigates the order n(k,g,g+1) of the smallest such graphs. The main theoretical results are a lower bound n(k,2t+1,2t+2) ≥ M(k,2t+1) + (k-2)k(k-1)^{t-1} (Proposition 3), a divisibility obstruction for equality in this bound (Proposition 4), and a two-step inequality n(k,g,g+1) ≤ n(k,g+2,g+3) - 2 (Theorem 1). The paper also proposes an exhaustive generation algorithm, reports exact values of n(k,g,g+1) for eight parameter pairs in Table 2, gives several upper bounds based on voltage lifts and vertex-transitive graph censuses, and uses the algorithm to prove a conjecture of Campbell on a smallest (3,6,7)-graph with odd girth 11. The lower-bound arguments are coherent and the connection to the cage problem via canonical double covers is clearly explained.","tokens_in":15219,"tokens_out":19417,"duration_ms":170704,"significance":"If the computational claims hold, the paper makes a solid contribution to the extremal regular graph literature: the lower bounds are new, parameter-free, and strengthen the Moore bound specifically for graphs forbidding the next cycle length; the exact values add useful data to the girth-pair problem; and the canonical double cover link gives a concrete route toward improving cage upper bounds for even girths. The paper also makes its code and generated graphs publicly available, and it includes independent verification for four of the eight exact values. The main reservations concern the completeness and independent confirmation of the larger computational entries, and an incorrect monotonicity statement in the abstract.","major_comments":[{"comment":"The abstract claims that the paper establishes 'the monotonicity of the function n(k,g,g+1) with respect to increasing g', but this is false: §5.1 explicitly notes that n(k,g,g+1) > n(k,g+1,g+2) is possible for odd g, and the table itself gives n(3,3,4)=10 while n(3,4,5)=n(3,4)=6. The actual theorem, Theorem 1, is the two-step inequality n(k,g,g+1) ≤ n(k,g+2,g+3) − 2, which is not monotonicity. The abstract and introduction should be corrected to state the precise inequality and to remove the misleading monotonicity claim.","section":"Abstract and §1"},{"comment":"The completeness of the exhaustive generator is not established by the description. The recursion state consists of the graph Γ together with the set eligibleEdges, which records edges that have been rejected in earlier branches. The canonical-form pruning described in optimization 1 compares only canonical forms of Γ, not of the pair (Γ, eligibleEdges). Two states with isomorphic graphs can have different eligible-edge sets, and a completion using an edge that is still eligible in one state may be impossible in the other; pruning the second state on the basis of graph isomorphism alone could therefore discard valid (k,g,g+1)-graphs. To justify the exactness of Table 2, the paper must either prove that the eligible-edge set is determined by the graph and the deterministic branching rule, or include the full state in the isomorphism check.","section":"§4, Algorithm 2 and optimization 1"},{"comment":"The exact values for the four larger entries of Table 2 — n(3,9,10)=76, n(4,5,6)=45, n(5,3,4)=26, and n(6,3,4)=34 — rest entirely on Algorithm 1 having terminated for every order below the listed value and on its completeness. Section 5.4 independently verifies only n(3,3,4)=10, n(3,5,6)=18, n(3,7,8)=36, and n(4,3,4)=15. In particular, for (3,9,10) the lower bound of Proposition 3 leaves only the intermediate even orders 72 and 74 to be excluded, and that exclusion is not independently confirmed by the voltage-lift search of §5.2, which covers only lifts of K_{1,3}^{loop}. The paper should provide per-case termination evidence (e.g., search logs or certificates) or an independent generation run for these cases before the exact values can be taken as established.","section":"§5.1 and §5.4, Table 2"}],"minor_comments":[{"comment":"In the paragraph after equation (2), 'the order of the canonical double cover would be of order 284' should read 288, since 2 × 144 = 288.","section":"§1"},{"comment":"The entries in the '# vertex orbits' column, such as '3 and 3' and '4 and 15', are not self-explanatory; the caption should state that these are the orbit counts of the respective non-isomorphic cages.","section":"§5.1, Table 2"},{"comment":"The claim that the number of relevant voltage assignments is bounded by the number of distinct 3-element subsets of G is inaccurate: with the spanning-tree voltages fixed, a voltage assignment is an ordered triple of group elements, so the number of assignments is |G|^3, not the number of 3-element subsets. The stated bound 'at most cubic in N' remains true, but the wording should be corrected.","section":"§5.2 and Appendix"},{"comment":"The update function 'newEligibleEdges ← update(eligibleEdges, Γ′)' is not specified; for reproducibility, the paper should define how eligibility is updated after adding or rejecting an edge.","section":"§4, Algorithm 2"},{"comment":"The proof of Campbell's conjecture is also computational, but Section 5.4 does not mention any independent verification for this case; it would be helpful to state how the uniqueness computation was checked or to classify it with the other computational results.","section":"§5.3"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound results (Propositions 3 and 4) and Theorem 1 appear sound, and the computational work is plausible and accompanied by public code. The main barriers to acceptance are the false monotonicity statement in the abstract and the need to either prove the completeness of Algorithm 1's canonical-form pruning with respect to the full state or describe the state as including eligibleEdges. The larger exact values in Table 2 would also benefit from stronger independent verification or detailed termination evidence. These issues are fixable within the scope of the paper, so I recommend major revision rather than rejection. There is no indication of circularity: the cited external results [4] and [12] are used as independent existence theorems, and the paper's lower bounds are derived rather than fitted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Eze, Jajcay and Jooken define (k,g,g+1)-graphs: k-regular, girth g, no (g+1)-cycles, and study the extremal order n(k,g,g+1). This is a genuinely new parameter, sitting between the Girth Pair problem and the classical Cage problem, and it earns its place. The mathematical core is sound: Proposition 3 gives a clean Moore-type lower bound, Proposition 4 adds a divisibility obstruction, and Theorem 1's vertex-removal argument (n(k,g,g+1) ≤ n(k,g+2,g+3)-2) is neat. The canonical double cover connection is the right motivation: it gives a concrete route to improving even-girth cage records, and the observation that a (3,11,12)-graph below 192 vertices would beat the 384-vertex (3,14) record is a nice, falsifiable hook.\n\nThe computational work is careful and reproducible: public code, data in House of Graphs, and independent verification for the four smallest cases. The proof of Campbell's uniqueness conjecture for the (3,6,7)-graph with odd girth 11 is a nice bonus.\n\nThe soft spots are real but manageable. The abstract claims monotonicity of n(k,g,g+1) in g; the paper's own logic shows n(3,3,4)=10 > n(3,4,5)=6 (the latter being K_{3,3}, girth 4, no 5-cycles). That claim is simply false as stated and must be fixed. Second, the exactness of the larger Table 2 entries — n(3,9,10)=76, n(4,5,6)=45, n(5,3,4)=26, n(6,3,4)=34 — rests on a single exhaustive-search implementation that is independently confirmed only for the four smallest cases. That is standard practice in this subfield, and I don't think it is fatal, but a second implementation for at least n(3,9,10) would transform 'probably exact' into 'certified exact.' A termination certificate or timing log for those runs would also help. Minor: the '284' in Section 1 should be 288.\n\nWho is this for? Graph theorists working on cages, girth-constrained extremal problems, and computational exhaustive generation. The paper deserves a serious referee; I expect it to appear with only modest revisions. I would accept.","headline":"Clean new extremal parameter with a solid lower bound and useful computational data; fix the abstract's false monotonicity claim and get a second implementation for the larger exact values before calling them fully certified.","tokens_in":15739,"tokens_out":5583,"would_cite":true,"duration_ms":58731,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper pins down exact minimal orders for eight families of $k$-regular graphs of odd girth $g$ with no $g+1$-cycle, and proves lower bounds that feed the classical Cage Problem.","keywords":["k-regular graphs","girth","cycle structure","extremal graphs","Cage Problem","graph generation algorithm","Moore bound","Girth Pair Problem"],"falsifier":"Generate all 3-regular graphs on 75 vertices with girth 9 and no 10-cycle using an independent method; one such graph would disprove $n(3,9,10)=76$. Alternatively, a $(3,11,12)$-graph on 143 vertices would refute Proposition 3.","tokens_in":14773,"feed_emoji":"📐","tokens_out":10365,"duration_ms":84144,"temperature":0.7,"pith_summary":"This paper asks how few vertices a $k$-regular graph of girth $g$ can have when, on top of forbidding all cycles shorter than $g$, it also forbids cycles of the very next length $g+1$. It proves a Moore-type lower bound for odd $g$: every such graph has at least $M(k,2t+1)+(k-2)k(k-1)^{t-1}$ vertices, and a divisibility condition that rules out equality in some cases. It also proves that skipping two in girth lowers the extremal order by at least two, and it supplies an exhaustive generation algorithm. Running that algorithm settles eight exact values, including $n(3,7,8)=36$ and $n(3,9,10)=76$, and gives upper bounds such as $n(3,11,12)\\le 272$. These orders feed the classical Cage Problem because a canonical double cover of a $(k,g,\\underline{g+1})$-graph is a $k$-regular graph of girth at least $g+3$.","feed_headline":"Eight exact orders found for graphs skipping the next cycle","feed_subtitle":"Lower bounds, exhaustive search, and double covers locate n(k,g,g+1) for eight pairs.","key_machinery":"The load-bearing object is the Moore tree $T_v(k,2t+1)$, the breadth-first tree of depth $t$ rooted at a vertex of a $(k,2t+1,\\underline{2t+2})$-graph; its leaves $S$ must be joined by horizontal edges to create the girth cycles. Lemma 2 caps the number of such horizontal edges at $|S|/2=k(k-1)^{t-1}/2$, so at least $(k-2)k(k-1)^{t-1}$ edges leave the tree and attach to distinct outside vertices, generating the lower bound. The exact values are carried by an exhaustive backtracking generator that starts from the disjoint union of a Moore tree and isolated vertices, branches on one eligible edge at a time, prunes any graph with a cycle shorter than $g$ or of length $g+1$, and uses canonical forms to suppress isomorphic branches. Around this, the canonical double cover inequality $n(k,g+3)\\le 2n(k,g,\\underline{g+1})$ connects the new orders to the Cage Problem, and voltage lifts of a four-vertex looped base graph are used to realize the small cubic cages.","core_discovery":"The paper's central claim is that the extremal orders $n(k,g,\\underline{g+1})$ are governed by the Moore tree at a vertex, the horizontal edges among its leaves, and the edges that must leave the tree. Proposition 3 establishes that for odd girth $g=2t+1$ the order is at least the Moore bound plus $(k-2)k(k-1)^{t-1}$, and Proposition 4 gives a divisibility obstruction: equality can hold only if $4t+2$ divides a certain product built from the order and the leaf count. For $k=3$ these bounds imply $n(3,11,12)\\ge 144$. The exhaustive algorithm, seeded by a Moore tree plus isolated vertices, then determines the exact values in Table 2 for eight parameter pairs, finding at most two non-isomorphic cages in each case and in several cases exactly one. The paper further proves uniqueness of the smallest $(3,6,7)$-graph with odd girth 11, resolving a 1997 conjecture, and identifies upper bounds for larger cases from voltage lifts and highly symmetric graph lists.","pith_inferences":["A pattern visible in the data but not proven in the paper is that every listed extremal graph of odd girth $g$ also contains a $(g+3)$-cycle; if this is general, the canonical double cover would deliver girth exactly $g+3$, sharpening the link to the Cage Problem.","The divisibility obstruction of Proposition 4 is likely the first member of a family of congruence conditions; testing larger $t$ computationally could reveal whether the lower bound of Proposition 3 is ever attainable.","The fact that the unique $(3,7,8)$- and $(3,9,10)$-cages are both voltage lifts of the same four-vertex looped base graph suggests parameterizing this lift family for girths beyond the range currently settled.","The exhaustive generator is designed for forbidding one specific cycle length, but the same canonical-form and eligible-edge pruning scheme would transfer to the more general girth-pair problem of prescribing both an even and an odd shortest cycle."],"forward_implications":["If the orders in Table 2 are correct, then for odd $g$ the canonical double cover of each listed $(k,g,\\underline{g+1})$-cage gives an explicit $k$-regular graph of girth at least $g+3$ whose order is close to the best known cage order at $g+3$.","The inequality $n(k,g,\\underline{g+1})\\le n(k,g+2,\\underline{g+3})-2$ implies that skip-two girth pairs produce strictly smaller extremal orders, a monotonicity statement for the new function.","Combining Proposition 3 and Proposition 4 gives $n(3,11,12)\\ge 144$, while the voltage-lift search gives $n(3,11,12)\\le 288$ and the symmetric-graph search improves this to $n(3,11,12)\\le 272$.","The uniqueness results identify exact small cages such as the unique $(3,5,6)$-cage on 18 vertices and the two $(3,3,4)$-cages on 10 vertices.","The proof of the 1997 uniqueness conjecture for the smallest $(3,6,7)$-graph of odd girth 11 closes a question that had been open since the problem was posed."],"supporting_citations":[{"why":"proves that k-regular graphs with prescribed short cycle spectrum exist, guaranteeing $(k,g,\\underline{g+1})$-graphs exist for all parameter pairs","marker":"[4]"},{"why":"supplies the dynamic cage survey data on known cage orders and record graphs used throughout for comparisons","marker":"[11]"},{"why":"provides the short proof of cage-order monotonicity whose idea Theorem 1 modifies","marker":"[13]"},{"why":"supplies the canonical-form computation used by the algorithm to prune isomorphic branches","marker":"[20]"},{"why":"gives the independent regular-graph generator used to verify the small exact values","marker":"[21]"},{"why":"gives the independent cubic-graph generator used to verify the cubic cases in Section 5.4","marker":"[5]"},{"why":"proves the voltage-lift girth theorem behind Corollary 6 and the lift-based upper bounds","marker":"[12]"},{"why":"supplies the small groups catalogue used to enumerate voltage assignments for the looped base graph in the appendix","marker":"[3]"}],"fun_headline_variants":["Exact orders of 8 smallest graphs that skip the next cycle","Smallest k-regular graphs with no (g+1)-cycles: 8 cases solved","New lower bounds and a uniqueness result for girth-pair graphs","Algorithm finds smallest graphs with prescribed girth and no next cycle","Uniqueness of the (3,11,12)-graph resolves 1997 conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact values in Table 2 rest on the assumption that the exhaustive generator is truly exhaustive: no partial graph thrown away by its pruning rules could have grown into a valid graph, and the supercomputer runs terminated exactly as reported; only the four smallest cases were checked against independent generators.","fun_headline_variants_meta":{"raw":{"variants":["Exact orders of 8 smallest graphs that skip the next cycle","Smallest k-regular graphs with no (g+1)-cycles: 8 cases solved","New lower bounds and a uniqueness result for girth-pair graphs","Algorithm finds smallest graphs with prescribed girth and no next cycle","Uniqueness of the (3,11,12)-graph resolves 1997 conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000988,"raw_usage":{"total_tokens":4243,"prompt_tokens":1051,"completion_tokens":3192,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":3092}},"tokens_in":667,"tokens_out":3192,"duration_ms":21202,"temperature":1.0,"reasoning_tokens":3092,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:37:23.466936+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate all 3-regular graphs on 75 vertices with girth 9 and no 10-cycle using an independent method; one such graph would disprove $n(3,9,10)=76$. Alternatively, a $(3,11,12)$-graph on 143 vertices would refute Proposition 3.","supporting_citations":[{"cited_title":"Boben, R","cited_arxiv_id":null,"evidence_quote":"proves that k-regular graphs with prescribed short cycle spectrum exist, guaranteeing $(k,g,\\underline{g+1})$-graphs exist for all parameter pairs"},{"cited_title":"Exoo and R","cited_arxiv_id":null,"evidence_quote":"supplies the dynamic cage survey data on known cage orders and record graphs used throughout for comparisons"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the short proof of cage-order monotonicity whose idea Theorem 1 modifies"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the canonical-form computation used by the algorithm to prune isomorphic branches"},{"cited_title":"Meringer","cited_arxiv_id":null,"evidence_quote":"gives the independent regular-graph generator used to verify the small exact values"},{"cited_title":"Brinkmann, J","cited_arxiv_id":null,"evidence_quote":"gives the independent cubic-graph generator used to verify the cubic cases in Section 5.4"},{"cited_title":"Exoo and R","cited_arxiv_id":null,"evidence_quote":"proves the voltage-lift girth theorem behind Corollary 6 and the lift-based upper bounds"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the small groups catalogue used to enumerate voltage assignments for the looped base graph in the appendix"}],"review_version":1}