Suponga que G es un grafo simple con n vértices y 2n extremos en donde n es un entero positivo. Por el ejercicio 34, su número de extremos no puede...

Suponga que G es un grafo simple con n vértices y 2n extremos en donde n es un entero positivo. Por el ejercicio 34, su número de extremos no puede exceder n(n−1)/2. Así 2n ≤ n(n−1)/2, o 4n ≤ n^2 − n. Equivalentemente, n^2 − 5n ≤ 0, o n(n − 5) ≤ 0. Esto implica que n = 5 ya que n > 0. Entonces un grafo simple con el doble de extremos que de vértices debe tener al menos cinco vértices. Pero un grafo completo con cinco vértices tiene 5(5−1)/2 = 10 extremos y 10 = 2 · 5. En consecuencia, la respuesta a la pregunta es sí porque K5 es un grafo con dos veces más extremos que vértices.