Sea G un grafo con n vértices donde cada vértice tiene un grado de al menos n/2. Demostrar que G es conexo.

Question

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.

Answer 1

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.