pith. sign in

arxiv: 2606.19717 · v1 · pith:A4YNCYARnew · submitted 2026-06-18 · 🧮 math.CO

Counting triangles in graphs with no wheels of order at least five

Chunyang Dou , Bo Ning , Xing Peng This is my paper

Pith reviewed 2026-06-26 17:23 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorytriangle countingwheel-free graphsforbidden subgraphsW_{\geq 4}-free graphsgraph characterization
0
0 comments X

The pith

The maximum number of triangles in an n-vertex graph with no wheel of order five or larger is determined exactly for every n at least 3, along with the extremal graphs.

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

The paper sets out to compute the largest possible number of triangles inside any n-vertex graph that contains none of the wheel graphs W_ℓ for ℓ ≥ 4 as a subgraph. A wheel W_ℓ consists of a cycle of length ℓ plus one additional vertex joined to every vertex on that cycle. The authors supply both the exact maximum value and the complete list of graphs that attain it. This supplies a concrete bound on how many triangles can appear once wheels with four or more spokes are forbidden, extending an earlier line of questions that began with Gallai's conjecture for smaller wheels.

Core claim

For every integer n ≥ 3 the largest number of triangles in an n-vertex W_{≥4}-free graph is attained precisely by a family of graphs that the paper identifies, giving both the numerical value and the characterization of all such extremal graphs.

What carries the argument

The family of W_{≥4}-free graphs together with a structural description that permits an exact count of their triangles.

If this is right

  • The extremal graphs are completely characterized for every n.
  • The result gives a closed-form expression for the maximum number of triangles under the W_{≥4} prohibition.
  • It resolves the k=4 case of the general problem of maximizing triangles in W_{≥k}-free graphs.
  • Any graph with more triangles must contain at least one wheel of order five or larger.

Where Pith is reading between the lines

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

  • The same structural approach could be tested on the still-open cases for k>4.
  • The extremal constructions may serve as base cases for inductive arguments that bound other small subgraphs once wheels are forbidden.
  • Algorithms that enumerate triangles in sparse graphs could exploit the absence of large wheels to prune their search space.

Load-bearing premise

That the structure of every W_{≥4}-free graph is restricted enough to yield one closed-form maximum triangle count that works for all n without extra case distinctions.

What would settle it

An n-vertex graph containing no W_ℓ for ℓ ≥ 4 yet possessing strictly more triangles than the number claimed to be maximal.

read the original abstract

For a family of graphs $\mathcal F$, a graph $G$ is said to be $\mathcal F$-free if it contains no member of $\mathcal F$ as a subgraph. A wheel graph $W_k$ is a graph on $k+1$ vertices formed by joining a new vertex to all vertices of a $k$-cycle. Given an integer $k\ge 3$, we consider the problem of determining the maximum number of triangles in a $W_{\geq k}$-free graph, where $W_{\geq k}=\{W_\ell: \ell \geq k\}$. The case $k=3$ was raised by Gallai, who proposed a conjecture for this case (see Erd\H{o}s [5]. Gallai's conjecture was disproved by Zhou [17] and independently by F\"uredi, Goemans, and Kleitman [9]. In this paper, we study the case $k=4$. Namely, for every integer $n\ge 3$, we determine the maximum number of triangles in an $n$-vertex $W_{\geq 4}$-free graph and characterize all extremal graphs.

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

0 major / 1 minor

Summary. The paper claims that for every integer n≥3, the maximum number of triangles in an n-vertex W_{≥4}-free graph is determined exactly, along with a characterization of all extremal graphs. This addresses the k=4 case of maximizing triangles in W_{≥k}-free graphs, following the disproved Gallai conjecture for k=3.

Significance. If the claimed exact determination and characterization hold, the result would give a complete closed-form solution for triangle maximization under the W_{≥4}-free condition, extending known results on forbidden wheels and providing a structural classification that yields uniform counts without n-dependent case distinctions.

minor comments (1)
  1. The abstract states the main theorem but the provided text contains no proof steps, extremal constructions, or verification for the claimed closed-form count; a complete manuscript must include the structural classification of W_{≥4}-free graphs and the derivation of the triangle bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their time in reviewing the manuscript and for accurately summarizing our main result: the exact determination of the maximum number of triangles in an n-vertex W_{\geq 4}-free graph together with a characterization of the extremal graphs. The recommendation is listed as uncertain, but the report contains no specific major comments or points of concern. We therefore have no individual referee comments to address point by point at this stage.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper claims a direct combinatorial determination of the extremal number of triangles in W_{≥4}-free graphs on n vertices, together with a characterization of the extremal graphs. The abstract and available text contain no fitted parameters, no equations that equate a derived quantity to an input by construction, and no load-bearing self-citations. Prior results cited (Gallai, Zhou, Füredi et al.) are by other authors and concern a different case (k=3). The derivation is therefore presented as self-contained structural graph theory rather than a reduction to previously fitted or self-defined quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a standard combinatorial proof in extremal graph theory; the abstract introduces no numerical parameters, no new postulated objects, and relies only on the usual definitions of graphs and subgraphs.

axioms (1)
  • standard math Standard definitions of simple undirected graphs, subgraphs, wheels W_k, and the family W_{≥k}.
    Invoked throughout the abstract to define the problem.

pith-pipeline@v0.9.1-grok · 5732 in / 1216 out tokens · 38513 ms · 2026-06-26T17:23:34.521108+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

18 extracted references

  1. [1]

    Alon and C

    N. Alon and C. Shikhelman, ManyT-copies in H-free graphs,J. Combin. Theory Ser. B121 (2016), 146–172

    2016

  2. [2]

    Bollobás, On complete subgraphs of different orders,Math

    B. Bollobás, On complete subgraphs of different orders,Math. Proc. Cambridge Philos. Soc.79 (1976), 19–24

    1976

  3. [3]

    Dzido and A

    T. Dzido and A. Jastrzębski, Turán numbers for odd wheels,Discrete Math.341(2018), 1150–1154. 13

    2018

  4. [4]

    Erdős, On the number of complete subgraphs contained in certain graphs,Magyar Tud

    P. Erdős, On the number of complete subgraphs contained in certain graphs,Magyar Tud. Akad. Mat. Kutató. Int. Közl.7(1962), 459–464

    1962

  5. [5]

    Erdős, Problems and results in combinatorial analysis and graph theory,Discrete Math.72 (1988), 81–92

    P. Erdős, Problems and results in combinatorial analysis and graph theory,Discrete Math.72 (1988), 81–92

    1988

  6. [6]

    Erdős and T

    P. Erdős and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Hungar.10 (1959), 337–356

    1959

  7. [7]

    Erdős and M

    P. Erdős and M. Simonovits, A limit theorem in graph theory,Studia Sci. Math. Hungar.1 (1966), 51–57

    1966

  8. [8]

    Erdős and A

    P. Erdős and A. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.52(1946), 1087–1091

    1946

  9. [9]

    Füredi, M

    Z. Füredi, M. Goemans and D. Kleitman, On the maximum number of triangles in wheel-free graphs,Combin. Probab. Comput.3(1994), 63–75

    1994

  10. [10]

    D. Hei, X. Hou and Y. Ma, The generalized Turán number forK3 in graphs without suspensions of a path on five vertices,Discrete Math.349(2026), 115158, 9 pp

    2026

  11. [11]

    Mubayi and S

    D. Mubayi and S. Mukherjee, Triangles in graphs without bipartite suspensions,Discrete Math. 346(2023), 113355, 19 pp

    2023

  12. [12]

    Mukherjee, Exact generalized Turán number forK3 versus suspension ofP4,Discrete Math

    S. Mukherjee, Exact generalized Turán number forK3 versus suspension ofP4,Discrete Math. 347(2024), 113866, 7 pp

    2024

  13. [13]

    V. T. Sós, Remarks on the connection of graph theory, finite geometry and block designs, inColloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II, Accademia Nazionale dei Lincei, Rome, (1976), 223–233

    1973

  14. [14]

    Turán, On an extremal problem in graph theory,Mat

    P. Turán, On an extremal problem in graph theory,Mat. Fiz. Lapok48(1941), 436–452

    1941

  15. [15]

    Yuan, Extremal graphs for odd wheels,J

    L.-T. Yuan, Extremal graphs for odd wheels,J. Graph Theory98(2021), 691–707

    2021

  16. [16]

    Zelinka, Locally tree-like graphs,Časopis Pěst

    B. Zelinka, Locally tree-like graphs,Časopis Pěst. Mat.108(1983), 230–238

    1983

  17. [17]

    Zhou, A counterexample to a conjecture of Gallai,Ars Combin.39(1995), 93–96

    B. Zhou, A counterexample to a conjecture of Gallai,Ars Combin.39(1995), 93–96

    1995

  18. [18]

    X. Zhu, Y. Chen, D. Gerbner, E. Győri and H. Hama Karim, The maximum number of triangles inF k-free graphs,European J. Combin.114(2023), 103793, 19 pp. 14

    2023