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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

The maximum number of triangles in regular graphs

Long‐Tu Yuan, Zhuojie Tu, Shi-Cai Gong, Changhong Lu et al.
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

The maximum number of triangles in regular graphs

Long‐Tu Yuan, Zhuojie Tu, Shi-Cai Gong, Changhong Lu, Ya-Hong Chen
preprint en

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.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon