Matemáticas discretas; teoría de grafos no dirigidos

Question

Sea G un grafo no dirigido de 4 vértices y sin bucles (es decir, flechas hacia sí mismo). ¿Cuál de las siguientes afirmaciones se garantiza que es verdadera?

1) G tiene al menos dos vértices del mismo grado

2) G tiene una trayectoria de Hamilton

3) Entre dos vértices distintos hay un camino simple

4) G tiene una trayectoria de Euler

La respuesta es aparentemente la 3), y no la 1). No puedo dibujar un gráfico sin al menos dos vértices del mismo grado que sea no dirigido con 4 vértices y sin bucles.

Es posible que se haya perdido la terminología exacta, ya que lo he traducido del noruego.

Salud.

Answer 1

Podemos demostrar (1) por el principio de encasillamiento. Los posibles grados de cada vértice son 0,1,2,3. Si dos son iguales, hemos terminado. Si no, hay uno de cada grado; sin embargo, el vértice de grado 3 debe tener una arista hacia cada uno de los otros, incluyendo el vértice de grado 0. Esto es una contradicción.