Erdős #1033 · graph theory

A conjecture of Bollobás and Erdős. In [Er82e] it is asked whether $h(n)\geq \frac{3}{2}n$. It is now known that

The upper bound is due to Erdős and Laskar [ErLa85], and the lower bound is due to Fan [Fa88]. (Note that $2(\sqrt{3}-1)\approx 1.464$ and $21/16=1.3125$.)

The upper bound is not made explicit in [ErLa85], which is concerned with chordal subgraphs (i.e. subgraphs which do not contain any induced cycle on $>3$ vertices). The connection to this problem is that taking a triangle together with all incident edges forms a chordal subgraph of $G$. The construction of the upper bound is made more explicit in [Fa88].

In brief, let $m=\lfloor n^2/4\rfloor+1$ and take a complete bipartite graph between $k$ and $l$ vertices where $k+l=n$ and $k=cn$. If $c$ is chosen such that $m-kl\leq k^2/4$ then we can add $m-kl$ edges between the $k$ vertices creating no triangles, while having maximum degree (amongst these vertices) $\lceil 2\frac{m-kl}{k}\rceil$. This creates a graph $G$ on $n$ vertices with $m$ edges. Every triangle uses exactly one vertex from the side with $l$ vertices and two vertices from the side with $k$ vertices, and hence the sum of degrees is at most

This is minimised at $c=1/\sqrt{3}$, where it is $2(\sqrt{3}-1)n+O(1)$ (and a short calculation verifies that with this choice of $c$ we do indeed have $m-kl\leq k^2/4$).

More generally, let $\Delta_r(n,m)$ be such that every graph $G$ with $n$ vertices and $m$ edges contains a clique on $r$ vertices, say $x_1,\ldots,x_r$, such that

Let $r\geq 2$ and let $t_r(n)$ be the Turán number (the maximal number of edges in a graph on $n$ vertices with no $K_{r+1}$). One can ask more generally about the behaviour of $\Delta_r(n,m)$ for $m>t_{r-1}(n)$ (when $m\leq t_{r-1}(n)$ this is trivial since there may be no clique on $r$ vertices at all). The behaviour of $\Delta_r(n,m)$ in the regime $m\geq t_r(n)$ is the subject of [904].

Erdős (see [Fa92]) proved that, for every $\epsilon>0$, there exists $\delta>0$ such that if $t_{r-1}(n)<m<t_r(n)-\delta n^2$ then

Bollobás and Nikiforov [BoNi05] proved that, for every $\epsilon>0$, there exists $\delta>0$ such that if $m>t_r(n)-\delta n^2$ then

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.