Problem Statement
Let $h(n)$ be such that every graph on $n$ vertices with $>n^2/4$ many edges contains a triangle whose vertices have degrees summing to at least $h(n)$. Estimate $h(n)$. In particular, is it true that\[h(n)\geq (2(\sqrt{3}-1)-o(1))n?\]
Categories:
Graph Theory
Progress
Erdős and Laskar [ErLa85] proved\[2(\sqrt{3}-1)n \geq h(n) \geq (1+c)n\]for some $c>0$. The lower bound was improved to $\frac{21}{16}n$ by Fan [Fa88].Source: erdosproblems.com/1033 | Last verified: January 19, 2026