Si $G$ es un gráfico simple de $7$ vértices cuyos grados de vértice son $2,2,2,2,2,3,3$ ¿es un gráfico hamiltoniano? ¿Existe un grafo simple no hamiltoniano con $7$ vértices cuyos grados de vértice son $2,2,2,2,2,3,3$ ?
La única forma completa de determinar si un gráfico es hamiltoniano que he encontrado es la Teorema de Bondy-Chvatal . Según este teorema, dejemos que $d_i$ sea el grado del vértice $v_i\in V$ .
Entonces: $$ d_1=2>1\\d_2=2\le2 \quad\land\quad d_{7-2=5}=2<5 $$ por lo tanto, según el teorema anterior, el gráfico no es hamiltoniano.
Pero la segunda pregunta se refiere a si existe algún grafo simple con dicha secuencia. Pero según el lema de Handshaking: $$ \sum_{v\in V}\deg(v)=2\cdot |E|\implies |E|=16/2=8. $$ ¿Pero no es que en cualquier grafo simple el número de vértices es siempre mayor que el número de aristas? Si es así, nuestro grafo no existe porque tiene $8$ bordes pero $7$ vértices.
Creo que hay alguna trampa en la pregunta, porque si mi respuesta a la segunda parte es correcta, ¿por qué me preguntan si existe ese gráfico hamiltoniano si el gráfico en sí no es posible?
También tengo una micropregunta sobre el teorema de Bondy-Chvatal que dice que para la secuencia de grados $d_1\le d_2\le ...\le d_n$ si no $m<n/2$ existe tal que $d_m\le m$ y $d_{n-m}<n-m$ entonces el gráfico hamiltoniano es posible. ¿Y si $n$ ¿es impar? Es $m=\lceil n/2 \rceil$ ¿entonces?
