Estoy tratando de demostrar esto por contradicción. Por lo tanto, estoy asumiendo que el gráfico no está conectado. Pero incluso si el gráfico no está conectado, creo que todavía tendrá n/2 vértices grado. Me resulta difícil demostrarlo de esta manera.
Respuesta
¿Demasiados anuncios?
Supongamos un gráfico $G$ con la mencionada propiedad no está conectada. Por lo tanto, se puede dividir en (al menos) 2 componentes conectados, llámese $G_1$ y $G_2$ . Ambos subgrafos deben satisfacer la propiedad de que cada vértice tenga grado $n/2$ al menos, y como no hay aristas entre los vértices de $G_1$ y $G_2$ el número de vértices en ambos $G_1$ y $G_2$ debe ser como mínimo $n/2$ para que coincida con el requisito.
Ahora observe que si $n=2k+1$ entonces al menos $n/2$ significa que ambos $G_1$ y $G_2$ debe tener al menos $k+1$ vértices pero que suman un total de $2k+2 = n+1$ para $G$ que es una contradicción. Del mismo modo, para $n=2k$ ambos $G_1$ y $G_2$ deben tener al menos $k + 1 $ vértices para que cada vértice tenga al menos un grado $k$ . Así, el número total de vértices en $G$ se convierte en $k+1 + k+1 = n+2$ que es una contradicción.
