pith. sign in

arxiv: 2605.17218 · v1 · pith:3UMPKLYInew · submitted 2026-05-17 · 🧮 math.CO

Induced subdivisions in graphs of large girth

Peiru Kuang , Yan Wang This is my paper

Pith reviewed 2026-05-19 23:35 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords induced subdivisionsgraph girthminimum degreeMader's theoremcomplete graph subdivisionsextremal graph theory
0
0 comments X

The pith

Graphs with minimum degree at least k and girth above a fixed constant contain an induced subdivision of K_{k+1}.

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

The paper establishes that there exists an absolute constant g0 such that for every integer k at least 3, any graph with minimum degree at least k and girth at least g0 contains an induced subdivision of the complete graph on k+1 vertices. This provides a strong affirmative answer to a question originally posed by Shi and later by Kuhn and Osthus about induced subdivisions in high-girth graphs. A sympathetic reader would care because the result shows that girth can be increased to force these specific induced structures to appear uniformly, no matter how large the minimum degree becomes. The argument proceeds by reducing the problem to an auxiliary statement about induced subdivisions in bounded-degree high-girth graphs with high average degree.

Core claim

There exists an absolute constant g0 such that for every integer k greater than or equal to 3, every graph G with minimum degree delta(G) at least k and girth g(G) at least g0 contains an induced subdivision of K_{k+1}. The proof relies on an induced variant of Mader's theorem asserting that for every fixed s, eta, and D, every graph J with maximum degree at most D, average degree greater than s minus 2 plus eta, and sufficiently large girth contains an induced subdivision of K_s.

What carries the argument

The induced variant of Mader's theorem, which guarantees an induced subdivision of a complete graph in any graph of bounded maximum degree, average degree above a linear threshold, and large girth.

If this is right

  • Once girth exceeds the fixed g0, minimum degree k alone suffices to guarantee an induced subdivision of K_{k+1}.
  • The girth threshold g0 works simultaneously for every minimum degree k at least 3.
  • The result strengthens classical subdivision theorems by requiring the subdivision to be induced rather than merely topological.
  • High-girth graphs cannot avoid induced subdivisions of complete graphs when their minimum degree is large.

Where Pith is reading between the lines

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

  • The same reduction technique might extend to induced subdivisions of other fixed graphs beyond complete graphs.
  • Explicit upper bounds on g0 could be pursued by refining the dependence on the parameters in the induced Mader variant.
  • The statement suggests that large girth acts as a uniform forcing condition for induced dense substructures across all degree regimes.

Load-bearing premise

The argument requires that an induced version of Mader's theorem holds for graphs with bounded maximum degree, average degree exceeding s minus 2 plus eta, and sufficiently large girth.

What would settle it

A graph with minimum degree k, girth larger than the claimed g0, and no induced subdivision of K_{k+1} for some k at least 3 would refute the central claim.

Figures

Figures reproduced from arXiv: 2605.17218 by Peiru Kuang, Yan Wang.

Figure 1
Figure 1. Figure 1: Local construction of the path Peλ and the corresponding edge eλ in the auxiliary graph H∗ . Claim 4.4. Let y ∈ S ∗ , z ∈ NJ (y) and let λ, λ′ ∈ Lz(y) be distinct. Then NF (eλ) ∩ NF (eλ′) = {y}. Suppose that w ∈ NF (eλ) ∩ NF (eλ′) \ {y}. For each ξ ∈ {λ, λ′}, there exist a vertex aξ ∈ V (Peξ ) and an aξ-w path Qξ of length at most 2ℓ + 1 whose internal vertices lie in Tw. Let u be the last common vertex of… view at source ↗
read the original abstract

In this paper, we prove that there exists an absolute constant $g_0$ such that, for every integer $k\ge 3$, every graph $G$ with $\delta(G)\ge k$ and $g(G)\ge g_0$ contains an induced subdivision of $K_{k+1}$. This answers, in a strong sense, a problem asked by K\"uhn and Osthus (originally attributed to Shi). A main ingredient in our proof is an induced variant of Mader's theorem: for every fixed \(s,\eta,D\), every graph \(J\) with \(\Delta(J)\le D\), \(d(J)>s-2+\eta\) and sufficiently large girth contains an induced subdivision of \(K_s\).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper proves that there exists an absolute constant g_0 such that for every integer k ≥ 3, every graph G with minimum degree δ(G) ≥ k and girth g(G) ≥ g_0 contains an induced subdivision of K_{k+1}. The proof relies on a new induced variant of Mader's theorem: for every fixed s, η, D, every graph J with Δ(J) ≤ D, average degree d(J) > s-2 + η, and sufficiently large girth contains an induced subdivision of K_s. This is presented as answering a problem of Kühn and Osthus (attributed to Shi) in a strong form.

Significance. If the central claim holds, the result gives a uniform girth threshold independent of k for the existence of induced K_{k+1}-subdivisions in graphs of minimum degree k, which is a substantial strengthening of known results on subdivisions in high-girth graphs. The induced Mader theorem is a potentially reusable tool for studying induced subgraphs in sparse graphs with large girth.

major comments (1)
  1. [Abstract] Abstract: The main theorem asserts a single absolute g_0 independent of k. The induced Mader ingredient is stated only for fixed s, η, D with 'sufficiently large girth' (whose dependence on the fixed parameters is not quantified). To derive the main result, the argument must set s = k+1 and select D, η to accommodate δ(G) ≥ k (likely via some core or auxiliary graph whose parameters grow with k). If the girth threshold implicit in the proof of the induced Mader statement grows with s or D, the resulting g_0 would depend on k, contradicting the claimed uniformity. The manuscript must explicitly confirm that the girth bound remains bounded independently of k or supply the dependence function.
minor comments (1)
  1. [Abstract] The abstract refers to the problem 'originally attributed to Shi' without a citation; a reference should be added for completeness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this important point regarding the uniformity of the girth threshold. We address the comment in detail below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The main theorem asserts a single absolute g_0 independent of k. The induced Mader ingredient is stated only for fixed s, η, D with 'sufficiently large girth' (whose dependence on the fixed parameters is not quantified). To derive the main result, the argument must set s = k+1 and select D, η to accommodate δ(G) ≥ k (likely via some core or auxiliary graph whose parameters grow with k). If the girth threshold implicit in the proof of the induced Mader statement grows with s or D, the resulting g_0 would depend on k, contradicting the claimed uniformity. The manuscript must explicitly confirm that the girth bound remains bounded independently of k or supply the dependence function.

    Authors: We agree that the dependence of the girth threshold on the parameters must be made fully explicit to avoid any ambiguity. In the proof of the induced Mader theorem, the required girth is determined by a probabilistic argument that depends only on η and D (specifically, on ensuring the existence of a suitable expander-like subgraph after deleting low-degree vertices and short cycles); the target clique size s enters only in the final embedding step and does not affect the girth lower bound. Consequently, once η and D are fixed independently of k (which is possible by working in a suitable auxiliary graph derived from the k-core of G), the same absolute girth g_0 suffices for every s = k+1. We will revise the manuscript by (i) adding an explicit sentence to the statement of the induced Mader theorem quantifying the girth bound as a function of η and D only, and (ii) inserting a short paragraph in the proof of the main theorem that records the parameter choices and confirms that g_0 can be chosen independently of k. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper states a theorem asserting an absolute constant g0 independent of k, with the proof relying on a stated induced variant of Mader's theorem for fixed s, η, D and sufficiently large girth. No equations or steps in the abstract reduce a claimed result to a fitted parameter, self-definition, or load-bearing self-citation by construction. The ingredient is presented as an internal component of the argument rather than an external assumption that loops back to the target claim. The derivation chain therefore remains non-circular and self-contained as a mathematical proof.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard graph-theoretic definitions plus the unproven (in the abstract) induced variant of Mader's theorem.

axioms (1)
  • standard math Standard definitions of girth, minimum degree, induced subdivision, and Mader's theorem in graph theory.
    Invoked throughout the abstract as background.

pith-pipeline@v0.9.0 · 5643 in / 1190 out tokens · 31698 ms · 2026-05-19T23:35:39.186918+00:00 · methodology

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

36 extracted references · 36 canonical work pages

  1. [1]

    N. Alon, S. Hoory and N. Linial, The Moore bound for irregular graphs,Graphs Combin.18(2002), no. 1, 53–57. 13

    work page 2002

  2. [2]

    Alon and J

    N. Alon and J. H. Spencer,The Probabilistic Method, Wiley, Hoboken, NJ, 4th ed., 2016

    work page 2016

  3. [3]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason, Proof of a conjecture of Mader, Erd˝ os and Hajnal on topological complete subgraphs,European J. Combin.19(1998), no. 8, 883–887

    work page 1998

  4. [4]

    Buci´ c and R

    M. Buci´ c and R. Montgomery, Towards the Erd˝ os–Gallai cycle decomposition conjec- ture,Adv. Math.437(2024), Paper No. 109434

    work page 2024

  5. [5]

    Catlin, Haj´ os’ graph-coloring conjecture: variations and counterexamples,J

    P. Catlin, Haj´ os’ graph-coloring conjecture: variations and counterexamples,J. Combin. Theory Ser. B26(1979), no. 2, 268–274

    work page 1979

  6. [6]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem,Ann. of Math.164(2006), no. 1, 51–229

    work page 2006

  7. [7]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl, Erd˝ os–Hajnal for graphs with no five-hole,Proc. Lond. Math. Soc.126(2023), no. 3, 997–1014

    work page 2023

  8. [8]

    G. A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc.27(1952), 85–92

    work page 1952

  9. [9]

    Erd˝ os and S

    P. Erd˝ os and S. Fajtlowicz, On the conjecture of Haj´ os,Combinatorica1(1981), 141–143

    work page 1981

  10. [10]

    Erd˝ os and L

    P. Erd˝ os and L. Lov´ asz, Problems and results on 3-chromatic hypergraphs and some related questions,Infinite and Finite Sets (Colloq., Keszthely, 1973), Vol. II, Colloq. Math. Soc. J´ anos Bolyai, Vol. 10, North-Holland, Amsterdam (1975), 609–627

    work page 1973

  11. [11]

    J. Fox, C. Lee and B. Sudakov, Chromatic number, clique subdivisions, and the conjectures of Haj´ os and Erd˝ os–Fajtlowicz,Combinatorica33(2013), 181–197

    work page 2013

  12. [12]

    Gir˜ ao and Z

    A. Gir˜ ao and Z. Hunter, Induced subdivisions inKs,s-free graphs with polynomial average degree,Int. Math. Res. Not.(2025), no. 4, Paper No. rnaf025, 23 pp

    work page 2025

  13. [13]

    Gir˜ ao and Z

    A. Gir˜ ao and Z. Hunter, Induced subdivisions of Kd+1 in graphs of high girth, arXiv:2603.09521 (2026)

    work page arXiv 2026

  14. [14]

    Gy´ arf´ as, Problems from the world surrounding perfect graphs,Appl

    A. Gy´ arf´ as, Problems from the world surrounding perfect graphs,Appl. Math.19 (1987), no. 3–4, 413–441

    work page 1987

  15. [15]

    T. R. Jensen and B. Toft,Graph Coloring Problems, Wiley–Interscience, New York, 1995

    work page 1995

  16. [16]

    H. A. Jung, Eine Verallgemeinerung des n-fachen Zusammenhangs f¨ ur Graphen,Math. Ann.187(1970), 95–103

    work page 1970

  17. [17]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi, Topological cliques in graphs,Combin. Probab. Comput. 3(1994), no. 2, 247–256

    work page 1994

  18. [18]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi, Topological cliques in graphs II,Combin. Probab. Comput.5(1996), no. 1, 79–90

    work page 1996

  19. [19]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus, Topological minors in graphs of large girth,J. Combin. Theory Ser. B86(2002), no. 2, 364–380. 14

    work page 2002

  20. [20]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus, Induced subdivisions inKs,s-free graphs of large average degree,Combinatorica24(2004), no. 2, 287–304

    work page 2004

  21. [21]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus, Improved bounds for topological cliques in graphs of large girth,SIAM J. Discrete Math.20(2006), no. 1, 62–78

    work page 2006

  22. [22]

    Kuratowski, Sur le probl` eme des courbes gauches en topologie,Fund

    K. Kuratowski, Sur le probl` eme des courbes gauches en topologie,Fund. Math.15 (1930), 271–283

    work page 1930

  23. [23]

    L´ evˆ eque, F

    B. L´ evˆ eque, F. Maffray and N. Trotignon, On graphs with no induced subdivision of K4,J. Combin. Theory Ser. B102(2012), no. 4, 924–947

    work page 2012

  24. [24]

    Liu and R

    H. Liu and R. Montgomery, A solution to Erd˝ os and Hajnal’s odd cycle problem,J. Amer. Math. Soc.36(2023), no. 4, 1191–1234

    work page 2023

  25. [25]

    Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen,Math

    W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen,Math. Ann.174(1967), 265–268

    work page 1967

  26. [26]

    Mader, Topological subgraphs in graphs of large girth,Combinatorica18(1998), no

    W. Mader, Topological subgraphs in graphs of large girth,Combinatorica18(1998), no. 3, 405–412

    work page 1998

  27. [27]

    Mader, An extremal problem for subdivisions of K− 5 ,J

    W. Mader, An extremal problem for subdivisions of K− 5 ,J. Graph Theory30(1999), no. 4, 261–276

    work page 1999

  28. [28]

    Mader, Subdivisions of a graph of maximal degree n + 1 in graphs of average degreen+εand large girth,Combinatorica21(2001), no

    W. Mader, Subdivisions of a graph of maximal degree n + 1 in graphs of average degreen+εand large girth,Combinatorica21(2001), no. 2, 251–265

    work page 2001

  29. [29]

    Penev, S

    I. Penev, S. Thomass´ e and N. Trotignon, Isolating highly connected induced subgraphs, SIAM J. Discrete Math.30(2016), no. 1, 592–619

    work page 2016

  30. [30]

    Sachs, Regular graphs with given girth and restricted circuits,J

    H. Sachs, Regular graphs with given girth and restricted circuits,J. London Math. Soc.38(1963), 423–429

    work page 1963

  31. [31]

    A. D. Scott, Induced trees in graphs of large chromatic number,J. Graph Theory24 (1997), no. 4, 297–311

    work page 1997

  32. [32]

    Segre, Ovals in a finite projective plane,Canad

    B. Segre, Ovals in a finite projective plane,Canad. J. Math.7(1955), 414–416

    work page 1955

  33. [33]

    Thomas and P

    R. Thomas and P. Wollan, An improved linear edge bound for graph linkages,European J. Combin.26(2005), no. 3–4, 309–324

    work page 2005

  34. [34]

    Thomassen, Girth in graphs,J

    C. Thomassen, Girth in graphs,J. Combin. Theory Ser. B35(1983), no. 2, 129–141

    work page 1983

  35. [35]

    Trotignon and K

    N. Trotignon and K. Vuˇ skovi´ c, On triangle-free graphs that do not contain a subdivi- sion of the complete graph on four vertices as an induced subgraph,J. Graph Theory 84(2017), no. 3, 233–248

    work page 2017

  36. [36]

    Wang, Balanced subdivisions of a large clique in graphs with high average degree, SIAM J

    Y. Wang, Balanced subdivisions of a large clique in graphs with high average degree, SIAM J. Discrete Math.37(2023), no. 2, 1262–1274. 15

    work page 2023