On properties of extremal graphs

Question

Let H be a graph, and define $c_n(H) := \frac{ex(n, H)}{\frac{n(n-1)}{2}}$ Prove that $c_n(H) \leq c_{n−1}(H)$, and show that $\lim_{n→∞} c_n(H)$ exists.

So first of all, if we managed to show that the inequality holds, then this means that $(c_n(H))$ is a decreasing sequence bounded by $0$ and so the limit will exist.

The inequality is equivalent to $$\frac{ex(n, H)}{n} \leq \frac{ex(n-1, H)}{n-2}$$

I have no idea how to proceed. The only inequality I know about extremal graphs is that if $H$ has chromatic number $r+1$, then it certainly isn't $r$-partite so the Turan graph $T_r(n)$ will contain no copy of $H$. But this certainly won't work

Any hints/suggestions are appreciated

Answer 1

Hint: remove a vertex of minimum degree from a graph not containing $H$.

Proof: Suppose $G$ is a graph on $n$ vertices and $\text{ex}(n, H)$ edges that does not contain a copy of $H$. Then there is a vertex $v$ of $G$ of degree no more than $2\text{ex}(n, H)/n$, by a simple averaging argument. Upon deleting $v$, $G - v$ has at least $\text{ex}(n, H)(1-\frac{2}{n})$ edges and $n-1$ vertices, and $G-v$ also does not contain a copy of $H$. Thus $$ \text{ex}(n-1, H) \geq \text{ex}(n, H) (1-2/n) $$ and the desired inequality follows.