Demostrar/desmentir: En un grafo con al menos un componente que no contenga un circuito hamiltoniano, podemos hacerlo hamiltoriano añadiendo un vértice

Question

Demostrar/desmentir: En un gráfico $G$ con al menos un componente que no contenga un circuito hamiltoniano, podemos añadir un vértice $x$ y ciertas aristas que lo conectan con ciertos vértices del grafo, de forma que obtenemos un grafo en el que cada componente del mismo tiene un circuito hamiltoniano.

Mi respuesta fue:

Desmentir. Tomemos por ejemplo el grafo de la garra con 3 vértices. Cualquier adición de $x$ y ciertas aristas no harán un circuito hamiltoniano. (sí hace un camino hamiltoniano, pero no un circuito).

¿Es eso correcto o me estoy perdiendo algo?

Answer 1

No sé a qué te refieres con "gráfico de garras con 3 vértices". Si te refieres a $P_3$ o $K_{1,2}$ entonces sí podemos hacer un circuito hamiltoniano, creando un cuadrado. Si te refieres a $K_{1,3}$ entonces tu ejemplo es correcto pero tu prueba es incompleta. Sólo puede ayudar (en términos de producir un circuito hamiltoniano) conectar $x$ a cada vértice de $K_{1,3}$ . Consideremos los tres vértices de grado 2 resultantes. Cada camino de uno a otro debe pasar por $x$ o el otro vértice de grado 4. Pero en un circuito hamiltoniano hay que poder ir de cada uno al siguiente (tres caminos) que no se cruzan. Contradicción.

Errores/omisiones específicas en la solución del OP:

1. No se discute qué aristas se añaden a $x$ excepto la afirmación general y sin fundamento "cualquier".

2. No justifica por qué tal adición no hará un circuito hamiltoniano, o por qué hará un camino hamiltoniano.

3. Utiliza el término no estándar "grafo de garras con 3 vértices" para $K_{1,3}$ (que tiene 4 vértices).