{"id":"7b139cf0-5cae-4d39-adf3-f7e32e3f5446","arxiv_id":"2607.15501","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Large 4-critical graphs can have only short runs of consecutive cycle lengths; for every k≥5 there are k-critical graphs with bounded chords per cycle; and every 31-vertex graph of minimum degree 8 has a cycle with at least 31 chords.","lead":"This paper settles three open graph-theory problems: it disproves a 2021 question for 4-critical graphs, disproves Voss's chord conjecture for every k≥5, and proves the Kára–Král conjecture that minimum degree 8 on 31 vertices forces a cycle with at least 31 chords. The main tools are explicit graph constructions and a block-decomposition proof.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.12 rests on the unproved terminal-cycle lemma (Lemma 4.3); if its distilled statement drops a hypothesis, the f(31,31)=8 proof collapses. The k=3 and Voss-counterexample parts are not affected.","rationale":"The k=3 counterexample (Theorem 1.2) is self-contained: the Hajós construction, Lemmas 2.3–2.4 and Theorem 2.5 check out, and the conclusion ρ(G_t)≤4 is arithmetic. The Voss counterexample (Theorem 1.6) is also well supported: the criticality proof in Lemma 3.7 and the chord-counting in Lemma 3.8 are detailed; the spine-edge chord argument is careful, and the O(k^2) bound depends only on k. I do not see a fatal gap there. The Kára–Král proof is the delicate part. Its structure is sound assuming Theorem 1.11, and the block analysis in Propositions 4.8–4.9 and Lemmas 4.6–4.7 is mostly coherent. But Theorem 1.11's non-Hamiltonian case is exactly Lemma 4.3, which is imported without proof. This is the weakest link because it is central and cannot be checked from the manuscript. The small garbled step in Lemma 4.6's Claim 4.1 reinforces that this section has not received the same level of checking as Sections 2–3, though it appears fixable. Therefore I agree with the reader's CONDITIONAL verdict; the condition should be a full verification of Lemma 4.3 (and a repair of Claim 4.1).","tokens_in":20892,"tokens_out":28928,"duration_ms":266301,"concrete_test":"Extract the non-Hamiltonian case of Ash's proof from [1] and verify that the statement of Lemma 4.3 appears there exactly, or obtain a complete proof of Lemma 4.3 from the terminal-cycle setup; if any hypothesis (such as a lower bound on the terminal cycle length or a 2-connectivity condition) is missing, Theorem 1.11 and hence f(31,31)=8 would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of f(31,31)=8 is a chain: Theorem 4.10 uses Proposition 4.8, whose case |Q(B*)|≥14 applies Theorem 1.11; Theorem 1.11's non-Hamiltonian half is exactly Lemma 4.3, which is not proved here. It is only said to be 'distilled' from Ash's proof. As stated, Lemma 4.3 is non-obvious: from accessibility of u1,u_{m-1} and degree≥d on accessible vertices inside H, it jumps to a cycle with d(d−2) chords in G, even though the terminal-cycle setup leaves vertices of P outside H whose role is not visible in the lemma. One cannot tell from this paper whether Ash's argument needs extra hypotheses (e.g., |W(H)| large, a lower bound on m, or 2-connectivity of G) that the distillation has silently dropped. If Lemma 4.3 is false or incomplete, Theorem 1.11 fails, so the |Q(B*)|≥14 branch of Proposition 4.8 fails and Theorem 4.10 has no proof. Separately, the proof of Claim 4.1 in Lemma 4.6 contains a garbled Hamilton-cycle construction: when X∩Y=∅, the written cycle 'a x b y c d P1 a' uses an edge b y that is not guaranteed; this is likely repairable (one can route through a Hamilton path in Q from b to c), but it shows the block-analysis section has not been independently verified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses three questions relating chromatic number or minimum degree to cycle lengths and chords. It first gives a negative answer to a question of Gao–Huo–Ma for k=3 by constructing 4-critical graphs G_t of order 3t+1 whose cycle-length sets contain no interval longer than 4 (Theorems 1.2 and 2.5). Second, it constructs k-critical graphs H_{k,m} with linearly many vertices but only O_k(1) chords on every cycle for every k≥4, thereby disproving a conjecture of Voss for k≥5 and, using the cited construction of Alexeev et al., also for k=4 (Theorem 1.6). Third, it proves the Kára–Král conjecture f(31,31)=8 (Theorem 1.12) by proving a degree-refined theorem (Theorem 1.11) and then carrying out a block-level extremal analysis. A final section proves a result on K4-free 4-chromatic graphs and gives an infinite family refuting a separate conjecture of Voss on 3-connected graphs.","tokens_in":21270,"tokens_out":13230,"duration_ms":121163,"significance":"If fully correct, this is a substantial paper. The k=3 negative answer and the Voss-conjecture counterexamples are cleanly demonstrated: the Hajós construction is elementary, the criticality proof is explicit, and the chord bound in Lemma 3.8 is explicit and constant in the order of the graph. The k=4 case is properly attributed to Alexeev et al., with the present contribution being the extension to all k≥5. The Kára–Král theorem is a significant extremal result, and the block decomposition in Propositions 4.8–4.9 appears carefully designed. However, the proof of Theorem 1.12 currently depends on an unproved imported lemma (Lemma 4.3), and another proof in the same section contains an invalid displayed cycle. These must be repaired before the paper can be considered correct as a self-contained contribution.","major_comments":[{"comment":"The terminal-cycle lemma is not proved in the paper; it is only said to be 'distilled' from Ash's proof, with no page or lemma number. This lemma is load-bearing: the non-Hamiltonian case of Theorem 1.11 is exactly Lemma 4.3, Proposition 4.8 applies Theorem 1.11 in the branch |Q(B*)|≥14, and Theorem 4.10 relies on Proposition 4.8. The statement is not immediate: it concludes from accessibility of u1,u_{m-1} and degree conditions on W(H) that G contains a cycle with d(d−2) chords, even though the terminal-cycle setup leaves vertices of P outside H. The manuscript provides no way to rule out dropped hypotheses on |W(H)|, m, or 2-connectivity. Please supply a complete proof, or quote Ash's argument in sufficient detail and verify that the distilled statement is correct.","section":"Section 4.1, Lemma 4.3"},{"comment":"The proof of Lemma 5.3 silently changes G to its complement. It asserts that 'Since δ(G)≥3, we have ∆(G)≤2' and later that 'G is triangle-free'; both assertions are false for the intended 6-vertex graph, the wheel W5, which has ∆=5 and contains triangles. The intended argument is coherent only if the unbarred graph is the complement throughout the proof. Please rewrite with explicit complement notation, re-check the matching and coloring arguments, and ensure the conclusion 'contains a cycle with four chords' is drawn for the original graph. As printed, the proof cannot be followed.","section":"Section 5.1, Lemma 5.3"},{"comment":"In the subcase X∩Y=∅, the displayed cycle 'a x b y c d P1 a' uses the edge b y, which is not guaranteed (b∈X, but y is not necessarily adjacent to b). The claim is probably repairable—for instance, take a Hamilton path in Q from b to c and finish with the edge d a—but as written the construction is invalid. Please correct the cycle and re-verify the rest of the case analysis, since Lemma 4.6 is used in Proposition 4.9.","section":"Section 4.2, Lemma 4.6, Claim 4.1"}],"minor_comments":[{"comment":"The sentence 'our graph H4,m is isomorphic to their graph Gm m' should read 'G_m'.","section":"Page 3, after Theorem 1.5"},{"comment":"The phrase 'select one that maximizes the length of the terminal cycle defined below' refers to an object not yet defined. Define the terminal cycle before the maximization, or state the choice criterion more formally.","section":"Page 9, terminal-cycle setup"},{"comment":"In the inequality |E(B*)| ≥ (8q(B*) + d_{B*}(x))/2, the degree d_{B*}(x) is inside B*, not in G. The surrounding text implies this, but an explicit sentence would avoid confusion, especially because x is a cut vertex of G.","section":"Page 12, Lemma 4.7"},{"comment":"The cited arXiv item [2] and the erdosproblems.com link are acceptable, but if a published version of [2] becomes available it should be cited in the standard way.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle to acceptance is Lemma 4.3: it is unproved, load-bearing for Theorem 1.12, and not verifiable from the manuscript. If the authors cannot provide a full proof or a precise, verified quotation from Ash, the Kára–Král proof collapses. The garbled notation in Lemma 5.3 and the invalid cycle in Claim 4.1 are correctable but must be fixed. The paper also includes an AI-usage declaration; the editor may wish to check that this complies with the journal's policy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main thing to know: this is a strong, substantial paper that resolves several open problems, but it is not ready to publish as is. The k=3 negative answer to Gao–Huo–Ma and the k≥5 counterexamples to Voss's conjecture are well-built and check out; the Kára–Král proof is the part that needs work.\n\nThe Hajós construction in Section 2 is clean. I checked the recurrence in Lemmas 2.3–2.4 and the resulting cycle-length set; it indeed gives ρ(G_t)=4 for all t≥3, which kills Problem 1.1 for k=3. The H_{k,m} construction in Section 3 is also solid: the leaf-forcing argument in Lemma 3.2 is convincing, criticality follows from the degree counts and cactus coloring, and the chord-counting in Lemma 3.8 is careful. The bound depends only on k, so Voss's conjecture is false for every k≥5. The k=4 case is attributed to Alexeev et al.; the paper says H_{4,m} is isomorphic to their graph, which I did not verify, but that is not load-bearing for k≥5.\n\nThe real issue is Theorem 1.12. The proof is a chain, and one load-bearing link, Lemma 4.3, is not proved. The paper states it is \"distilled from the proof of Ash's Theorem 1.\" That is not enough for a referee. Lemma 4.3 is non-obvious and its hypotheses involve accessible vertices in a terminal cycle while the conclusion is a chord-rich cycle in the whole graph. If the distillation has dropped a hypothesis, the |Q(B*)|≥14 branch of Proposition 4.8 fails and Theorem 4.10—and hence f(31,31)=8—collapses. The authors need either to prove Lemma 4.3 or to cite a precise lemma from Ash with a location.\n\nThere is also a genuine garble in Lemma 5.3 (used for Proposition 1.13): the proof says δ(G)≥3 implies Δ(G)≤2, which is false in G; the argument is being run in the complement. The result itself—the six-vertex K4-free 4-critical graph is the wheel—is true, but the proof as printed is not usable.\n\nOne stress-test concern I checked did not land: the alleged bad Hamilton cycle in Claim 4.1 of Lemma 4.6. The cycle a x b c y d P1 a uses the edge b-c, which is present because H[Q] is a clique after closure; it does not use the supposedly missing edge b-y. That part is fine.\n\nWho is this for? People working on chromatic-critical graphs, cycle lengths, and chorded cycles. It deserves a serious referee, but the referee will need to inspect Ash's paper. My recommendation: send it to peer review, and require the authors to prove or precisely cite Lemma 4.3 and to repair Lemma 5.3 before acceptance.","headline":"Strong paper with real results and a clear fix needed: the Kára–Král proof rests on an unproved 'distilled' lemma, and one side proof is garbled.","tokens_in":21841,"tokens_out":6304,"would_cite":true,"duration_ms":52529,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper settles three old questions about cycle chords and lengths in critical graphs: the 31-vertex/31-chord conjecture is true, and two growth conjectures fail.","keywords":["k-critical graphs","cycle lengths","cycle chords","minimum degree","consecutive cycle lengths","block decomposition","chromatic number","Hamiltonian cycles"],"falsifier":"Find a 2-connected non-Hamiltonian graph G with a terminal-cycle setup in which u1 and u_{m−1} are accessible and every accessible vertex has degree at least d inside H, yet G has no cycle with d(d−2) chords; such a graph would invalidate the terminal-cycle lemma and the theorem f(31,31)=8.","tokens_in":20742,"feed_emoji":"🔄","tokens_out":8578,"duration_ms":82010,"temperature":0.7,"pith_summary":"This paper answers three standing questions about how chromatic number, criticality, and minimum degree force cycles with many chords or long runs of consecutive lengths. It shows that the consecutive-cycle-length question fails already for k=3: there are 4-critical graphs of arbitrarily large order whose cycle lengths contain no interval of more than four consecutive integers. It refutes the conjecture that every large k-critical graph must contain an odd cycle with arbitrarily many chords, by building k-critical graphs of unbounded order in which every cycle has a number of chords bounded by a constant depending only on k. It proves the 31-vertex/31-chord conjecture in the affirmative, showing that minimum degree 8 is exactly the threshold. A reader should care because the results draw sharp lines around how much structural regularity chromatic-number conditions can force.","feed_headline":"Minimum degree 8 exactly forces a 31-chord cycle on 31 vertices","feed_subtitle":"It settles the 31-vertex chord conjecture and refutes two earlier conjectures about critical graphs.","key_machinery":"The three results use different engines. For k=3, the machine is a recursive chain of joins of copies of K4: at each step a new triangle is grafted onto a distinguished terminal edge, and recurrences for the sets of terminal-path lengths and cycle lengths give the exact formula L(G_t)={3,4}∪{5+3i,6+3i:0≤i≤t−2}∪{3t+1}, whose gaps (7+3i) cap ρ(G_t) at 4. For bounded chords, the graph H_{k,m} layers a clique of size k−3, a chain of m+1 spine pentagons, and pendant pentagons attached to spine vertices; each leaf forces a spine vertex to avoid a clique color, yielding k-criticality, while cycles can meet few leaf pentagons, bounding the chord count by binom(k−3,2)+10(k−3)^2+60(k−3). For f(31,31),","core_discovery":"In the paper's own terms, the central claim is a triple conclusion. First, for k=3, the consecutive-cycle-length question has a negative answer: there are 4-critical graphs G_t of order 3t+1 whose cycle lengths avoid arbitrarily long intervals; in fact, the largest run of consecutive cycle lengths, ρ(G_t), is at most 4 for all t≥3. Second, for every k≥4 there are infinitely many k-critical graphs in which every cycle has at most binom(k−3,2)+10(k−3)^2+60(k−3) chords, so the chord-growth conjecture for k-critical graphs is false. Third, every 31-vertex graph with minimum degree at least 8 contains a cycle with at least 31 chords, and minimum degree 7 does not suffice; hence f(31,31)=8. The pa","pith_inferences":["Editorial inference: the recursive-join construction used for k=3 is likely adaptable to higher k by joining copies of K_{k+1}; if so the negative answer to the consecutive-length question would extend beyond k=3, a step the paper does not take.","Editorial inference: the chord bound for H_{k,m} grows quadratically in k; whether the true maximum chord count in k-critical graphs is linear in k is a natural open problem.","Editorial inference: the block-closure argument for the 31-vertex theorem may be parameterizable to other small pairs (n,c), giving exact values of f(n,c) for nearby parameters, though the authors only establish (31,31).","Editorial inference: the K4-free four-chord result, combined with the pentagonal-wheel example, suggests a threshold phenomenon for K_r-free critical graphs that could be tested computationally for r≥5."],"forward_implications":["For k=3, the consecutive-cycle-length question is closed: no function f_3(n) exists, since the 4-critical graphs G_t have ρ(G_t)≤4.","For every k≥4 there are k-critical graphs of arbitrarily large order with at most binom(k−3,2)+10(k−3)^2+60(k−3) chords on every cycle, so the chord-growth conjecture is false.","The extremal function f(31,31) equals 8: minimum degree 8 suffices and minimum degree 7 does not.","Every K4-free graph with chromatic number at least 4 has a cycle with at least four chords.","The H_{k,m} construction recovers the earlier k=4 counterexample under relabeling, so the bounded-chord phenomenon is uniform across k≥4."],"fun_headline_variants":["Min degree 8 forces a 31-chord cycle on 31 vertices","No arbitrarily long consecutive cycle lengths in 4-critical graphs","Chord conjecture false for all k≥4 in k-critical graphs","31-vertex graph with min degree 8 always has 31-chord cycle","Consecutive cycle lengths question answered negatively for k=3"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof of the 31-vertex theorem depends on a terminal-cycle lemma imported from a 1985 proof rather than proved here; if that lemma's distilled statement is wrong or incomplete, the non-Hamiltonian case—and with it the f(31,31)=8 upper bound—collapses.","fun_headline_variants_meta":{"raw":{"variants":["Min degree 8 forces a 31-chord cycle on 31 vertices","No arbitrarily long consecutive cycle lengths in 4-critical graphs","Chord conjecture false for all k≥4 in k-critical graphs","31-vertex graph with min degree 8 always has 31-chord cycle","Consecutive cycle lengths question answered negatively for k=3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000853,"raw_usage":{"total_tokens":3625,"prompt_tokens":904,"completion_tokens":2721,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":2629}},"tokens_in":648,"tokens_out":2721,"duration_ms":20573,"temperature":1.0,"reasoning_tokens":2629,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T23:12:47.754955+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a 2-connected non-Hamiltonian graph G with a terminal-cycle setup in which u1 and u_{m−1} are accessible and every accessible vertex has degree at least d inside H, yet G has no cycle with d(d−2) chords; such a graph would invalidate the terminal-cycle lemma and the theorem f(31,31)=8.","supporting_citations":[],"review_version":1}