¿Cómo probar el teorema de Mantel del límite de la teoría de grafos es lo mejor posible?

Question

El teorema establece que cada gráfico de orden$n$ y el tamaño mayor que la función de piso$\lfloor \frac{n^2}{4} \rfloor$ contienen un triángulo.

Ya conozco una prueba del número del borde del gráfico$\leq\frac{n^2}{4}$ si no contiene un triángulo, pero cómo demostrar que este límite es mejor si n es mayor que 100, en otra palabra, cómo probar allí ¿Son infinitos ejemplos para satisfacer el mejor límite?

Answer 1

No podemos usar un pequeño obligado porque podemos demostrar que para cada número natural $n$, existe un grafo de orden $n$ con exactamente $\lfloor \frac{n^2}{4} \rfloor$ bordes y no triángulos. En respuesta a su edición, esto nos da un número infinito de ejemplos.

Así que vamos a $n$ ser un número natural, y vamos a encontrar un gráfico de la orden de $n$ sin triángulos y $\lfloor \frac{n^2}{4} \rfloor$ bordes.

Si $n$ es incluso, a continuación,$\lfloor \frac{n^2}{4} \rfloor = \frac{n^2}{4}$, y el gráfico de $K_{n/2,n/2}$ $\left( \frac{n}{2} \right) \left( \frac{n}{2} \right) = \frac{n^2}{4}$ bordes y no triángulos.

Si $n$ es impar, entonces $n = 2m + 1$ para algunos entero $m$, por lo que \begin{align*} \lfloor \frac{n^2}{4} \rfloor &= \lfloor \frac{4m^2 + 4m + 1}{4} \rfloor \\ &= \lfloor m^2 + m + \frac{1}{4} \rfloor \\ &= m(m + 1). \end{align*} A continuación, el gráfico de $K_{m,m+1}$ orden $m + m + 1 = n$, sin triángulos, y ha $m(m + 1) = \lfloor \frac{n^2}{4} \rfloor$ bordes.