La secuencia de grados de un gráfico tiene entradas repetidas

Question

Estoy tratando de mantener mi teoría de grafos habilidades. Yo no he hecho ninguna en más de 4 años y estoy oxidado...Si alguien me pudiera ayudar con esta simple prueba, yo estaría muy agradecido.

Demostrar que para cualquier gráfico de $G$ de orden al menos 2, el grado de secuencia tiene al menos un par de entradas repetidas.

Así que el grado de secuencia si una lista de los grados de cada vértice (normalmente escrito en orden descendente).

Sé que la suma de los grados de los vértices de un grafo es igual a$2|E|$, y que el número de vértices de grado impar es par.

Si alguien me pudiera ayudar y me apunte en la dirección correcta, yo estaría muy agradecido.

Answer 1

Sí, me llegó después de que publiqué el comentario en la respuesta anterior.

Una gráfica con al menos 2 vértices y sin aristas el grado 0 se repite. En una gráfica con 2 vértices y 1 borde se repite el grado 1. Cada vértice tiene al menos una entrada en la secuencia de grados, por lo que hay un total de$N$ entradas. Pero cada grado puede tener un máximo de grado =$N-1$. Por lo tanto, según el principio del casillero, al menos uno de los grados debe repetirse.

Answer 2

Si no hubiera repeticiones, ¿cómo sería la secuencia de grados? ¿Por qué no podría verse así?