Demostrar la existencia de un grafo que no contenga tres vértices con el mismo grado.

Question

Demostrar que para cualquier $n \ge 3$ con $n \in \mathbb{N}$ Hay un $G$ gráfico con $n$ vértices, que no contiene tres vértices con el mismo grado.

Empecé con la inducción por $n$ .

Para $n=3$ podemos tomar vértices $\{a,b,c\}$ y bordes $e_1 = ab, e_2 = ac$

Ahora bien, suponiendo que sea válido para $n$ Debemos mostrarlo para $n+1$ . He intentado separar dos casos.

• Caso 1:

  si hay un vértice con algún grado, entonces también hay otro (el gráfico contiene dos vértices con el mismo grado), y al añadir un nuevo vértice, sólo se añadirán aristas de mayor grado + 1

• Caso 2:

  Cuando hay al menos un vértice, con grado único, y el nuevo vértice se conectará con aristas, tanto como tenga vértice con grado único.

Pero parece que está mal. Cualquier consejo o ayuda es bienvenida.

Answer 1

Podemos considerar una construcción especial para esta cuestión. En primer lugar, explicaré cómo podemos construir dicho gráfico en el caso general (para $n$ ) y luego dar algunos ejemplos para hacerlo más concreto.

Supongamos que tenemos $n$ vértices. A continuación, ponlos en línea y nómbralos como $x_1, x_2, ..., x_n$ . Después de eso;

• Conectar $x_1$ a cada vértice hasta $x_n$ ( $x_n$ incluido). Así que tenemos $d(x_1) = n-1$ .

• Conectar $x_2$ a cualquier otro vértice hasta $x_{n-1}$ (incluido de nuevo). Así que tenemos $d(x_2) = n-2$

Siguiendo así, ya que $x_n$ tendrá una sola conexión a lo largo de este proceso, tenemos $d(x_n) = 1$ y de manera similar $d(x_{n-1}) = 2$ y así sucesivamente. Ahora tenemos que encontrar cuando este proceso se detendrá.

Obsérvese que mientras estamos incrementando el índice del vértice de $x_1$ lado, también disminuimos el índice del vértice de $x_n$ lado. Así que podemos decir que el proceso debe detenerse después de $\lfloor n/2 \rfloor$ pasos. Observe también que después de $i^{th}$ paso, ciertamente tenemos dos vértices con grados $n-i$ y $i$ , donde $i \le \lfloor n/2 \rfloor$ .

Ahora, cuando $n$ es incluso, después de $n/2$ pasos, tendremos dos vértices con el mismo grado, que es $n-n/2 = n/2$ . Todos los demás vértices tendrán grados distintos $n/2-1$ , $n/2+1$ , $n/2-2$ , $n/2+2$ , ..., $n-1$ , $1$ .

Cuando $n$ es impar, primero $(n-1)/2$ y por último $(n-1)/2$ vértices tienen grados distintos, de forma similar, por lo que nos queda un vértice cuyo grado no se conoce. Sin embargo, aunque sea igual que uno de los otros grados, podemos tener como máximo dos vértices con el mismo grado, así que hemos terminado.

Este es un ejemplo de construcción para $n = 7$ . Para entender cómo se realiza la construcción, ¿podría construir además los gráficos para $n = 8$ y $n = 9$ ?

SUGERENCIA: Puedes añadir nuevos vértices al final de la construcción que he hecho para ti. Entonces sólo tendrás que hacer algunas conexiones adicionales sin cambiar las actuales para construir un grafo con sólo dos vértices con el mismo grado.

Answer 2

Dejemos que $\Psi(n)$ sea la declaración

Existe un grafo simple no dirigido con $n$ vértices tales que para cada $k$ el gráfico
tiene como máximo dos vértices de grado $k$ .

Dejemos que $\Phi(n,d)$ sea la declaración

Existe un grafo simple no dirigido $G=G(n,d)$ con $n$ vértices con un vértice especial $v$ y las siguientes propiedades:

• Como máximo cuatro vértices tienen grado $d$
• Para $k\ne d$ , a lo sumo dos vértices tienen grado $k$
• $\deg v=d$
• Si $u$ es vecino de $v$ entonces $\deg u\le d$
• Como máximo un vecino de $v$ tiene grado $d$ .

Tenga en cuenta que $\Phi(n,d)$ implica $\Psi(n)$ si $d\ge n$ porque los grados no pueden superar $n-1$ .

Lema 1. Si $\Phi(n,d)$ entonces $\Phi(n,d+1)\lor\Psi(n)$ .

Prueba. Supongamos que $\Phi(n,d)$ y $\neg \Psi(n)$ . Considere $G(n,d)$ con vértice especial $v$ . Como $\Psi(n)$ es falso, $G(n,d)$ debe tener al menos tres vértices de grado $d$ . Uno de ellos es $v$ a lo sumo otro es vecino de $v$ . de ahí que podamos encontrar $w$ con $\deg w=d$ que no es ni $v$ ni un vecino de $v$ . Dejemos que $G(n,d+1)$ sea $G(n,d)$ con borde $vw$ añadido.

• Los únicos vértices posibles de grado $d+1$ son $v,w$ y hasta dos vértices de grado $d+1$ en $G(n,d)$
• Como $v,w$ ya no tiene título $d$ , a lo sumo dos vértices tienen grado $d$ . Para $k\ne d,d+1$ seguimos teniendo como máximo dos vértices de grado $k$ .
• $\deg v=d+1$ debido al borde adicional
• $\deg u\le d<d+1$ para todos los vecinos "antiguos" de $v$ y $\deg w=d$ para el nuevo vecino

$\square$

Lema 2. Si $\Psi(n)$ entonces $\Phi(n+1,0)$ .

Prueba. Dado un gráfico descrito por $\Psi(n)$ añadir un nuevo vértice $v$ sin aristas y llamamos al gráfico resultante $G(n,0)$ . Los cinco puntos se verifican fácilmente: Como máximo tres vértices tienen grado $0$ para $k>0$ , a lo sumo dos vértices tienen grado $k$ ; $\deg v=0$ ; afirmaciones sobre $v$ de los vecinos son vacuamente ciertas. $\square$

Utilizando el lema 1 y la inducción en $d$ vemos que $$ \Phi(n,0)\implies \Psi(n)\qquad\text{for all }n.$$ Junto con el lema 2, esto nos da $$ \Psi(n)\implies \Psi(n+1)\qquad\text{for all }n$$ de manera que (partiendo de la verdad trivial $\Psi(1)$ ) obtenemos $$ \Psi(n)\qquad\text{for all }n$$ por inducción.

Answer 3

A menos que se dé la propiedad adicional de que los gráficos son simple la prueba es trivial.

Etiqueta todos los vértices con un único número natural. Crea tantos bucles de cada vértice a sí mismo, como su número de etiqueta.

El grado es entonces el doble del número de etiqueta, y estos son únicos, por lo que los grados son únicos, por lo que nunca hay dos o más vértices con el mismo grado.