Demostrar que para todo n≥2n≥2n\geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos.

El reclamo tal como está escrito actualmente " por cada$n\geq 2$existe un$n$-el grafo simple de vértices cuyos vértices tienen grados distintos " es falso y puede verse como falso a modo de contraejemplo. Podemos describir muy rápida y fácilmente cada grafo en dos vértices hasta el isomorfismo.

* *y*----*

La secuencia de grados de la primera es (0,0) y la de la segunda es (1,1), ninguna de las cuales satisface la reivindicación.

Una pregunta más interesante y desafiante, y muy probablemente la pregunta que debería intentar probar es que, de hecho, nunca es posible encontrar una gráfica de este tipo para cualquier$n$. Eso es:

Para cada gráfico simple en$n\geq 2$vértices debe haber al menos dos vértices en el gráfico con el mismo grado.

Para acercarse tenga en cuenta las siguientes cosas:

• Ignorando todo lo demás sobre el gráfico excepto el número de vértices$n$, mirando un vértice individual, ¿cuáles son los valores posibles para su grado?

$0,1,2,\dots,n-1$, entonces hay$n$opciones

• Si hay un vértice aislado en el grafo, ¿hay alguno de esos grados antes mencionados que ahora son imposibles? ¿Cuántos grados son posibles teniendo eso en cuenta entonces?

¿Puede haber un vértice de grado cero y un vértice de grado$n-1$en el mismo gráfico con$n$vértices? El vértice de grado cero no está junto a ningún otro vértice excepto el grado$n-1$vértice está al lado de todos los demás vértice incluyendo el grado cero uno...

• Si no hay un vértice aislado en el grafo, ¿hay alguno de esos grados antes mencionados que ahora son imposibles? ¿Cuántos grados son posibles teniendo eso en cuenta entonces?

Si no hay vértices aislados, no hay vértices de grado cero...

Use estas observaciones junto con el principio del casillero para llegar a una conclusión.

A modo de ejemplo, considere un gráfico simple con$5$vértices. El grado máximo en tal gráfico sería$4$, si un vértice estuviera conectado a todos los demás vértices. El grado mínimo sería$0$, para un vértice que no está conectado a ningún otro (un vértice aislado). Entonces consideramos el rango$[0,4]$y de hecho hay$5$enteros distintos. Sin embargo, tenga en cuenta que los valores mínimo y máximo calculados no pueden existir en el mismo gráfico: no puede haber un vértice conectado a todos los demás y también un vértice conectado a ninguno de los demás. Entonces, el número máximo de valores de grados distintos no es más que$4$y así - por el siempre útil principio del casillero - al menos dos de los$5$los vértices deben tener el mismo grado.

No es difícil ver cómo se aplica esto a un gráfico con cualquier número de vértices (te lo dejo a ti). Siempre debe haber dos vértices con el mismo grado en un gráfico simple.