Problem 904

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}$ ).

If $G$ is a graph with $n$ vertices and $m\geq t_r(n)$ edges there exists a clique on $r$ vertices, say $x_1,\ldots,x_r$ , such that

d(x_1)+\cdots+d(x_r)\geq \frac{2rm}{n}.

Second statement

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}$ ).

If $G$ is a graph with $n\geq r$ vertices and $m\geq t_r(n)$ edges there exists a clique on $r$ vertices, say $x_1,\ldots,x_r$ , such that

d(x_1)+\cdots+d(x_r)\geq \frac{2rm}{n}.

Source: erdosproblems.com/904

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site shows PROVED (LEAN), which describes the corrected Statement, the form the sources prove; its Lean qualification is a catalog suffix explained under Formalization. The corrected Statement holds by Theorem 2 of [BoNi05] with its display (13), for every $r\ge2$ and $n\ge r$ , recorded as the accepted full claim Bollobás--Nikiforov (accepted on the refereed publication and the site's credit), from which the frontmatter standing derives. The earlier ranges are accepted partial claims: Edwards ( $2\le r\le8$ and $n\ge r^2$ , and every $r$ under $m>(r-1)n^2/2r$ ) and Faudree (every $r\ge2$ and $n>r^2(r-1)/4$ ). The Lean proof behind the site's suffix declares itself a formalization of the Bollobás--Nikiforov paper, by Parcly Taxel with the AI system Aristotle, and is a formalization link on that claim page; no build or audit of it is recorded, so it gives no formalized evidence.

Notes

The site's wording leaves $n$ free and fails whenever $n<r$ . For $n\le r$ no graph on $n$ vertices contains $K_{r+1}$ , so $t_r(n)=\binom n2$ and the only graph with $n$ vertices and $m\ge t_r(n)$ edges is $K_n$ ; for $n<r$ it has no clique on $r$ vertices, so the hypothesis is met and the conclusion fails. The smallest failing instance is $r=2$ , $n=1$ ( $K_1$ , $m=0\ge t_2(1)=0$ , no edge); the first that asks for a triangle is $r=3$ , $n=2$ ( $K_2$ , $m=1\ge t_3(2)=1$ , no triangle). The change inserts " $\geq r$ " after "a graph with $n$ ", which excludes exactly the sizes at which no graph has a clique on $r$ vertices, so that no object can meet the conclusion; it is the corpus's own correction, an exclusion of size-degenerate values. No source of higher rank supplies a range. Erdős's own statement of the case $r=3$ , in [Er75], printed p. 13, assumes $e\ge n^2/3$ , which excludes $n<3$ by itself ( $n=1$ needs $e\ge1/3$ and $n=2$ needs $e\ge4/3$ , both above $\binom n2$ ). The hypothesis $n\ge r$ of Theorems 1 and 2 of [BoNi05] is a theorem's range and is not the evidence, and the formal-conjectures statement, which quantifies over $1\le r\le n$ , counts with the site. The defect is not in Erdős's 1975 words: it comes with the hypothesis $m\ge t_r(n)$ in place of his $e\ge n^2/3$ , a form the introduction of [BoNi05] (p. 2) already prints with no range on $n$ (its display (2) fails for $2\le n<r$ , where $\Delta_r(n,m)=0$ by its convention); whether the 1975 Aberdeen collection [BoEr75], where [BoNi05] places the conjecture for every $r$ , restricts $n$ is unknown, since that collection is unread.

BoNi05: Bollobás, Béla and Nikiforov, Vladimir, The sum of degrees in cliques. Electron. J. Combin. 12 (2005), no. 1, Note 21, 10 pp., doi:10.37236/1988 (published 7 November 2005). arXiv:math/0410218v1 (8 October 2004, the only arXiv version, with no journal reference on the arXiv record); Theorem 1, p. 3; display (13) and Theorem 2, p. 6; Corollary 1, p. 7; the introduction's history, p. 2. Library home: Bollobás and Nikiforov 2005; paged at Bollobás and Nikiforov 2005, Theorem 2 (p. 6) and Bollobás and Nikiforov 2005, Corollary 1 (p. 7).
Ed78: Edwards, C. S., 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 (the venue and pages as [BoNi05]'s reference [4] and the volume's contents pages give them; the site's reference text gives "(1978), 293-306" with no venue, and Erdős's 1982 paper cites it with the page "293"). Print only; unread.
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. Not a site key; [BoNi05]'s reference [3], and the Erdős--Laskar note's reference [7], which states a weaker form of its theorem (below). Unread.
Fa92: Faudree, Ralph J., Complete subgraphs with large degree sums. J. Graph Theory 16 (1992), no. 4, 327--334, doi:10.1002/jgt.3190160406 (the Crossref record carries the publisher's abstract). Unread.
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 4, printed p. 13. Library home: Erdős 1975; the passage is paged at Erdős 1975, Conjecture (Chapter 4, printed p. 13 = PDF p. 11).
BoEr75: The site's source key, rendered on the page beside [Er75, p.13]; the site's export carries no reference text for it. [BoNi05]'s reference [2] (p. 10) identifies the conjecture's source as B. Bollobás and P. Erdős, Unsolved problems, Proc. Fifth Brit. Comb. Conf. (Univ. Aberdeen, Aberdeen, 1975), Winnipeg, Util. Math. Publ., 678--680, a volume published as Congr. Numer. XV, Utilitas Math., Winnipeg (1976), as the card of Erdős's paper in the same proceedings records (Erdős 1976), and the formal-conjectures file's docstring prints the key with the same title and pages. Unread.
ErLa85: Erdős, P. and Laskar, R., A note on the size of a chordal subgraph. Congr. Numer. 48 (1985), 81--86; p. 82, the attestation of [Ed77]. Not a site key for this problem. Library home: Erdős and Laskar 1985.

Problem 904

Second statement

Status

Notes

Proof claims

Discussion