Demuestra que existe un ciclo de 4 en un grafo con 100 vértices, cada uno con un grado de al menos 50

Question

Espero haber escrito bien la pregunta ya que es mi intento de traducir del libro. Si no es lo suficientemente claro, La pregunta dice que en cada gráfico como se describe en el título de un ciclo simple de longitud 4 existe.

Perdón por mi inglés y gracias de antemano por la ayuda.

Answer 1

Es evidente que existe un ciclo hamiltoniano, digamos $abc....a$ . [desde, $\delta(G) \geq n/2$ (Aunque esto no es necesario, fue lo primero que se me ocurrió).

Si $G$ es un gráfico completo, ya ha terminado, puesto que $G$ tiene $k$ -ciclos para $k=3,4,...,100$ . Si no $G$ tiene un triplete $abc$ que es un camino.

Ahora considere este camino $abc$ ya que $deg(a)$ y $deg(c)$ es superior a 50, necesitamos al menos 49 vértices (excepto $b$ ) sean vecinos de $a$ y para $c$ por lo que un total de $98$ vértices. Pero ya hemos agotado $3$ vértices, por lo que se quedan con 97 vértices más. Por tanto, existe un vértice $d \neq b$ que es común en $nbd(a)$ y $nbd(c)$ .

Así que $abcda$ es un ciclo de cuatro. De hecho para cada camino inducido $abc$ tenemos un 4 tiempos.

Answer 2

Podemos suponer que el gráfico no está completo. Elegimos dos vértices no adyacentes $u$ y $v$ . Ahora $N(u)$ y $N(v)$ son $50$ -subconjuntos de elementos del $98$ -conjunto de elementos $V(G)\setminus\{u,v\}$ Así que $$|N(u)\cap N(v)|=|N(u)|+|N(v)|-|N(u)\cup N(v)|\ge50+50-98=2.$$ Así que $u$ y $v$ y sus dos vecinos comunes forman un subgrafo $K_{2,2}=C_4$ en $G$ .