Paperlane

no. 5 · Friday 30 October 2026

The maximum number of triangles in regular graphs

Ya-Hong Chen, Shi-Cai Gong, Changhong Lu, Zhuojie Tu and Long-Tu Yuan

math.CO

Abstract

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.

fields
Combinatorics
pdf ↗ page arXiv:2610.39461 ↗