Un gráfico con casi todos los grados diferentes

Question

Es cierto que para cada $n\geq 3$ uno puede encontrar un grafo grpah, sin bucles o doble los bordes, en $n$ vértices de tal manera que no se $n-1$ vértices, todos con diferentes grados? (Claramente no puede ser $n$ diferentes grados por el principio del palomar).
Gracias por la ayuda.

Answer 1

Usted puede introducir. Deje $G_n$ ser una gráfica de $n$ vértices; entonces, su palomar argumento muestra que el $G_n$ tiene un vértice de grado $n-1$ o un vértice de grado $0$, pero no tanto. También, su complemento $\tilde{G_n}$ es otro ejemplo del gráfico, que tiene un vértice de grado $0$ fib $G_n$ no. Así que podemos suponer sin pérdida de generalidad que $G_n$ no tiene ningún vértice de grado $0$. Pero entonces la unión de $G_n$ con un vértice aislado es una gráfica de $n+1$ vértices.

Answer 2

Si $n$ es impar comienzan con un camino de longitud $2$ lo contrario comenzar con un solo borde. En cada paso, agregar dos vértices y conectar uno de ellos a todos los demás vértices hasta que se tiene el gráfico de $n$ vértices y tendrá la propiedad deseada.