Sugerencia para una teoría de grafos problema (el suficiente criterio para un gráfico simple para ser conectado)

Question

Alguien puede darme una pista de cómo probar la siguiente : Vamos a $G$ ser un simple gráfico con $n$ vértices, que tiene la propiedad de que la suma de los grados de cualquiera de los dos vértices que no son adyacentes, es $n-1$. A continuación, $G$ está conectado.

Answer 1

Tomar cualquiera de los dos vértices $v$ $w$ que no son adyacentes. Hay $n-2$ otros vértices en la gráfica. Desde $deg(v)+deg(w)=n-1$, por pigeon-hole principio $v$ $w$ tienen en común un vecino. Así, en este gráfico hay un camino de longitud 2 de unirse a cualquier no-adyacentes pares de vértices. Por lo tanto está conectado.