Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let . If is a graph on vertices with at least edges then must contain a vertex with degree whose neighbourhood contains at least edges?
Source: erdosproblems.com/1079
An accepted solution exists. The statement is true.
Solved, the site's label; the answer is yes, and the standing here is solved and proved, derived from the claim pages below. The site credits the affirmative answer, with the Turán graph as the one exception, to Bollobás and Thomason [BoTh81], credits Bondy [Bo83b] with the strengthening that for more than edges the vertex can be taken of maximum degree, and the community database records the problem as solved. The two status-defining sources are B. Bollobás and A. Thomason, "Dense neighbourhoods and Turán's theorem", J. Combin. Theory Ser. B 31 (1981), no. 1, 111--114, and J. A. Bondy, "Large dense neighbourhoods and Turán's theorem", J. Combin. Theory Ser. B 34 (1983), no. 1, 109--111 (both refereed, per their Crossref records). Neither source card holds a file. [BoTh81] (library home Bollobás and Thomason 1981, the publisher's open-archive version) carries the affirmative answer in its theorem (printed p. 111), paged at Bollobás and Thomason 1981, Theorem (p. 111), in the paper's indexing with the -partite Turán graph and its number of edges: "Let be a graph of order with edges. Then either or else there is a vertex such that , the subgraph spanned by the neighbours of , contains at least edges, where . Furthermore ." With this is the site's statement in the paper's letters, with the "" of Erdős's question in the conclusion, the Turán graph the only exception, and an explicit constant, in the site's indexing (). The paper attributes the conjecture to [Er75], its [2], in the form "if " (p. 111). Its proof (pp. 112--114) is followed on the card, which records four observations (three misprints and a final inequality that needs in the paper's ). [Bo83b] (library home Bondy 1983, the publisher's version with its erratum) carries Bondy's own strengthening as its Theorem 2 (p. 110), paged at Bondy 1983, Theorem 2, in the same indexing: "Let be a simple graph on vertices and more than edges, where , and let be a vertex in of degree . Then the subgraph induced by the neighbours of has more than edges"; its proof is twelve lines. In the problem's letters: more than edges, Erdős's , force every vertex of maximum degree to have a neighborhood with more than edges, Erdős's "at least "; the maximum degree is at least the average degree, which is more than , so the degree is linear (this page's own observation; the note states no degree bound for its own theorem). The note also states the theorem of [BoTh81] as its Theorem 1 (p. 109), paged at Bondy 1983, Theorem 1, with the attribution "proved independently by Bollobás and Thomason [1] and Erdős and Sós [4]" and the degree bound as its (1); the restatement agrees with the 1981 theorem, its "more than edges" being that paper's "at least edges", and it names a second proof, an Erdős--Sós preprint, which is not among this page's sources. Bondy's examples (p. 111), graphs with exactly edges that are not Turán graphs and whose maximum-degree vertices do not have the strict conclusion, show that the "" of the site's account of [Bo83b] cannot be weakened for that conclusion; for the site's non-strict conclusion a maximum-degree vertex always works, as the Bondy claim page records. Nothing here is independently reviewed. The site's label SOLVED attaches to an affirmative answer proved in two refereed notes; the claim pages (Bollobás and Thomason, full, and Bondy, partial, for graphs with more than edges) record the result as proved.