The maximum number of triangles in regular graphs
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≥18, 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.
Related
- On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
- On the minimum number of triangles in balanced tripartite graphs with large minimum degree
- Maximum cut and maximum bisection in random regular graphs
- The Maximum Commute Time of Regular Graphs
- Maximum edge overlap between independent random regular graphs
BibTeX
@misc{chen2026maximum,
title = {{The maximum number of triangles in regular graphs}},
author = {Ya-Hong Chen and Shi-Cai Gong and Changhong Lu and Zhuojie Tu and Long-Tu Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39461},
eprint = {2610.39461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39461},
}
RIS
TY - UNPB
TI - The maximum number of triangles in regular graphs
AU - Ya-Hong Chen
AU - Shi-Cai Gong
AU - Changhong Lu
AU - Zhuojie Tu
AU - Long-Tu Yuan
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39461
UR - https://arxiv.org/abs/2610.39461
AB - 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≥18, 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.
ER -