Un gráfico con $n$ vértices tiene grados distintos excepto un grado, digamos $x$ que ocurre dos veces. Encuentre $x$ y probarlo.

Question

Descubro que cuando $n$ es un número impar, entonces $x$ es igual a $\frac{n-1}{2}$ . Cuando $n$ es un número par, entonces $x$ tiene dos valores posibles, uno es $\frac{n}{2}$ y otra es $\frac{n}{2} -1$ . Pero tengo dificultades para demostrarlo.

Answer 1

Pista: debe haber un vértice adyacente a ningún otro (grado $0$ ) o un vértice adyacente a todos los demás (grado $n-1$ ), pero no ambos.

Si se elimina este vértice, el gráfico restante también tiene todos los grados diferentes, excepto uno que aparece dos veces (a menos que sólo quede un vértice). Además, si el vértice eliminado no era adyacente a ningún otro, el grafo restante tiene un vértice adyacente a todos los demás, y viceversa. Esto debería permitirte proceder por inducción.