Asunción de que el gráfico está conectado para demostrar el Teorema de Ore

Question

En Wikipedia, el Teorema de Ore dice que si $G$ es un grafo simple finito con $n \ge 3$ vértices y para todos los vértices no adyacentes $u$ y $v$ la suma de sus grados es mayor o igual a $n$ entonces $G$ es hamiltoniano.

En Prueba Wiki este teorema se enuncia casi de la misma manera, pero hay una hipótesis adicional que $G$ debe estar conectado.

Me pregunto cuál de las dos versiones es más precisa.

Parece que esta condición de grado ya implica que el grafo está conectado, por lo tanto, no necesitamos suponerlo.

Entonces, ¿es realmente necesaria esta suposición?

Answer 1

Si un gráfico simple de $n$ vértices es tal que cualquier par de vértices no adyacentes $x$ y $y$ son tales que $\text{deg}(x) + \text{deg}(y) \geq n$ entonces el gráfico es conexo. Así que la condición de conectividad no es necesaria.

Para ver esto, supongamos que el gráfico no está conectado. Entonces hay vértices $x$ y $y$ en diferentes componentes de tamaños $\ell_x$ y $\ell_y$ ( $\ell_x + \ell_y \leq n$ por supuesto). Ahora $x$ y $y$ no son adyacentes, y no que $\text{deg}(x) \leq \ell_x-1$ y $\text{deg}(y) \leq \ell_y - 1$ . Por lo tanto, $$ \text{deg}(x) + \text{deg}(y) \leq \ell_x + \ell_y -2 \leq n -2, $$ que es una contradicción con la condición de Ore.

Answer 2

La suposición de las sumas de grado implica la conectividad.

Para verlo, supongamos lo contrario, es decir $G$ está desconectado pero cada par de vértices no adyacentes tiene una suma de grados de al menos $n$ .

Dejemos que $C_1, C_2$ sean dos componentes conectados de $G$ .
Dejemos que $x \in V(C_1)$ y $y \in V(C_2)$ . Claramente, $x$ y $y$ son no adyacentes.

El grado de $x$ es como máximo $|V(C_1)| - 1$ y la de $y$ es como máximo $|V(C_2)| - 1$ . Porque $C_1$ y $C_2$ son vértices disjuntos, $|V(C_1)| + |V(C_2)| \leq n$ . Pero entonces, $deg(x) + deg(y) \leq |V(C_1)| - 1 + |V(C_2)| - 1 < |V(C_1)| + |V(C_2)| \leq n$ contradiciendo nuestra hipótesis inicial.