¿Es un error de Pruebas del Libro?

Question

He visto el lema de cruce en el capítulo cuarenta y cinco titulado La probabilidad hace que contar (a veces) fácil .

Teorema 4. Dejemos que $G$ sea un grafo simple con n vértices y m aristas, donde $m \ge 4n$ . Entonces $${\rm{cr}}(G) \ge \frac{1}{64}\frac{m^3}{n^2}$$ Lo que me confunde es esta frase, marcada en morado: Sabemos que si $n=1$ entonces $cr(K_1)-m+3n=3<6$ . No satisface (4).

De la misma manera, $K_2$ es uno y el último insatisfecho. ¿Es esto un error? ¿Es posible utilizar otros métodos para obtener este resultado? $$E(X_p-m_p+3n_p)\ge 0?$$ El enlace a la versión electrónica está más abajo. Pruebas de El Libro

Answer 1

Gracias a todos por su entusiasta ayuda. Parece que entiendo el origen del problema. Efectivamente, aplicar (4) por sí solo es problemático. (4) sólo es válida para $n \geq 3$ .
Pero $E(X_p-m_p+3n_p)\ge 0$ sigue siendo correcto . Desde cuando $n$ es menor o igual a 2 la fórmula sigue siendo válida.

Para ser más específicos.

Si $n=1$ entonces $cr(K_1)-m+3n=3>0$ .

Si $n=2$ entonces $cr(K_2)-m+3n=0-2+6=4>0$ y $cr(2K_1)-m+3n=0-0+6>0$