---

Statement

Notation (pp. 968--969). $G(n;e)$ is a graph with $n$ vertices and $e$ edges, and $K_r(p_1,\dots,p_r)$ is the complete $r$-partite graph with $p_i$ vertices in the $i$-th part. As on the Theorem 1 page, $m(n;l)$ is read as the largest number of edges of a graph on $n$ vertices with no $K_{l+1}$, the edge count of the complete $l$-partite graph with parts as equal as possible; the paper's definition on p. 968 is off by one from this use.

Lemma (p. 969, unnumbered). For $n>n_0(l)$, every graph on $n$ vertices with $m(n;l)+n+1$ edges contains $K_{l+1}(1,3,\dots,3)$.

Proof pointer

No proof is given. The paper credits the lemma to Simonovits and Erdős, citing (reference 5) M. Simonovits, A method for solving extremal problems in graph theory, Stability problems, then to appear in the proceedings of the Colloquium on Graph Theory of 1966 (the print names the place "Ochary" [sic]), and P. Erdős, Extremal problems in graph theory, Proceedings of the Symposium on Theory of Graphs and Its Applications, Smolenice (1963), 29--36.

Read depth

Claims checked: the statement and the notation were read on the page images of the print. The lemma is an external result; it is not proved in the paper and its proof was not checked here.

Dependencies

None in the corpus.

Source. P. Erdős, On some applications of graph theory to geometry, Canad. J. Math. 19 (1967), 968--971; the edition read is named on the source card.

Bears on

• Problem 1085: through Theorem 1, whose upper bound $f_d(n)\le m(n;l)+n$ for even $d=2l\ge4$ and large $n$ rests on this lemma; the lemma itself is a statement about graphs only.