The Maximum Number of Triangles in a Graph of Given Maximum Degree

Abstract

We prove that any graph on $n$ vertices with max degree $d$ has at most $q\left(\genfrac{}{}{0ex}{}{d+1}{3}\right)+\left(\genfrac{}{}{0ex}{}{r}{3}\right)$ triangles, where $n=q(d+1)+r$, $0\le r\le d$. This resolves a conjecture of Gan-Loh-Sudakov.

arXiv comment5 pages, 1 figure