Solution

We prove the Quadratic Turan edge bound by induction. The case

r = 1

is immediate. For

r \geq 2

, if

G

contains no

K_{r}

, the induction hypothesis for

r - 1

gives the stronger bound. Otherwise choose a copy

S

K_{r}

. Every vertex outside

S

has at most

r - 1

neighbours in

S

, since one adjacent to all of

S

would complete a

K_{r + 1}

. Thus the number of edges having at least one endpoint in

S

is at most

(2 r) + (n - r) (r - 1) = (r - 1) (n - \frac{r}{2}) .

The graph

G - S

is still

K_{r + 1}

-free, so induction on the number of vertices gives

e (G) \leq (1 - \frac{1}{r}) \frac{( n - r ) ^{2}}{2} + (r - 1) (n - \frac{r}{2}) = (1 - \frac{1}{r}) \frac{n ^{2}}{2} .

This proves the stated form of Turan theorem.

Solved by gpt-5.6-sol high.

 Ancestors (11)