Pith. sign in

REVIEW 5 minor 15 references

Dense graphs with large odd girth must map homomorphically onto a Möbius ladder.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

Every n-vertex graph with odd girth at least 2k+1 and minimum degree greater than 4n/(6k−1) is homomorphic to the Möbius ladder M_{4k}.

T0 review reviewed 2026-07-11 challenge →

load-bearing objection Solid resolution of Messuti–Schacht’s question: the 4n/(6k−1) threshold forces Hom(G,M_{4k}) for odd girth ≥2k+1, with matching extremal construction.

arxiv 2607.04323 v1 pith:QNGORMMF submitted 2026-07-05 math.CO

On the structure of dense graphs with given odd girth

Xingyan Lu , Shipeng Wang This is my paper
classification math.CO MSC 05C1505C3805C35
keywords homomorphismodd girthMöbius ladderminimum degreegraph homomorphism thresholdmaximal graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The paper proves that any n-vertex graph whose shortest odd cycle is at least 2k+1 long and whose minimum degree exceeds 4n/(6k-1) admits a homomorphism into the Möbius ladder on 4k vertices. Earlier density thresholds already forced such graphs to be bipartite or to map onto an odd cycle; the new bound sits between those thresholds and forces a richer but still fixed target. The result settles an open question about whether the next natural target after the cycle is the Möbius ladder, and it recovers known special cases for small girth. A sympathetic reader cares because the statement gives a precise structural description of all sufficiently dense graphs that avoid short odd cycles: they are essentially blow-ups of one fixed ladder graph.

Core claim

For every integer k at least 2, every n-vertex graph of odd girth at least 2k+1 and minimum degree strictly larger than 4n/(6k-1) is homomorphic to the Möbius ladder M_{4k} obtained from a 4k-cycle by adding all diameters. The same degree bound is conjectured to be optimal, witnessed by certain blow-ups of (6k-1)-cycles with selected chords.

What carries the argument

The argument expands two families of forbidden configurations—diagonal Φ_{4k,1}/Φ_{4k,3} subgraphs and (2k+1)-tetrahedra with long spokes—until each forces an induced copy of M_{4k}; maximality then lets missing edges be completed by controlled even paths that generate these configurations.

Load-bearing premise

The graphs are assumed maximal: every missing edge can be completed by an even path of length exactly 2k-2 that creates a (2k+1)-cycle, and the whole proof relies on the existence of those paths.

What would settle it

Exhibit a single n-vertex graph of odd girth at least 2k+1, minimum degree greater than 4n/(6k-1), that admits no homomorphism into M_{4k} (for example a suitable blow-up of a tetrahedron or of the conjectured extremal (6k-1)-cycle with chords).

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any graph meeting the degree and girth hypotheses is 3-colourable, since M_{4k} is 3-colourable.
  • The earlier cycle-homomorphism threshold is improved: the same graphs map onto the richer fixed target M_{4k} rather than merely C_{2k+1}.
  • When the minimum degree exceeds 4n/(6k-1) the only maximal examples are blow-ups of M_{4k} itself.
  • The bound specialises for k=2 and k=3 to previously known statements about triangle-free and {C3,C5}-free graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the conjectured extremal blow-ups of chordal (6k-1)-cycles can be shown to have homomorphism number strictly larger than that of M_{4k}, the degree threshold is sharp.
  • The same configuration-expansion technique may push the threshold lower still, toward the open question of whether degree n/(2k-2) already forces a homomorphism into some generalised Andrásfai graph F_{ℓ,k}.
  • A computer search for small-k counter-examples just below the bound would quickly test whether maximality can be relaxed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves that every n-vertex graph G with odd girth at least 2k+1 and minimum degree δ(G) > 4n/(6k-1) is homomorphic to the Möbius ladder M_{4k}. This strengthens the Andrásfai–Erdős–Sós theorem (homomorphism to K_2 under the weaker bound 2n/(2k+1)) and the Messuti–Schacht theorem (homomorphism to C_{2k+1} under the bound 3n/(4k)), answers a question of Messuti and Schacht, and generalizes the Brandt–Ribe-Baumann result for girth 7. The argument proceeds by maximality reduction to the class G_{n,k}, configuration expansion via diagonal Φ_{4k,1}/Φ_{4k,3} (Lemmas 3.1–3.2) and (2k+1)-tetrahedra in T_1 (Lemmas 4.3–4.4), and a final absorption argument showing that any maximal blow-up of M_{4k} must be the whole graph (Section 5, using forbidden induced Ψ_1/Ψ_2 and degree counting).

Significance. The result sits cleanly in the classical line of Andrásfai–Erdős–Sós, Häggkvist, Jin, Brandt–Ribe-Baumann, Messuti–Schacht and Letzter–Snyder: it supplies the next natural host graph (M_{4k}) under a degree threshold that the authors and Messuti–Schacht already conjectured to be optimal via blow-ups of a (6k-1)-cycle with selected chords. The proof is a self-contained combinatorial case analysis that does not rely on regularity or probabilistic methods; the degree bound is an external hypothesis, the host is a fixed finite graph, and the maximality reduction is standard. The work therefore advances the structural theory of dense graphs of large odd girth and settles an explicit open question.

minor comments (5)
  1. In the definition of F_{ℓ,k} (page 1) the phrase “distance of the form j(2k-1)+1” is slightly ambiguous; a short clarifying sentence or a reference to the standard generalized Andrásfai graph would help.
  2. Lemma 2.1 and Lemma 2.2 are used repeatedly; a one-sentence reminder of their conclusions at the first major application (e.g., in the proof of Lemma 3.1) would improve readability.
  3. Figure 1 labels M_{4k} and Φ_{4k,3}; the same style of labelling for the tetrahedron configurations in Section 4 would make the case distinctions easier to follow.
  4. In Section 5 the graphs Ψ_1 and Ψ_2 are introduced without a forward reference; a brief sentence explaining that they are the only remaining forbidden configurations needed for the blow-up maximality argument would clarify the logical flow.
  5. A few minor typos appear (e.g., “aÿirmative”, “consequenty”, occasional missing articles); a careful copy-edit pass is recommended.

Circularity Check

0 steps flagged

No circularity: self-contained combinatorial configuration-chasing proof under an external degree hypothesis, with one independent black-box lemma.

full rationale

The derivation of Theorem 1.2 proceeds by maximality reduction (standard for free graphs: non-edges completed by controlled-length even paths creating (2k+1)-cycles), followed by exhaustive case analysis on forbidden configurations (diagonal Φ4k,1 forcing Φ4k,3 forcing induced M4k via Lemmas 3.1–3.2 and Corollaries; T1-tetrahedra forcing length-one spokes forcing M4k via Lemmas 4.3–4.4; induced C6,1 likewise; and the final blow-up maximality argument in §5 using degree counting and Ψ1/Ψ2-freeness). All steps are internal to the odd-girth and minimum-degree hypotheses. The sole external input is Lemma 5.2 (if no induced C6,1 and no T1-tetrahedron then homomorphic to C2k+1), taken verbatim from Messuti–Schacht [15] as an independent black box; the authors have no overlap with that work, and the lemma is not used to smuggle an ansatz or uniqueness claim. The target host M4k is a fixed finite graph independent of G, and the degree threshold 4n/(6k−1) is an unfitted external hypothesis (conjectured optimal by the same external source). No self-definitional loop, fitted parameter renamed as prediction, load-bearing self-citation, imported uniqueness, smuggled ansatz, or renaming of a known empirical pattern appears.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 1 invented entities

Pure extremal graph theory. No free parameters or physical constants. Background axioms are standard graph-theoretic definitions plus the maximality convention common to the AES literature. The only external non-trivial black box is Lemma 5.2 of Messuti–Schacht (homomorphism to C_{2k+1} when neither induced C_{6,1} nor T_1-tetrahedron is present). Configurations Φ and T are proof devices, not postulated entities.

axioms (3)
  • domain assumption A graph is maximal {C_3,…,C_{2k−1}}-free if adding any missing edge creates an odd cycle of length ≤2k−1; such graphs always contain even paths of length exactly 2k−2 between non-adjacent vertices that would close short odd cycles.
    Used throughout §§3–5 (especially Lemmas 3.4, 4.1 and the construction of P_{v1v2k+1}, P_{a0a3}, etc.) to force the existence of the paths that build Φ_{4k,3} and the tetrahedra.
  • domain assumption Lemma 5.2 (Messuti–Schacht): a maximal odd-girth-(≥2k+1) graph containing neither an induced C_{6,1} nor a tetrahedron in T_1 is homomorphic to C_{2k+1}.
    Invoked at the start of the proof of Theorem 1.2 to reduce to the case that one of those two configurations is present.
  • standard math Standard definitions of graph homomorphism, odd girth, distance, symmetric difference of edge sets, and the Möbius ladder M_r.
    Background language of the entire paper.
invented entities (1)
  • Diagonal Φ_{4k,1} / Φ_{4k,3} configurations and (2k+1)-tetrahedra T_ℓa,ℓb,ℓc (T_1,T_2) independent evidence
    purpose: Intermediate forbidden/forced subgraphs that expand, under the degree hypothesis, into an induced copy of M_{4k}.
    Defined in §§3–4 purely as combinatorial tools; they are not new physical or abstract objects beyond ordinary graphs.

reviewed 2026-07-11 · how reviews work

0 comments
Cite this review

Pith. "Pith review of On the structure of dense graphs with given odd girth." pith.science (2026). https://pith.science/paper/QNGORMMF

@misc{pith2026260704323,
  author       = {Pith},
  title        = {Pith review of: On the structure of dense graphs with given odd girth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QNGORMMF}},
  note         = {Machine review of arXiv:2607.04323}
}
Share X Bluesky LinkedIn Reddit HN
abstract

A classical theorem of Andr\'asfai, Erd\H{o}s, and S\'os states that every $n$-vertex graph $G$ with odd girth at least $2k+1$ and minimum degree $\delta(G)>\frac{2n}{2k+1}$ is bipartite (i.e., homomorphic to $K_2$). Messuti and Schacht proved that the same odd girth condition with $\delta(G)>\frac{3n}{4k}$ forces a homomorphism to $C_{2k+1}$. In this paper, we strengthen the above results by showing that every $n$-vertex graph $G$ with odd girth at least $2k+1$ and minimum degree $\delta(G)>\frac{4n}{6k-1}$ is homomorphic to the M\"obius ladder on $4k$ vertices. This answers a question of Messuti and Schacht and generalizes a result of Brandt and Ribe-Baumann.

Figures

Figures reproduced from arXiv: 2607.04323 by Shipeng Wang, Xingyan Lu.

Figure 1
Figure 1. Figure 1: Möbius ladder M4k and its spanning subgraph Φ4k,3 We call a {C3, C5, . . . , C2k−1}-free graph G, i.e., G has odd girth at least 2k + 1, is maximal if adding any edge to G yields an odd cycle of length at most 2k −1. For integers k ≥ 2 and n, we denote by Gn,k the set of all maximal n-vertex graphs which satisfy the 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The proof of Lemma 3.1 Claim 1. For any vertex x in G, it holds that |N(x) ∩ V (H′ )| ≤ 4. Proof. Suppose not, and let x be a vertex in G such that |N(x) ∩ V (H′ )| ≥ 5. Note that V (H′ ) = V (C ′ ) ∪ V (H). Since x has at most two neighbors in C ′ , it must have at least three other neighbors in H. Because H is a diagonal Φ4k,1, x has exactly three neighbors in H. This implies that x has exactly five neig… view at source ↗
Figure 3
Figure 3. Figure 3: The proof of Claim 4 Note that the three paths v0v1 . . . vj−1xvj+1vj+2 . . . v2k, v0v2k and v0v4k−1v4k−2 . . . v2k form a (2k + 1)-Theta graph Θ. Clearly, P1, P2 are the two (x, v2k+r)-outer paths, and P3, P4 are the two (x, v2k+r)-intersecting paths in Θ. By Lemma 2.2, we have that ei￾ther the cycles xP1v2k+rx and xP2v2k+rx both have length 2k + 1, or one of the cycles xP3v2k+rx, xP4v2k+rx has length 2k … view at source ↗
Figure 4
Figure 4. Figure 4: H′ = H ∪ {uv2, uv0, uv4k−2} Claim 5. For any vertex x in G, if x has at least one neighbor on P, then |N(x)∩V (H′ )| ≤ 3. Proof. Suppose not, and let |N(x) ∩ V (H′ )| ≥ 4. Recall that every vertex in G has at most three neighbors in C. Hence x has exactly three neighbors, say y1, y2, y3, in C, and u is another neighbor of x. By the choice of x, one of y1, y2, y3 lies on P. Since the vertices on D1 at dista… view at source ↗
Figure 5
Figure 5. Figure 5: T ∪ {xy1, xy2, xy3} So, the cycle D1 has length 2k+3 and the cycle D2 has length 2k+1, which implies that ℓ(P3) = 2k + 2 and ℓ(P4) = 2k. If ℓ(zPbzy2) = 1, i.e., zy2 ∈ E(G), then ℓ(Cac[z, a, y3]) = ℓ(D2) − ℓ(zy2xy3) = 2k − 2. Since y3 ∈ S2, it follows that the sub-path y3Pacc of Pac has length at least two. Recall that the path Pcz has length at least two. Therefore ℓ(Cac[z, c, y3]) = ℓ(y3Pacc) + ℓc ≥ 4. Bu… view at source ↗
Figure 6
Figure 6. Figure 6: T ∪ {xy1, xy2, xy3} So, we have y = b. Without loss of generality, we may assume that y1 and y2 are on the paths Pab − {a, b} and Pbz − {b, z}, respectively. Thus, y3 is on the path Cac[z, c, a]. We distinguish the following two cases. Case 1. y3 is on the path Pcz − {z}. Since y2, y3 are in the cycle Cbc, it follows that distCbc (y2, y3) = 2, which implies that either y2, y3 ∈ N(z), or y3 = c and ℓ(Pbc) =… view at source ↗
Figure 7
Figure 7. Figure 7: T ∪ {xy1, xy2, xy3} Now suppose that the cycle xP4y3x, denoted by D, has length 2k + 1, as shown in Figure 7b. Then replacing Cab by D in T yields a tetrahedron T2 ∈ Tk with center vertex z and branch vertices y2, y3, c. Note that the spoke Pcz of length at least two in T is also a spoke of T2, and another spoke Cac[z, a, y3] of T2 has length at least two. By Lemma 4.3, the other spoke zPbzy2 of T2 has len… view at source ↗
Figure 8
Figure 8. Figure 8: Graphs Ψi , Ψ Lemma 5.1. If G ∈ Gn,k, then G contains no induced copy of Ψ1 or Ψ2. Proof. Suppose, to the contrary, that G contains an induced copy H (say) of Ψ1 or Ψ2, labeled as shown in Figure 8a. Note that a1a6, a2a5, a0a7 ∈/ E(G) and distH(a1, a6) = distH(a2, a5) = distH(a0, a7) = 3. Since G is a maximal {C3, . . . , C2k−1}-free graph, it follows that there exist three (a1, a6),(a2, a5),(a0, a7)-paths… view at source ↗
Figure 9
Figure 9. Figure 9: Ψ On the other hand, let C ′ := a2Pa2a5 a5a4a1Pa1a6 a6a3a2 be a cycle of length 4k in Ψ shown in Figure 9b. Clearly, C ′ ∪ {a1a2, a3a4, a5a6} is a copy of Φ4k,3 with rim cycle C ′ . By Lemma 3.2, G[V (C ′ )] is also a copy of M4k, which implies that C ′ contains y4, y5, and at most one of y1, y2, y3. Since V (C ′ ) = V (D) ∪ V (Pa2a5 ) and y4, y5 ∈ V (Pa2a5 ), it follows that D contains at most one of y1, … view at source ↗
Figure 10
Figure 10. Figure 10: T ∪ {v2kv2k+1} Claim 16. We have a = v1, c = v4k−1, b = x. Consequently, the spokes of T are v0v1, v0v4k−1, v0v2kx. Proof. By Claim 15, we have D1 ∩ D2 = v0v1, and hence a = v1 because a is the branch vertex lying on the spoke D1 ∩ D2 in T. Note that the rim cycle of T is C := bPxv1 v1v2k+1v2k+2 . . . cPxv4k−1 b and the spokes of T are the edge v0v1 and the paths v0v2kxPxv1 b, v0v4k−1v4k−2 . . . c, as sho… view at source ↗
Figure 11
Figure 11. Figure 11: T ∪ {yz1, yz2, yz3, v2k+1v2k+1} So, z1, z2 are on the path v2k+1v2k+2 . . . v4k−1, say z1 = vj and z2 = vj+2 for some j ∈ {2k + 1, . . . , 4k − 3}. Note that y has at most two neighbors in an odd cycle of length 2k + 1 by the odd girth assumption. Since the odd cycles v0v2kv2k+1 . . . v4k−1v0 and D1 both have length 2k + 1 and these two odd cycles contain both z1, z2, it follows that z3 is on the path Pxv… view at source ↗
Figure 12
Figure 12. Figure 12: The proof of Case 2 Recall that G[V (C)] is an induced copy of M4k, and let vtv be the diagonal chord in this M4k. Since D2 and Cxvt are two odd cycles of length 2k + 1, it follows that vvt cannot be the chord in these two odd cycles, which implies that v is on the path Pxvs − {x}. Let D′ 2 := vtvPxv4k−2 v4k−2v4k−1v0v2k . . . vt and D := vtPxvtxPxvs vvt be two odd cycles of G[V (C)]. Since vvt is a diagon… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 1 linked inside Pith

  1. [1]

    Andrásfai, P

    B. Andrásfai, P. Erdős, and V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218

    1974

  2. [2]

    Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol

    B. Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998

    1998

  3. [3]

    J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008

    2008

  4. [4]

    Bottcher, N

    J. Bottcher, N. Frankl, D. Cecchelli, O. Parzcyk and J. Skokan, Graphs with large minimum degree and no small odd cycles are 3-colourable, arXiv: 2302.01875v1 (2023)

    Pith/arXiv arXiv 2023

  5. [5]

    Brandt and E

    S. Brandt and E. Ribe-Baumann, Graphs of odd girth 7 with large degree, Electron. Notes in Discrete Math. 34 (2009), 89-93

    2009

  6. [6]

    C. C. Chen, G. P. Jin, and K. M. Koh, Triangle-free graphs with large degree, Combin. Probab. Comput. 6 (1997), 381–396

    1997

  7. [7]

    Ebsen and M

    O. Ebsen and M. Schacht, Homomorphism thresholds for odd cycles, Combinatorica 40 (2020), 39-62

    2020

  8. [8]

    R. K. Guy and F. Harary, On the Möbius ladders, Canad. Math. Bull. 10 (1967), 493–496

    1967

  9. [9]

    Häggkvist, Odd cycles of specified length in non-bipartite graphs, Graph theory (Cambridge, 1981), North-Holland Math

    R. Häggkvist, Odd cycles of specified length in non-bipartite graphs, Graph theory (Cambridge, 1981), North-Holland Math. Stud., vol. 62, North-Holland, Amsterdam- New York, 1982, pp. 89–99

    1981

  10. [10]

    Häggkvist and G

    R. Häggkvist and G. P. Jin, Graphs with odd girth at least seven and high minimum degree, Graphs Combin. 14 (1998), 351–362

    1998

  11. [11]

    G. P. Jin, Triangle-free four-chromatic graphs, Discrete Math. 145 (1995), 151-170. 32

    1995

  12. [12]

    G. P. Jin, Triangle-free graphs with high minimal degrees, Combin. Probab. Comput. 2 (1993), no. 4, 479-490

    1993

  13. [13]

    Letzter and R

    S. Letzter and R. Snyder, The homomorphism threshold of {C3, C5}‐free graphs, J. Graph Theory 90 (2019), 83-106

    2019

  14. [14]

    Łuczak, On the structure of triangle-free graphs of large minimum degree, Com- binatorica 26 (2006), 39-62

    T. Łuczak, On the structure of triangle-free graphs of large minimum degree, Com- binatorica 26 (2006), 39-62

    2006

  15. [15]

    Messuti and M

    S. Messuti and M. Schacht, On the structure of graphs with given odd girth and large minimum degree, J. Graph Theory 80 (2015), 69-81. 33

    2015

This paper was first reviewed by grok-4.5 on July 11, 2026.