2
$\begingroup$

Lets define polygonal triangulation a triangulation which has a hamiltonian cycle.

It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable.

Is any 3-colorable triangulation also polygonal triangulation? In other words, is any 3-colorable maximal planar graph hamiltonian?

$\endgroup$
11
$\begingroup$

You seem to be confusing two concepts: triangulations of simple polygons are maximal outerplanar graphs (and every maximal outerplanar graph is Hamiltonian); maximal planar graphs are something else.

But anyway: no.

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

For an example of an Eulerian maximal planar graph that is not Hamiltonian, glue nine octahedra together: one in the center and one attached to each of its faces. The dihedral angle of a regular octahedron is less than 120 degrees so there's plenty of room to do this without even having to distort anything.

If the graph of this polyhedron could have a Hamiltonian cycle, then it would visit the central octahedron's six vertices in an order that is also a Hamiltonian cycle, together with six paths connecting those six vertices. But each of those six paths can only visit one of the eight side octahedra that are glued onto the center, so two of the side octahedra must remain unvisited, contradicting the Hamiltonicity of the cycle.

$\endgroup$
2
$\begingroup$

(This really is a comment on the prior answer.)

If one has a maximal plane graph where all of the 3-circuits bound faces then the graph has a hamiltonian circuit by a theorem due to Hassler Whitney. Whitney's Theorem is a special case of Tutte's Theorem that every planar 4-connected graph has a hamiltonian circuit. If one starts with a maximal planar graph which has more faces than vertices (the graph of the regular octahedron for example) and erects a "pyramid" on each face, then the resulting graph will have no hamiltonian circuit. This "trick" (sometimes called constructing the Kleetope) was used by Victor Klee in a similar fashion on higher dimensional polytopes (erecting pyramids on the facets) to construct non-hamiltonian d-polytopes.

$\endgroup$
  • $\begingroup$ It's really the same trick, as you say, but the usual Kleetope has a degree-three vertex at each pyramid tip; that's why I used octahedra instead. The point is that to destroy Hamiltonicity it doesn't matter what you replace each face with, so you can make that choice in a way that preserves the even vertex degrees. $\endgroup$ – David Eppstein Sep 14 '10 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.