[JorgeFC]

Tengo que probar lo siguiente:

Si en un grafo simple de n vértices, cada uno tiene grado mayor o igual a \( \displaystyle\frac{n-1}{2} \), entonces el grafo es conexo.

He intentado probarlo por inducción, pero no he sido capaz de concluir el resultado.

[Luis Fuentes]

Hola

Tengo que probar lo siguiente:

Si en un grafo simple de n vértices, cada uno tiene grado mayor o igual a \( \displaystyle\frac{n-1}{2} \), entonces el grafo es conexo.

He intentado probarlo por inducción, pero no he sido capaz de concluir el resultado.

Si no es conexo al menos tiene dos componentes conexas con \( a,b \) vértices cada una y \( a+b\leq n \). Entonces o bien \( a\leq n/2 \) o bien \( b\leq n/2 \). Sin pérdida de generalidad suponemos \( a\leq n/2 \). Los vértices de esa compoenente conexa a lo sumo tienen grado \( a-1\leq \dfrac{n}{2}-1=\dfrac{n-2}{2} \), lo cuál contradice la hipótesis.

Saludos.