¿Por qué las secuencias de grados del gráfico siempre tienen al menos un número repetido?

Question

¿Por qué las secuencias de grados del gráfico siempre tienen al menos un número repetido?

$(1, 2, 2, 3)$ = Válido, como se puede ver, porque el $2$ se repite.
$(1, 2, 3)$ = No es posible construir un gráfico con porque todos los números son únicos.

Sé que la suma de grados del gráfico debe ser par, pero en este caso, ambos son pares.

Nuestro profesor dijo que tenía que ver con la Combinatoria, pero nunca tocamos ese tema.

EDIT: Los bucles no están permitidos.

Answer 1

Es bastante fácil construir un árbol infinito cuyos vértices tengan grados distintos, por lo que esta observación sólo se aplica a los grafos finitos. También un grafo con un solo vértice y sin aristas no tiene grados repetidos. Así que tenemos que suponer que hay al menos dos vértices.

Si hay dos vértices aislados, entonces hay dos vértices con el mismo grado. Así que un contraejemplo tendría una componente conectada del grafo que contenga al menos dos vértices.

Este componente del gráfico tiene $m\ge 2$ vértices. No tiene vértices de grado $0$ y el grado máximo es $m-1$ . Dado que hay $m$ vértices, y sólo $m-1$ posibilidades para el grado de cada uno, dos vértices deben tener el mismo grado.

Answer 2

Para los gráficos que no son simples es falso generalmente. Ejemplo: $ V = \{1,2,3\}$ , $ E = \{\{1,2\}, \{2,3\}, \{2,3\}\} $ , donde $V$ es el conjunto de vértices y $E$ es el conjunto de aristas. Tenemos $d(1)=1, d(2)=3, d(3)=2$ .