Ejercicio sobre el teorema de Turan

Question

Teorema 1

$\alpha(G) \geq \frac{n^2}{2|E(G)| + n}$

donde $\alpha(G)$ representa el mayor conjunto independiente de vértices del gráfico $G$ .

Utilizando teorema 1 demostrar que cualquier gráfico en $n$ vértices sin triángulos tiene como máximo $n^2/4$ bordes.

Busqué una formulación alternativa del teorema en Wikipedia, que da la respuesta fácilmente dando el límite superior de las aristas si el gráfico G es $K_{r+1}$ -libre, utilizando que el ejercicio se vuelve trivial.

Sin embargo, no veo cómo resolverlo con de Teorema 1 . Sé que si consideramos el complemento de $G$ la camarilla más grande sería del mismo tamaño que el conjunto independiente más grande. Pero un triángulo no tiene por qué ser la mayor camarilla, es más, un gráfico complementario de un gráfico sin triángulos no tiene por qué incluir un triángulo. No veo la relación entre no tener triángulos y el tamaño de la mayor camarilla/conjunto independiente.

Cualquier sugerencia será bienvenida.

Answer 1

Si $G$ es un gráfico sin triángulos con $n$ vértices y $m$ aristas, entonces la mayor camarilla en $G$ tiene un tamaño máximo de $2$ . Por lo tanto, $\alpha(\bar{G})\leq 2$ , donde $\bar{G}$ es el complemento de $G$ . Así que Teorema 1 aplicado a $\bar{G}$ da $$2\geq \alpha(\bar{G}) \geq \frac{n^2}{2\left({n\choose 2}-m\right)+n}.$$ Confío en que puedas terminarlo desde aquí.