The exact generalized Turán number for \(C_6\) in \(C_8\)-free graphs

Abstract

For graphs $F$ and $H$, let $\ex(n,F,H)$ denote the maximum number of copies of $F$ in an $n$-vertex $H$-free graph. Gerbner, Győri, Methuku and Vizer proved that $\ex(n,C_6,C_8)=Θ(n^3)$ and predicted that the unrestricted problem should have the same first-order asymptotics as the bipartite one. We determine the exact value for all sufficiently large $n$, showing that \[ \ex(n,C_6,C_8)=6\binom{n-3}{3}+12(n-5). \] Moreover, the unique extremal graph is $K_3\vee (K_2\cup I_{n-5})$. The main new ingredient is a codegree decomposition for $C_8$-free graphs: a packing lemma for triangles in the linear-codegree graph recovers an almost spanning common neighborhood, and a defect-absorption argument upgrades this stability to the exact extremal graph.

Disclosure

“, 1}, and n − 5 > 0, equality forces rs = 3; hence r = 3 and s = 1. Therefore G∼= K3 ∨ (K2 ∪ In−5 ). This proves both the exact value and uniqueness. Declaration on the use of AI The authors used generative AI tools to assist in discussing proof strategies, checking proofs, and improving exposition. 13”

PDF page 13

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:28:51.963Z

Structural counts