{"id":"350004a4-4849-4c96-9cdf-4eda016651be","arxiv_id":"2507.12798","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains a cycle whose length is a multiple of 4, and this bound is sharp for all n at least 12.","lead":"This paper finds that a 2-connected graph on n vertices with no cycle of length divisible by 4 has at most (3n-1)/2 edges, rounded down, and it builds graphs reaching that bound for every n of size 12 or more. The result settles the 2-connected version of a question left open by the recent 19/12 bound for all graphs, and it adds a new method for constructing extreme examples.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2.3 is the load-bearing classification; its appendix defers critical cases to unreviewed code and contains roughly sketched inductions, so the exact bound is not yet independently verifiable.","rationale":"The reader's weakest-assumption analysis already identifies Proposition 2.3 as load-bearing, and my read agrees. The proof of Theorem 1.2 proceeds by minimal counterexample, forces planarity via [9]'s non-planar result, and then uses Proposition 2.3 to control the two sides of every 2-vertex cut. Those controls feed directly into Lemma 3.1's f3 <= 2 and f5 <= 5, which drive the Euler-formula contradiction. No circularity is apparent: the external results [5,9] are from different author groups, and no fitted parameters occur. The internal weakness is real but not a demonstrated falsehood: the appendix is a sketch, the (A5) case is left to 'tedious case checking', and the supplementary code is unpinned. I also noticed a separate terse assertion in Claim 3.16 that G0 = G - {v,w,w1,w2} is 2-connected with no argument; that is a secondary gap worth attention, but Proposition 2.3 is the broader structural hinge and the one the authors themselves flag. A complete independent enumeration for n <= 9 is cheap and decisive; if it confirms Table 2, Theorem 1.2 should be accepted. Hence I keep the reader's CONDITIONAL verdict.","tokens_in":24837,"tokens_out":23258,"duration_ms":238365,"concrete_test":"Independently enumerate all graphs on 3 to 9 vertices, e.g. with nauty geng, filtering those with no cycle length 0 mod 4 and with every edge contained in some (x,y)-path, then for each two-element residue class L compute the maximum e(H) and the reversing-equivalence classes of extremal graphs; verify Table 2 and the (A1)-(A5) equality statements. Additionally, clone the cited repository, record a specific commit hash, and re-run its case analysis; the classification counts as verified only if the independent enumeration and the pinned code agree.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem collapses if Proposition 2.3 is wrong: it drives Lemmas 3.5, 3.7, and hence Lemma 3.2's vertex-cut conclusion that one side of a 2-vertex cut is K3, F3, or F4, which in turn yields the triangle and 5-face bounds used in the Euler contradiction. The appendix explicitly flags that 'Some cases are written in a rough way', that (A5) ends in 'tedious case checking', and that verification is delegated to a GitHub repository with no commit hash, run instructions, or certificate that the code enumerates exactly the cases (A1)-(A5). The equality cases F7, F8, F9 at n=7,8,9 are used quantitatively in Lemma 3.5(i) and Claim 3.8; a single missed graph or a wrong upper bound at these orders would invalidate the contradiction. This is a verification gap, not a demonstrated error, so the appropriate status is conditional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper determines the extremal number of edges in a 2-connected graph that contains no cycle of length 0 modulo 4. The main result, Theorem 1.2, states that any 2-connected n-vertex graph with more than floor((3n-1)/2) edges contains such a cycle, and Section 4 constructs 2-connected extremal graphs attaining exactly floor((3n-1)/2) edges for every n >= 12. The proof proceeds by taking a minimal counterexample, using the result of [9] that every non-planar graph contains a (0 mod 4)-cycle to reduce to planar graphs, analyzing the structure of 2-vertex cuts through a sequence of lemmas culminating in Lemma 3.2, bounding the numbers of 3-faces and 5-faces (Lemmas 3.13 and 3.14), and finally deriving a contradiction from Euler's formula. Tightness is shown by a gap-reducing construction based on the small graphs F3, F4, F6, F7, F8, and F9.","tokens_in":24968,"tokens_out":4151,"duration_ms":50870,"significance":"If the main theorem is correct, it provides the first exact extremal result for cycles of length 0 modulo 4 within the 2-connected class, giving a linear coefficient of 3/2 instead of the general bound 19/12 from [9]. The result would also add a clean exact value to the catalogue of c_{ell,k} constants for a constrained graph class, and the proposed construction method in Section 4 appears flexible enough to produce many extremal examples. The overall architecture of the proof is convincing: the reduction to a planar minimal counterexample, the vertex-cut decomposition, and the Euler-formula face-counting argument are all coherent. The paper also makes an honest attempt to handle finite cases by providing code, but that code is not yet in a form that makes the classification independently verifiable; this is the main obstacle to accepting the proof as complete.","major_comments":[{"comment":"The proof of Proposition 2.3 is not complete as written. The appendix explicitly states that 'Some cases are written in a rough way,' that case (A5) ends with 'tedious case checking,' and that verification is delegated to a GitHub repository with no commit hash, no run instructions, and no certificate that the code enumerates exactly the cases (A1)-(A5). Proposition 2.3 is load-bearing: it drives Lemma 3.5, Lemma 3.7, and Lemma 3.2, which in turn produce the triangle and 5-face bounds used in the Euler-formula contradiction. A wrong or missing case in this finite classification would invalidate Theorem 1.2. Please provide a fully written proof of all five cases or a versioned, executable certificate whose coverage of (A1)-(A5) is machine-checked.","section":"Appendix, proof of Proposition 2.3"},{"comment":"The equality characterization in Proposition 2.3 is used in a quantitative way, not merely as an upper bound. In Lemma 3.5(i) the argument distinguishes whether G1 is reversing-equivalent to F7 and whether G2 is reversing-equivalent to F8, and in Claim 3.8 it requires that G2 is reversing-equivalent to F9 when 5 <= n2 <= 9. The numerical contradictions depend on these exact classifications, so the unverified structural part of Proposition 2.3 is directly responsible for the face-counting contradiction. This strengthens the need to make the appendix's verification fully rigorous.","section":"Section 3.1, Lemma 3.5(i) and Claim 3.8"}],"minor_comments":[{"comment":"The phrase 'reserving-equivalent' should be 'reversing-equivalent' throughout the definition and subsequent usage.","section":"Section 2.2"},{"comment":"In the sentence 'V(H) ∩ E(Ci) = ∅', the first set should presumably be 'E(H)', so that the condition reads 'E(H) ∩ E(Ci) = ∅'; as written it is not meaningful.","section":"Lemma 2.7(iv) proof"},{"comment":"The repository link should be accompanied by a version identifier (commit hash) and explicit instructions for reproducing the verification; ideally the code should output a certificate that each of the enumerated cases (A1)-(A5) is covered.","section":"Appendix, code repository"},{"comment":"The constructions in Figure 14 are described briefly; a short explanation of why the two displayed examples have no (0 mod 4)-cycles would improve readability.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is plausible and the proof strategy is sound, but the load-bearing finite classification in Proposition 2.3 is currently verified only by a rough sketch plus an unversioned repository. This is a verification gap rather than a demonstrated mathematical error, so I recommend major revision rather than rejection. I would support acceptance once the finite cases are either fully written or supplied as a reproducible, versioned certificate. I also see no indication of self-citation circularity or author-overlap concerns in the cited heavy results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"New exact result: for 2-connected n-vertex graphs avoiding (0 mod 4)-cycles, e(G) ≤ floor((3n-1)/2), with tight examples for every n≥12. That's a genuine new entry in the modular-cycle extremal catalogue, and it answers the natural 2-connected version of the Győri et al. result. The high-level proof is clean: minimal counterexample, planarity, a structural lemma (Lemma 3.2) about 2-vertex cuts, bounds on 3-faces and 5-faces, and a short Euler-formula contradiction. The gap-reducing construction (Propositions 4.1, 4.2) is a concrete way to generate infinitely many extremal graphs in many shapes. Citation pattern is fine; the load-bearing external results come from non-overlapping groups, and no constant is fitted.\n\nThe soft spot is Proposition 2.3, the small-graph classification that drives Lemmas 3.5, 3.7, and Lemma 3.2. The appendix says outright that some cases are written roughly, the (A4)/(A5) checks are 'tedious case checking', and the rest is delegated to a GitHub repository with no commit hash, no run instructions, and no certificate that the code enumerates exactly cases (A1)-(A5). If that classification has a gap, the face-counting contradiction and the main theorem collapse. The equality cases F7, F8, F9 are used quantitatively, so a single missed graph at n=7,8,9 would matter. That's a verification gap, not a demonstrated error, but for an exact bound it's the difference between a proof and a conjecture.\n\nThere are also a few 'it is not difficult to find' steps in Lemma 3.13, but those are more local and less worrying. The rest of the paper is careful and honestly written.\n\nI'd send this to peer review. The theorem deserves referee time, and the conditional is actionable: fill in the case checks or provide a proper artifact—exact enumeration, commit hash, run instructions, and a certificate that the code covers (A1)-(A5). Once that's done, this is a solid contribution. For now, cite with caution; it's likely correct, just not independently checkable as-is.","headline":"New exact extremal bound for 2-connected graphs without (0 mod 4)-cycles, with a load-bearing classification that is only sketch-verified.","tokens_in":25697,"tokens_out":3241,"would_cite":true,"duration_ms":32573,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A 2-connected $n$-vertex graph with more than $\\lfloor (3n-1)/2 \\rfloor$ edges necessarily contains a cycle whose length is divisible by 4, and the bound is tight for every $n\\ge 12$.","keywords":["0 mod 4 cycles","cycles modulo k","extremal graph theory","2-connected graphs","planar graphs","Euler formula","edge bounds","gap-reducing constructions"],"falsifier":"An exhaustive search over 2-connected graphs on at most, say, 12 vertices, or over all graphs $(H;x,y)$ with $n\\le 9$, would settle the classification: the theorem is false if any 2-connected $n$-vertex graph without a $(0 \\bmod 4)$-cycle has more than $\\lfloor (3n-1)/2 \\rfloor$ edges, and Proposition 2.3 is false if, for instance, a 7-vertex graph with $(x,y)$ a $\\{2,3\\}$-type has 9 edges or a 9-vertex $\\{2,3\\}$-type graph has 13 edges. Completing the omitted appendix cases by a certified exhaustive check would confirm the supporting classification.","tokens_in":24457,"feed_emoji":"🔄","tokens_out":11455,"duration_ms":108921,"temperature":0.7,"pith_summary":"The paper establishes the exact extremal edge bound for 2-connected graphs that avoid cycles of length divisible by 4: any such graph on $n$ vertices has at most $\\lfloor (3n-1)/2 \\rfloor$ edges, and for every $n\\ge 12$ there are 2-connected $n$-vertex graphs with exactly that many edges and no forbidden cycle. This adds a new exact value to the small catalogue of extremal numbers for cyclic length conditions, and it sharpens the general 0-mod-4 bound of $\\lfloor 19(n-1)/12 \\rfloor$ within the 2-connected class, where the known extremal examples fail to be 2-connected. The proof turns a global cycle-avoidance condition into a planar face-counting argument, with the hard work concentrated in a structural classification of what can sit on the two sides of any 2-vertex cut.","feed_headline":"Two-connected graphs dodging 0 mod 4 cycles top out at (3n-1)/2 edges","feed_subtitle":"Bound is tight for every n ≥ 12, making (3n-1)/2 the exact edge maximum for 2-connected graphs.","key_machinery":"The load-bearing object is the $L$-type classification: for a specified pair $(x,y)$, the pair is $L$-type when every $(x,y)$-path has length congruent modulo 4 to an element of $L$. Proposition 2.3 classifies all small graphs (up to $n=9$) of the four relevant two-element types, giving sharp edge bounds and identifying the extremal members up to reversal, and this classification drives the structural lemmas that force each side of a 2-vertex cut to be $K_3$, $F_3$, or $F_4$. Around it stand the parallel-sum operation for gluing graphs at two identified vertices, reversing-equivalence for swapping the two sides of a cut, and the gap function $\\mathrm{gap}(G)=3n-1-2e(G)$ together with gap-reducing sequences that build the tight examples.","core_discovery":"The central claim, Theorem 1.2, is that a 2-connected $n$-vertex graph with no $(0 \\bmod 4)$-cycle has at most $\\lfloor (3n-1)/2 \\rfloor$ edges, and the threshold is tight: a family of constructions yields 2-connected $n$-vertex graphs with exactly $\\lfloor (3n-1)/2 \\rfloor$ edges for every $n\\ge 12$. The upper-bound proof takes a minimal counterexample, invokes the known fact that non-planar graphs already contain a $(0 \\bmod 4)$-cycle so the graph is planar, and then uses Euler's formula after showing there are at most two 3-faces and at most five 5-faces. That face control rests on Lemma 3.2, which says each side of every 2-vertex cut is, up to reversal, one of the tiny graphs $K_3$, $F_3$, or $F_4$; this is obtained from a classification of small graphs by their $(x,y)$-path-length types. The lower-bound side is a gap-function construction: operations that attach the small gadgets $F_3,F_4,F_6,F_7,F_8,F_9,P_4$, or $K_3$ along specified path-length types systematically reduce the gap $3n-1-2e(G)$, generating infinitely many tight examples.","pith_inferences":["The gap-reducing gadget machinery is a template that could plausibly transfer to other residue classes, such as cycles of length 1 or 2 mod 4, where the analogous 2-connected extremal numbers are not known.","The reliance on Proposition 2.3 means the theorem currently rests on an uncompleted case check; an independent certified exhaustive verification of the $n\\le 9$ classification would turn a sketch plus code into a checkable proof.","The sharp contrast with the general $\\lfloor 19(n-1)/12 \\rfloor$ extremal graphs suggests that cut vertices are not incidental in the general construction: forcing 2-connectivity lowers the density to $3/2$, so a useful avenue is to study which block decompositions can realize the general bound."],"forward_implications":["For $n\\ge 12$, the maximum number of edges in a 2-connected $n$-vertex graph with no cycle whose length is divisible by 4 is exactly $\\lfloor (3n-1)/2 \\rfloor$.","Because $19/12$ exceeds $3/2$, the new bound is strictly stronger than the general 0-mod-4 bound for all sufficiently large $n$.","Every graph meeting the bound must be planar, since non-planar graphs already contain a 0-mod-4 cycle.","Extremal graphs exist for every $n\\ge 12$ and can be generated in infinite families by gap-reducing sequences starting from a 5-cycle.","In any sufficiently large extremal example for the general $\\lfloor 19(n-1)/12 \\rfloor$ bound, every block must be small, since a large 2-connected block would violate the new bound."],"supporting_citations":[{"why":"Supplies the general $\\lfloor 19(n-1)/12 \\rfloor$ bound and the imported lemmas (even theta graphs, non-planar graphs contain 0 mod 4 cycles, bipartite edge bound, odd-cycle interaction rules) on which the proof is built.","marker":"[9]"},{"why":"Supplies Theorem 2.4, that every 3-connected graph contains a 0 mod 4 cycle, which forces the minimal counterexample to have a 2-vertex cut.","marker":"[5]"},{"why":"Menger's theorem, quoted as Theorem 2.1, provides the vertex-disjoint paths through 2-vertex cuts that the component-structure lemmas repeatedly use.","marker":"[11]"}],"fun_headline_variants":["Tight bound for 2-connected graphs avoiding 0 mod 4 cycles","2-connected graphs without 0 mod 4 cycles have at most (3n-1)/2 edges","Exact edge maximum for 2-connected graphs free of 0 mod 4 cycles","Max edges for 2-connected graphs with no 0 mod 4 cycles: floor((3n-1)/2)","2-connected graphs dodge 0 mod 4 cycles, max edges (3n-1)/2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on Proposition 2.3, a classification of small graphs with prescribed $(x,y)$-path-length types, and that classification is only sketched in the appendix with several cases deferred to an unverified computer check; if any of those small cases is wrong, the structural lemmas and the main theorem collapse.","fun_headline_variants_meta":{"raw":{"variants":["Tight bound for 2-connected graphs avoiding 0 mod 4 cycles","2-connected graphs without 0 mod 4 cycles have at most (3n-1)/2 edges","Exact edge maximum for 2-connected graphs free of 0 mod 4 cycles","Max edges for 2-connected graphs with no 0 mod 4 cycles: floor((3n-1)/2)","2-connected graphs dodge 0 mod 4 cycles, max edges (3n-1)/2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002451,"raw_usage":{"total_tokens":9523,"prompt_tokens":1160,"completion_tokens":8363,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":776,"completion_tokens_details":{"reasoning_tokens":8239}},"tokens_in":776,"tokens_out":8363,"duration_ms":62177,"temperature":1.0,"reasoning_tokens":8239,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:40:29.945874+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"An exhaustive search over 2-connected graphs on at most, say, 12 vertices, or over all graphs $(H;x,y)$ with $n\\le 9$, would settle the classification: the theorem is false if any 2-connected $n$-vertex graph without a $(0 \\bmod 4)$-cycle has more than $\\lfloor (3n-1)/2 \\rfloor$ edges, and Proposition 2.3 is false if, for instance, a 7-vertex graph with $(x,y)$ a $\\{2,3\\}$-type has 9 edges or a 9-vertex $\\{2,3\\}$-type graph has 13 edges. Completing the omitted appendix cases by a certified exhaustive check would confirm the supporting classification.","supporting_citations":[{"cited_title":"On graphs without cycles of length 0 modulo 4","cited_arxiv_id":"2312.09999","evidence_quote":"Supplies the general $\\lfloor 19(n-1)/12 \\rfloor$ bound and the imported lemmas (even theta graphs, non-planar graphs contain 0 mod 4 cycles, bipartite edge bound, odd-cycle interaction rules) on which the proof is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 2.4, that every 3-connected graph contains a 0 mod 4 cycle, which forces the minimal counterexample to have a 2-vertex cut."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Menger's theorem, quoted as Theorem 2.1, provides the vertex-disjoint paths through 2-vertex cuts that the component-structure lemmas repeatedly use."}],"review_version":1}