¿Ejemplo trivial de una triangulación planar no hamiltoniano?

Question

Estoy buscando un ejemplo simple (o mejor aún, un mínimo) de una triangulación planar que sería "obviamente" no hamiltoniano.

¡Gracias de antemano!

Answer 1

Si uno empieza con un gráfico que tiene más caras que los vértices (cuyas caras son triángulos), por ejemplo, la gráfica de la octaedro, y construye una pirámide en cada cara, se obtiene un gráfico cuyas caras son triángulos y que no se puede tener un circuito hamiltoniano.

Este proceso de trabajo para la construcción de la no-hamiltonianos polytopes en las dimensiones superiores, y es a veces conocido como un Kleetope porque Victor Klee, llamó la atención de esta idea.

Answer 2

Usted podría estar interesado en el siguiente Teorema de Whitney: Let $G$ ser un gráfico planar cuyas caras son triángulos (incluyendo la cara exterior). Supongamos que $G$ tiene ninguna lazos, sin aristas múltiples y cada ciclo $3$ de $G$ límites a la cara. $G$ Tiene un ciclo hamiltoniano.

Tenga en cuenta que el ejemplo de Joseph Malkevitch viola la condición en negrita.

Answer 3

Esto parece ser mínima: