The maximum number of triangles in regular graphs
We determine the maximum number of triangles in $n$-vertex $k$-regular graphs and characterize all extremal graphs for all admissible orders when $k$ is odd and for an explicit range of orders when $k$ is even. For even $k$, we also give explicit lower and upper bounds for the remaining orders. As a consequence, we obtain a lower bound on the number of independent sets of size three in $k$-regular graphs and characterize all equality cases. Our exact results confirm the conjecture of Petingi and Rodríguez and the triangle case of a conjecture of Cambie, de Joannis de Verclos and Kang for all odd $k$ and the specified orders when $k$ is even. Moreover, for every even $k\ge18$, we construct counterexamples to both conjectures and obtain a recursive characterization of all extremal graphs of order at least $Ck$, where $C$ is an absolute constant.
Authors
- Long‐Tu Yuan (ORCID: https://orcid.org/0000-0002-4602-5911)
- Zhuojie Tu
- Shi-Cai Gong (ORCID: https://orcid.org/0000-0002-0635-8308)
- Changhong Lu
- Ya-Hong Chen
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-10-29
- DOI
- https://doi.org/10.48550/arxiv.2610.39461
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint