---

Claim. Two results of C. S. Edwards on the degree sum of a clique. First, for $2\le r\le8$ and $n\ge r^2$, every graph with $n$ vertices and $m\ge t_r(n)$ edges has a clique on $r$ vertices whose degree sum is at least $2rm/n$. Second, for every $r\ge2$, a graph with $n$ vertices and $m>(r-1)n^2/2r$ edges has such a clique; since $(r-1)n^2/2r\ge t_r(n)$, this is the conclusion under a stronger hypothesis on $m$, and for $r=3$ it is a triangle of degree sum at least $6m/n$ when $m>n^2/3$. The papers are C. S. Edwards, Complete subgraphs with largest sum of vertex degrees, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai 18, North-Holland (1978), 293--306, and C. S. Edwards, 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. Both are unread; the statements above are those of the introduction of Bollobás and Nikiforov's paper (p. 2; card): "Edwards [3], [4] proved (2) under the weaker condition $m>(r-1)n^2/2r$; he also proved that the conjecture holds for $2\le r\le8$ and $n\ge r^2$", where (2) is the conjectured bound and "weaker" is the paper's word for the stronger condition. The site's commentary credits the first result to the 1978 paper. Erdős and Laskar's note (Congr. Numer. 48 (1985), p. 82; card) attests the 1977 paper only in a weaker form, a triangle of degree sum at least $2n$ when $m\ge n^2/3$. Both results prove parts of the corrected Statement of Problem 904.

Covers. (a) $2\le r\le8$ with $n\ge r^2$ and every $m\ge t_r(n)$; (b) every $r\ge2$ and $n\ge r$ with $m>(r-1)n^2/2r$, which leaves out the edge counts $t_r(n)\le m\le(r-1)n^2/2r$. The whole statement is the accepted full claim Bollobás--Nikiforov.

Depends on. Nothing in this wiki; the results rest on the cited papers alone.

Acceptance. Reviewed: the site's curator, T. F. Bloom, credits Edwards [Ed78] with the range $2\le r\le8$, $n\ge r^2$ in the problem's commentary on a page labeled PROVED (LEAN), and Bollobás and Nikiforov's refereed paper credits both results in its introduction. The range (a) rests on the Bolyai proceedings volume, which no record shows was refereed, so refereed is not listed although the 1977 paper appeared in the Bulletin of the London Mathematical Society.

Dating. The page is dated by the year of the Bolyai volume, 1978; the month and day are placeholders. The colloquium met in 1976, and the triangle case appeared in 1977.