Pith. sign in

REVIEW 3 major objections 3 minor 13 references

On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$

T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every n-vertex graph with no cycle of length 0, 3, or 4 modulo 6 has at most (11n − 14)/8 edges, and this bound is sharp.

desk verdict Real main theorem, but the all-n construction in Section 6 has a sign error that invalidates Corollary 1.4 as written; the fix is one line, so the paper is revisable. read the letter →

arxiv 2608.06698 v1 pith:5ISVCRRA submitted 2026-08-07 math.CO

Takahiro Ueoro This is my paper · ORCID
classification math.CO MSC 05C3505C3805C10
keywords extremalgraphtheoryforbiddencyclelengthscyclesmodulo6planargraphsexactnumbertheta-4edgebounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes the exact maximum number of edges in an $n$-vertex graph that contains no cycle whose length is divisible by $3$ or congruent to $4$ modulo $6$, that is, no cycle of length $0$, $3$, or $4$ modulo $6$. The answer is $\left\lfloor \frac{11}{8}n - \frac{7}{4} \right\rfloor$ edges for every $n \ge 2$. Equality is achieved only when $n = 8k+2$ and the graph is isomorphic to the explicitly constructed graph $H_k$, so all extremal graphs are classified. A central step is the proof that every such graph must be planar, which turns the extremal problem into a face-counting problem. The result shows that forbidding the three residue classes simultaneously forces a strictly smaller edge density, with slope $11/8$, than forbidding any two of them, whose known lower bounds have slope $3/2$.

What carries the argument

The proof runs on four structural reductions. First, planarity: Lemma 4.2 shows every subdivision of $K_5$ contains a cycle of length $0 \bmod 3$, and Lemma 4.3 shows every subdivision of $K_{3,3}$ contains a cycle of length $0$ or $4 \bmod 6$ by a $3\times 3$ matrix congruence argument; Kuratowski's theorem then forces every $(0,3,4 \bmod 6)$-cycle-free graph to be planar. Second, Lemma 3.1: an $8$-angulation whose dual is bipartite, with girth $8$ and no $10$- or $12$-cycles, must be a $\theta_4$-graph, meaning several internally disjoint paths of length $4$ sharing the same pair of endpoints. Third, a face-counting inequality, $3f_5 + f_7 \le \frac{2}{11}e + \frac{64}{11}$, obtained from the structure of the $5$-faces and $7$-face blocks. Fourth, Euler's formula converts that inequality into $e \le \frac{11}{8}n - \frac{7}{4}$. Equality forces the graph to decompose into a $\theta_4$-graph plus antipodal paths, and the cycle restrictions then identify the extremal graph as $H_k$.

What would settle it

Enumerate all $3\times 3$ matrices over $\mathbb{Z}/6\mathbb{Z}$ with entries in $\{1,2,3,5\}$, even row and column sums, and with $b_{\mathrm{sum}} + T_\sigma \in \{1,3,4,5\}$ for every permutation $\sigma$; Lemma 4.3 claims every such matrix is one of three displayed patterns. If a single matrix outside those patterns exists, it yields a $K_{3,3}$ subdivision with no $(0,3,4 \bmod 6)$-cycle, refuting the planarity proposition and the bound. Equivalently, exhibit one such subdivision explicitly.

Watch

Extended reading notes

Core claim

The paper's central claim is a sharp edge bound: every $n$-vertex graph $G$ with no $(0,3,4 \bmod 6)$-cycle satisfies $e(G) \le \frac{11}{8}n - \frac{7}{4}$, with equality exactly when $n = 8k+2$ and $G$ is isomorphic to the explicit graph $H_k$. The graph $H_k$ is built by taking $k$ copies of a fixed eight-vertex gadget, identifying the two marked vertices of every copy into a single pair, and adding one edge between them; every cycle of $H_k$ has length $5$, $7$, $8$, $11$, or $14$. The proof shows such graphs are planar, then bounds edges through Euler's formula and a detailed census of face lengths, and finally uses a structural lemma on $8$-angulations to identify the equality case. The paper also supplies, for every $n \ge 2$, a graph attaining $\left\lfloor \frac{11}{8}n - \frac{7}{4} \right\rfloor$ edges, so the extremal number is exact with no exceptional $n$.

Load-bearing premise

The proof depends on the claim that no matter how the nine edges of the complete bipartite graph $K_{3,3}$ are subdivided into paths, some resulting cycle has length $0$ or $4$ modulo $6$; the three-case matrix argument verifying this is asserted rather than shown in full, and a missing case would remove the planarity step and invalidate the edge bound.

Editorial extensions

If this is right

  • For every $n \ge 2$, the extremal number is exactly $\left\lfloor \frac{11}{8}n - \frac{7}{4} \right\rfloor$, so the upper bound is always attainable and there are no exceptional values of $n$.
  • Equality in the bound is fully classified: it occurs only for $n = 8k+2$ and forces $G \cong H_k$, giving a complete list of extremal graphs.
  • Every graph avoiding $(0,3,4 \bmod 6)$-cycles is planar, so the forbidden cycle lengths impose a topological restriction that can be exploited in other arguments.
  • Forbidding all three residue classes together is strictly stronger than forbidding any two of them, since the known lower-bound constructions for pairs have slope $3/2$, larger than $11/8$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is to apply the same planarity-plus-face-counting template to the pairs $(0,4 \bmod 6)$ and $(3,4 \bmod 6)$, whose exact extremal numbers the paper leaves open; the slope-$3/2$ lower bounds suggest their true coefficients may be $3/2$ or a nearby rational.
  • The matrix-congruence argument that rules out $K_{3,3}$ subdivisions is purely algebraic and may generalize to $K_{3,t}$ or to other residue pairs, potentially yielding a systematic planarity criterion for multi-residue cycle bans.
  • Because the equality graph $H_k$ is a chain of $k$ internally disjoint length-$4$ paths between two poles with alternating antipodal chords, varying the common path length or the chord lengths gives natural candidate extremal graphs for neighbouring residue problems.
  • If the rigid face structure of the equality case, with only $5$-, $7$-, and $8$-faces, is typical, then exact bounds for other multi-residue bans might be provable by classifying which near-$8$-angulations admit no forbidden cycle, a finite check for each residue set.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies n-vertex graphs containing no cycle of length divisible by 3 or congruent to 4 modulo 6, i.e., no (0,3,4 mod 6)-cycle. The main theorem states that every such graph satisfies e(G) ≤ (11/8)n − 7/4, with equality if and only if n = 8k+2 and G is isomorphic to an explicitly constructed graph H_k; Corollary 1.4 then asserts the exact extremal number floor((11/8)n − 7/4) for every n ≥ 2. The proof proceeds by showing planarity via exclusion of K_5 and K_{3,3} subdivisions, then uses face-counting, a structural lemma on 8-angulations, and induction on n to derive the bound and the extremal characterization. The paper also gives an all-n construction intended to attain the bound.

Significance. If correct, this is a valuable exact extremal result for simultaneously forbidden residue classes of cycle lengths, with a full characterization of all extremal graphs. The proof is self-contained and uses standard tools (Kuratowski, Euler's formula, Menger-type arguments, Ramsey theory), and the extremal constructions are explicit rather than asymptotic. The paper also demonstrates a genuinely new phenomenon: the coefficient 11/8 is smaller than the leading coefficients obtained by forbidding any two of the three residue classes separately. The main claims are falsifiable and the constructions are explicit, which is a strength.

major comments (3)
  1. [Section 6, proof of Corollary 1.4] The definition k = floor((n−2)/8) makes r = 8k+2−n negative for n ≡ 3,4,...,9 (mod 8); for example, n = 3 gives k = 0 and r = −1, so the expression H_k − {v_1,...,v_r} is undefined and the lower-bound construction for every n is not established as written. This is load-bearing because Corollary 1.4 and the abstract's 'for every n ≥ 2' claim depend on it. The intended definition appears to be k = ceil((n−2)/8), equivalently k = floor((n+5)/8), which gives 0 ≤ r ≤ 7 and, as the author states, the claimed edge count. Please correct the formula and verify the edge count for all r = 0,...,7.
  2. [Lemma 4.3] The reduction 'By considering the parity of the entries of B together with the symmetry of K_{3,3}, it suffices to examine only the following cases' is asserted rather than demonstrated. Since Proposition 4.1 depends entirely on this lemma, the parity classification should be justified explicitly: after row and column permutations, every 3×3 parity pattern with even row and column sums is indeed one of the three displayed cases, but the argument should be written out or replaced by a short enumeration. As written, a reader cannot fully verify the exhaustiveness of the case analysis.
  3. [Section 5, final paragraph of proof of Theorem 1.3] The assertion 'If end(R) ≠ {x,y}, then it is easy to check that G contains a (0,3,4 mod 6)-cycle' is the last step in the extremal classification and is not demonstrated. Since this completes the proof that G is isomorphic to H_k, please provide the short case analysis: for each of the three non-{x,y} antipodal pairs of the 8-face P_{2k} ∪ P_1, exhibit an explicit forbidden cycle using the paths Q_i already constructed.
minor comments (3)
  1. [Lemma 4.3, Case 2] The displayed congruence 'b_sum + T_id = 12 + 2b_{2,2} + 2b_{3,3} + b_{2,3} + b_{3,2} ≡ 12 + 3d ≡ 0' contains an arithmetic slip: the constant 2 from T_id = 2 + d is omitted, and the correct value is 14 + 3d ≡ 2 (mod 6). Since 2 is not in {1,3,4,5} (mod 6), the contradiction with equation (3) is still valid, but the formula should be corrected.
  2. [Introduction] There are several typographical and notational slips in the introduction, e.g., the display comparing ex(k,C_ℓ)/k with c_{ℓ,k} is missing the modulus in the cycle notation, and the intended statement should be about ex(n,C_{ℓ mod k})/n. Please proofread the introduction carefully.
  3. [Definition 5.5] The face counts e(B_1) = 7 and e(B_2) = 11 are used immediately after the definition but are not stated there; adding them to Definition 5.5 would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained and independent; Section 6 has a non-circular lower-bound indexing typo.

full rationale

The derivation chain is self-contained and does not reduce any claimed result to its inputs. The upper bound in Theorem 1.3 is obtained by induction on n, using planarity from Proposition 4.1, which rests on Lemmas 4.2 and 4.3 plus Kuratowski's theorem; those planarity lemmas are standalone cycle-length arguments and do not invoke the main theorem or any fitted quantity. Section 3's Lemma 3.1 is an independent structural statement about 8-angulations, proved from Euler-type counts and a dual-bipartite argument. The equality case is characterized by face-count identities and structural reconstruction from Lemma 5.8, not by assuming H_k. The lower bound uses the explicitly defined graphs H_k; Section 6 contains an indexing error, since setting k = floor((n-2)/8) makes r = 8k+2-n negative for n not congruent to 2 modulo 8, e.g., n=3, but this is a correctness or typo issue in the construction and not a circular step. No parameter is fitted to data, no prediction is defined as its own input, and there are no load-bearing self-citations: the reference list contains no work by the present author. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proof introduces no new objects beyond the explicit graph family H_k; all relied-upon background facts are standard theorems. There are no fitted constants or ad hoc assumptions.

assumptions (6)
  • standard math Kuratowski's theorem: a graph is planar iff it contains no subdivision of K5 or K3,3.
    Used in the proof of Proposition 4.1 to conclude planarity from Lemmas 4.2 and 4.3.
  • standard math Euler's formula V - E + F = 2 for connected plane graphs.
    Used in Section 5 for the face-counting inequality (2e = sum of face lengths and Euler's formula).
  • standard math Menger's theorem on vertex-disjoint paths in 2-connected graphs.
    Used in Claim 5.2.1 to find two vertex-disjoint paths between two 5-faces.
  • standard math Ramsey's theorem R(3,3)=6 for edge-colorings of K5.
    Used in Lemma 4.2 to force a monochromatic triangle in a 2-coloring, or the 5-cycle structure.
  • standard math In a 2-connected plane graph, every face is bounded by a cycle.
    Used in Section 5 to treat every face as a cycle for face-length counting.
  • domain assumption All graphs are simple.
    Stated in Section 2; the entire proof relies on the simple-graph convention.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$." pith.science (2026). https://pith.science/paper/5ISVCRRA

@misc{pith2026260806698,
  author       = {Pith},
  title        = {Pith review of: On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5ISVCRRA}},
  note         = {Machine review of arXiv:2608.06698}
}
abstract

We study graphs containing no cycle whose length is divisible by $3$ or congruent to $4$ modulo $6$. We prove that every such $n$-vertex graph $G$, where $n \ge 2$, satisfies $e(G) \le (11/8)n-7/4$. Moreover, equality holds if and only if $n=8k+2$ for some nonnegative integer $k$ and $G$ is isomorphic to the explicitly constructed graph $H_k$. We also construct, for every $n\geq2$, an $n$-vertex graph with $\left\lfloor (11/8)n-7/4 \right\rfloor$ edges satisfying the same cycle restriction. Consequently, this is the exact maximum number of edges for every $n \ge 2$.

Figures

Figures reproduced from arXiv: 2608.06698 by the authors.

Figure 1
Figure 1. The graph A (upper right) and the graph Hk (bottom). Remark 1.2. We have |V (Hk)| = 8k + 2 and e(Hk) = 11k + 1. Every cycle of Hk has length in {5, 7, 8, 11, 14}. In particular, Hk contains no (0, 3, 4 mod 6)-cycle. For each positive integer k, every face of Hk is either a 5-face, a 7-face, or an 8-face. The two faces incident with the edge xkyk are both 5-faces, whereas every edge other than xkyk is incident with a… view at source ↗
Figure 2
Figure 2. θ4-graph. In this section, we prove the following lemma, which will be used in the latter part of the proof of the Main Theorem. Lemma 3.1. Let H be an 8-angulation whose dual graph H∗ is bipartite. Suppose that the girth of H is 8, and that H contains no cycles of length 10 or 12. Then H is a θ4-graph. Proof. Since every face of H has even length, H is bipartite. Let fH denote the number of faces of H. If fH ≤ 2, t… view at source ↗
Figure 3
Figure 3. Claim 5.2.1 (1) and (2) Proof. (1) Suppose that C1∩C2 = ∅. Since G is 2-connected, there are two vertex-disjoint (C1, C2)-paths P1, P2. For i = 1, 2, let end(Pi)∩V (C1) = {vi} and end(Pi)∩V (C2) = {wi}, and put l(Pi) = ai . Let d1 = distC1 (v1, v2) and d2 = distC2 (w1, w2). If (d1, d2) = (2, 2), then C1 ∪ C2 ∪ P1 ∪ P2 contains cycles of lengths a1 + a2 + 4, a1 + a2 + 5, and a1 + a2 + 6, one of which is congruent to … view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The 7-faces C1 and C2. Define C ′ 1 := C1[x2, y1] ∪ C2[y1, x2], C′ 2 := C1[y1, x2] ∪ C2[x2, y1]. Then both C ′ 1 and C ′ 2 are cycles in G, and l(C ′ 1 )+l(C ′ 2 ) = l(C1)+l(C2) = 14. Since G contains no (0, 3, 4 mod 6)-cycles, we have l(C ′ 1 ) = l(C ′ 2 ) = 7. Theref…
Figure 5
Figure 5. Figure 5: The plane graphs B1 (left) and B2 (right). Remark 5.6. By Lemma 5.4, every 7-face of G is contained in exactly one 7-face block. Moreover, distinct 7-face blocks are edge-disjoint. Let f denote the number of faces of G, and let e denote the number of edges of G. For ea…
Figure 6
Figure 6. Figure 6: The graph G. and G = G ′ ∪ R ∪ [ k i=1 Qi . See [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages

  1. [1]

    Y. Bai, A. Grzesik, B. Li and M. Prorok, Cycle lengths in graphs of given minimum degree,Journal of Combinatorial Theory, Series B180 (2026), 111–150

    work page 2026

  2. [2]

    Y. Bai, H. Chu, B. Li, B. Park, H. Ryu, On 2-connected graphs without cycles of length 1 modulo 3,arXiv preprint arXiv:2606.02356, 2026

    work page Pith review arXiv 2026

  3. [3]

    Y. Bai, B. Li, Y. Pan and S. Zhang, On graphs without cycles of length 1 modulo 3,arXiv preprint arXiv:2503.03504, 2025

    arXiv 2025

  4. [4]

    Bollob´ as, Cycles modulok,Bulletin of the London Mathematical Society9 (1) (1977), 97–98

    B. Bollob´ as, Cycles modulok,Bulletin of the London Mathematical Society9 (1) (1977), 97–98. 19

    work page 1977

  5. [5]

    Cai and W

    X. Cai and W. E. Shreve, (2 mod 4)-cycles,Ars Combinatoria60 (2001), 97–129

    work page 2001

  6. [6]

    Chen and A

    G. Chen and A. Saito, Graphs with a cycle of length divisible by three,Journal of Combinatorial Theory, Series B60 (2) (1994), 277–292

    work page 1994

  7. [7]

    H. Chu, B. Park, H. Ryu, On 2-connected graphs avoiding cycles of length 0 modulo 4,arXiv preprint arXiv:2507.12798, 2025

    arXiv 2025

  8. [8]

    Erd˝ os, Some recent problems and results in graph theory, combinatorics, and num- ber theory,Proc

    P. Erd˝ os, Some recent problems and results in graph theory, combinatorics, and num- ber theory,Proc. Seventh SE Conf. Combinatorics, Graph Theory and Computing, Utilitas Math(1976), 3–14

    work page 1976

Show all 13 references
  1. [9]

    J. Gao, Q. Huo, C. H. Liu and J. Ma, A unified proof of conjectures on cycle lengths in graphs,International Mathematics Research Notices10 (2022), 7615–7653

    2022

  2. [10]

    J. Gao, B. Li, J. Ma and T. Xie, On two cycles of consecutive even lengths,Journal of Graph Theory106 (2) (2024), 225–238

    2024

  3. [11]

    Gy˝ ori, B

    E. Gy˝ ori, B. Li, N. Salia, C. Tompkins, K. Varga and M. Zhu, On graphs without cycles of length 0 modulo 4,Journal of Combinatorial Theory, Series B176 (2026), 7–29

    2026

  4. [12]

    Simonovits, Extremal graph problems with symmetrical extremal graphs

    M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Addi- tional chromatic conditions.Discrete Mathematics7 (3–4) (1974), 349–376

    1974

  5. [13]

    Sudakov and J

    B. Sudakov and J. Verstra¨ ete, The extremal function for cycles of lengthℓmodk. The Electronic Journal of Combinatorics24 (1) (2017). 20

    2017

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.