Problem 1033

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?

Source: erdosproblems.com/1033

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. The bounds in hand are $\frac{21}{16}n<h(n)\le2(\sqrt3-1)n+O(1)$ , with $21/16=1.3125$ and $2(\sqrt3-1)\approx1.4641$ . The lower bound is Fan's Theorem 1 with its Corollary 1.1 (J. Graph Theory 12 (1988), refereed): every graph with $n$ vertices and $e>n^2/4$ edges has a triangle with degree sum $>21e/4n$ , so $f(n,\lfloor n^2/4\rfloor+1)>21n/16$ as printed on p. 251 (Fan 1988, Theorem 1 (p. 252)); the earlier lower bound $h(n)\ge(1+\eta)n$ for a fixed $\eta>0$ and large $n$ is Theorem 2 of the Erdős--Laskar note (Erdős and Laskar 1985, Theorem 2 (p. 83)). The upper bound is the site's construction, recomputed below as an authored check; the site attributes it to Erdős and Laskar and says the bound is not explicit in their 1985 note, whose six pages indeed contain no such construction, while Fan's § 2 (pp. 251--252) prints the construction in full with the bound $f(n,e)<4\sqrt{3e}-2n+5$ for $n^2/4<e<n^2/3$ (Fan 1988, Upper bound (§ 2, p. 251)) and credits it to "the construction described in [4]", his reference [4] being that same 1985 note. The value of $h(n)/n$ is not known; no source settling the "in particular" question was found in the search whose scope the Current assessment records, and the thread's June--July 2026 claims that the conjectured lower bound fails are a pending partial claim, unreviewed and recorded below. This is a bounded negative finding, not a certificate of openness. Erdős's 1982 report that the inequality $3n/2$ was proved by Edwards is recorded beside these bounds, with which it is inconsistent, and is not resolved here.

Fa88: Fan, Genghua, Degree sum for a triangle in a graph. J. Graph Theory 12 (1988), no. 2, 249--263, doi:10.1002/jgt.3190120216; the definitions, pp. 249--250; the bounds and the § 2 construction, pp. 251--252; Theorem 1, p. 252; Corollary 1.1, p. 253; Theorem 2, p. 259; Theorem 3 and Corollary 3.1, pp. 261--262. Library home: Fan 1988; paged at Fan 1988, Theorem 1 (p. 252) and Fan 1988, Upper bound (§ 2, p. 251).
ErLa85: Erdős, P. and Laskar, R., A note on the size of a chordal subgraph. Congr. Numer. 48 (1985), 81--86 (the Rényi archive scan); the summary and the Edwards remark, p. 82; Theorem 1, p. 82; Theorem 2, p. 83. Library home: Erdős and Laskar 1985; paged at Erdős and Laskar 1985, Theorem 1 (p. 82) and Erdős and Laskar 1985, Theorem 2 (p. 83).
ErLa83: Erdős, P. and Laskar, R., On maximum chordal subgraphs. Congr. Numer. 39 (1983), 367--373; [ErLa85]'s reference [8] and [BoNi05]'s reference [5]. Not a site key; not held.
BoNi05: Bollobás, Béla and Nikiforov, Vladimir, The sum of degrees in cliques. Electron. J. Combin. 12 (2005), N21, doi:10.37236/1988; cited from arXiv:math/0410218v1; the introduction, p. 2; Theorem 3, p. 8. Library home: Bollobás and Nikiforov 2005; paged at Bollobás and Nikiforov 2005, Theorem 3 (p. 8).
Fa92: Faudree, Ralph J., Complete subgraphs with large degree sums. J. Graph Theory 16 (1992), no. 4, 327--334, doi:10.1002/jgt.3190160406 (Crossref record with the publisher's abstract). Not held; the site's source for Erdős's construction, quoted here through [BoNi05].
Ed77: Edwards, C. S., The largest vertex degree sum for a triangle in a graph. Bull. London Math. Soc. 9 (1977), no. 2, 203--208, doi:10.1112/blms/9.2.203 (Crossref record accessed). Not a site key; [ErLa85]'s reference [7], whose theorem it states. Not held.
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; §5, printed p. 71. Library home: Erdős 1982.
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 4, printed p. 13, the conjecture for $e\ge n^2/3$ . Not a site key for this problem. Library home: Erdős 1975; paged at Erdős 1975, Conjecture (Chapter 4, printed p. 13 = PDF p. 11).
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350, doi:10.1080/16073606.1993.9631741. Chapter V, problem 3, printed pp. 343--344: the definition of $h(n)$ , display (1) $2(\sqrt3-1)n\ge h(n)>\frac{21n}{16}$ , the upper bound credited to Erdős and Laskar (its reference [45], which is [ErLa85]) and the lower to Fan (its [46], [Fa88]), and "Perhaps the upper bound in (1) is the correct value for $h(n)$ "; no construction and no proof. Library home: Erdős 1993.

Problem 1033

Status

Proof claims

Discussion