Un gráfico con $n+1$ vértices y un vértice de cada grado $1\dots n$

Question

Dejemos que $G$ sea un gráfico con $n+1$ vértices. Supongamos que para cada $i=1,\ldots,n$ hay un vértice en $G$ de grado $i$ . ¿Cuál es el grado del otro vértice (es decir, qué grado se repite)?

Sé que si $n$ es par el grado del otro vértice es $\dfrac{n}{2}$ . Si $n$ es impar el grado del otro vértice es $\dfrac{n+1}{2}$ . Me dan la prueba de que el grado repetido no era $\dfrac{n}{2}$ o $\dfrac{n+1}{2}$ pero es muy grande. Puedo hacerlo de forma más compacta?

Answer 1

Dejemos que $u,v$ sean los vértices de grado $n$ y $1$ . Entonces $u$ está conectado a todos los vértices y en particular a $v$ .

Entonces, borrando $u$ y $v$ se obtiene un nuevo gráfico con $n-1$ vértices, donde todos los demás $n-1$ grados se redujo exactamente en $1$ . Así, en el nuevo gráfico los grados son $1,2,3,..., n-2$ y $??$ ...

Esto sugiere la inducción y esto es en realidad la prueba de $P(n) \Rightarrow P(n+2)$ .

Ahora: Comprueba la fórmula de $n=1$ y luego por inducción $P(n)\Rightarrow P(n+2)$ demuestras tu fórmula para todos los enteros Impares.

$n=2$ y la inducción lo demuestra para los pares. Esta prueba, además, explica un poco por qué se obtienen diferentes fórmulas para impar/par...

P.D. Borrar el vértice más grande es en realidad exactamente el algoritmo del teorema de Hakimi-Havel, si estás familiarizado con él puedes intentar reescribir la prueba usando ese Teorema, pero la inducción es probablemente más clara y sencilla.