Es cierto que una gráfica con muchas aristas tiene un largo recorrido?

Question

Es la frase siguiente verdad o no?

Si tenemos un gráfico con $n$ vértices, y $e$ bordes, si $e > 100 n$, entonces siempre tenemos una $100$-ruta larga en el gráfico.

Creo que es cierto, he intentado usar ese $2e = \sum_{i=1}^{n}d_i$, lo que significa que el promedio de grado de un vértice es, al menos,$200$. Realmente no puede ir hacia adelante. Alguna ayuda? :)

Edit: Respuesta a continuación.

Answer 1

Hoy tengo la respuesta:

El grado medio es el $200$, si todos ellos son más de $100$, estoy hecho, porque solo puedo usar uno de ellos como motor de arranque: $v_1$ e este vértice tiene al menos $99$ vecinos. Elegir uno de ellos(no $v_1$), que se $v_2$, este tiene al menos $98$, y así sucesivamente, de esta manera, tengo mi $100$-largo de la ruta.

Si algunos de los títulos son inferiores a $100$, eliminarlos de la gráfica hasta que todos los grados son más de $100$. El gráfico no quede vacío ya que el promedio es $200$. Puedo usar lo he demostrado anteriormente para el resto de la gráfica.