vértices que no contiene ningún
partes de igual tamaño (o cuyo tamaño difiere en a lo más en un vértice), y conectando cualesquiera dos vértices pertenecientes a partes distintas.
vértices que son libres de
Los grafos de Turán fueron descubiertos y estudiados por el matemático húngaro Pál Turán en 1941; sin embargo, un caso especial de dicho teorema fue demostrado anteriormente por Mantel en 1907.
-clanes y que contiene el máximo número de aristas posibles.
Idea general Demostramos que un grafo en n vértices libre de
Colocamos una arista entre cualquier par vértices tales que uno está en
es una relación de equivalencia, ya que esto implicaría que está relación particiona los vértices de
tales que ningún par de vértices dentro de la misma clase están conectados, y cualesquiera dos vértices en clases diferentes están conectados.
es una gráfica simple y ningún vértice está conectado consigo mismo.
Además, es claramente simétrica, por lo que sólo queda por demostrar la propiedad de transitividad.
Con el fin de llegar a una contradicción, supongamos que dicha relación no es transitiva.
y creamos una copia del vértice
Llamemos a esta nueva gráfica
no puede tener más vértices que la mayor clique en
contiene más ejes ya que: lo cual contradice la maximalidad del número de aristas en
y creamos dos copias del vértice
que se obtiene de este proceso no puede contener
-clanes, pero tiene más aristas: Ya que en cualquiera de los dos casos arriba,
es transitiva, y concluimos que es una relación de equivalencia.
-partita completa es maximizado cuando cualesquiera dos de las partes en que el conjunto de vértices queda subdividido difieren en tamaño en a lo más 1.
Entonces, en total el número de aristas aumentó ya que
Gracias a las Observaciones 1 y 2, la única posibilidad restante de que dicho grafo
Sin embargo, en dicho caso podemos también tratar a
conteniendo 0 vértices, y aplicar el mismo razonamiento de la Observación 2.
Explícitamente, este es su enunciado: En otras palabras, para obtener un grafo libre de triángulos a partir del grafo completo
Una versión más fuerte del Teorema de Mantel establece que cualquier grafo Hamiltoniano con al menos
, o de lo contrario es pancíclico; no solo contiene un triángulo, sino que además contiene ciclos de todas las posibles longitudes
Otra versión fuerte del teorema de Mantel establece que para cualquier grafo en
vértices, este puede ser cubierto por una colección de a lo sumo