Gráfico contiene triángulo

Question

Probar que si un simple gráfico de orden n tiene más de n^2/4 bordes, a continuación, contiene un triángulo.

Sé Martels teorema de los estados de la condición opuesta de un triángulo de libre gráfico, pero no estoy seguro de cómo demostrar esta condición.

Answer 1

Deje $G$ ser un simple gráfico de la orden de $n$. A continuación, la Repisa de la chimenea del Teorema establece que:

Si $G$ es de triángulo gratis, $G$ tiene más de $n^2/4$ bordes.

Pero al tomar el contrapositivo de esta implicación, conseguimos exactamente lo que queremos:

Si $G$ tiene más de $n^2/4$ bordes, a continuación, $G$ contiene un triángulo.

Answer 2

Deje $G$ un gráfico de la orden de $n$ y el tamaño de la $m$. Suponga que $G$ $K_3$- libre. Luego por la Repisa de la chimenea del Teorema sabemos que $m\leq {n^2\over 4}$. Sin embargo, esto es una contradicción ya que estamos, dado que el $m> {n^2\over 4}$. Por lo tanto si $G$ orden $n$$m>{n^2\over 4}$, $G$ contiene un triángulo.