¿Un ejemplo de grafo conexo con vértices de al menos 3 grados, pero no hamiltoniano?

Question

La cuestión es:

¿Existe un grafo simple conexo no dirigido $G$ con $7$ vértices de grado mínimo $3$ pero no contiene ningún ciclo hamiltoniano?

Llevo mucho tiempo intentando encontrar un ejemplo, pero aún no se me ocurre ninguno. La restricción "grado mínimo 3" me está dando un dolor de cabeza, ya que siempre puedo encontrar un gráfico con ciclo no hamiltoniano con "grado casi mínimo 3", pero cada vez que se añade una arista para satisfacer la condición, se convierte en hamiltoniano...

Así que viene la pregunta. ¿Existe algún gráfico con las propiedades anteriores? Puede que esté siendo poco imaginativo, pero hasta ahora me ha resultado bastante difícil encontrar grafos no hamiltonianos con ciertas propiedades.

Sería genial que explicaras también tu estrategia con un ejemplo, ya que parece que me falta lo necesario en este tipo de ejercicios: No consigo "sentirlo".

Gracias de antemano,

Answer 1

Tomemos dos copias de $K_4$ y contrae un vértice de cada copia.

Más exactamente, $G=(V,E)$ donde $V=\{1,\dots,7\}$ , $E=\{\{u,v\}\mid u\neq v, u,v\in\{1,2,3,4\}\}\cup\{\{u,v\}\mid u\neq v, u,v\in\{4,5,6,7\}\}.$

Si además exigimos que no tenga ningún vértice de corte, podemos considerar $G=(V,E)$ donde $V=\{1,\dots,7\}$ , $E=\{\{1,2\},\{2,3\},\dots,\{5,6\},\{6,1\}\}\cup\{\{1,3\},\{2,4\},\{3,6\}\}\cup\{\{1,7\},\{3,7\},\{5,7\}\}$ .