Gráfico con la condición de que cada vértice esté conectado al menos a n otros vértices.

Question

Problema: (Adrian Tang)

$G$ es un gráfico con $2n+1$ vértices. En $G$ para cada conjunto $S$ de a lo sumo $n$ vértices, hay un vértice fuera de $S$ que es adyacente a cada vértice en $S$ .

Demuestra que al menos un vértice es adyacente a cada uno de los otros vértices.

Mi enfoque: asumir por contradicción que el vértice de mayor grado no tiene grado $2n$ . Hay algo en su vecindario que despierta la contradicción de que hay un vértice con un grado superior.

Answer 1

Digamos que un gráfico $M$ es completa si cada vértice de $M$ está conectado a cada vértice $M$ . Obsérvese que dicho gráfico existe (digamos que con $2$ vértices).

Tomar el subgrafo completo máximo $M$ . Si el tamaño de este gráfico $M$ es $k\leq n$ entonces hay algún vértice conectado a cada vértice en $M$ . Así que podemos añadirlo a este gráfico y obtendremos un nuevo gráfico completo $M'$ que es mayor que $M$ . Una contradicción. Así que $M$ es de tamaño $k\geq n+1$ . Entonces en $M^C$ tenemos como máximo $n$ vértices, por lo que hay algún vértice en $M$ que está conectado a todos los in $M^C$ . Pero entonces éste está conectado a cada vértice.