Are all Hamiltonian planar graphs are 4 colorable? Does this imply all planar graphs are colorable?

Question

Planar graphs with a Hamiltonian loop connecting all faces do not necessarily have a Hamiltonian on their edges, which would make a 3 edge coloring and thus a 4 face coloring easy. However they have a lot of great structure. If you split the graph along the face Hamiltonian using it like an equator,the edges in the northern or southern hemisphere form trees. Thus the problem of coloring Hamiltonian planar graphs with n faces reduces to finding a mutual edge 3 coloring of any two n trees.

Regarding the Hamiltonian graphs as compositions of trees makes them easily counted, and gives a relation between graphs by relating their trees.

Between trees of the same size: Any tree of size n may converted into another of size n by iterated diamond switches, DS, of internal branches. I have proven any n-tree can be converted into any other n-tree in less than 2n DS. Nicely, if 2 trees are within n DS they have a mutual coloring.

Between trees of different sizes: Larger and smaller Hamiltonian graphs can be made by adding or subtracting branches that cross the equator, preserving the Hamiltonian loop. So inductive proofs are encouraged.

Also any tree of n roots has exactly 2^(n-3) colorings , which can be arranged on a hypercube, so you could prove all Hamiltonian graphs with n faces are colorable by proving any two color-hypercubes of n-trees intersect.

Hamiltonian graphs are a good restricted simpler group of graphs to try to prove colorable, interesting in their own right. They are even more important if their colorability implies the colorability of all planar graphs. Is it so?

Answer 1

If $G$ is a graph all of whose faces are triangles, and $G'$ is its dual, then recall that $G$ is $4$-vertex-colorable if and only if $G'$ is $3$-edge-colorable. It is unclear whether you are asking about the situation of $G$ or of $G'$ having a Hamiltonian cycle. As far as I know (but I am not a graph theorist), there is no relation between these two conditions.

Whitney's theorem says that, modulo some minor hypotheses, $G$ has a Hamiltonian cycle. Specifically:

Whitney's Theorem: Let $G$ be a planar graph all of whose faces are triangles. Suppose that $G$ contains no loops, no multiple edges, and no $3$-cycles which are not faces. Then $G$ has a Hamiltonian cycle.

$4$-colorability for graphs that meet the hypotheses of Whitney's theorem easily implies $4$-colorability of all planar graphs.

If $G'$ has a Hamiltonian cycle, then $G'$ is trivially $3$-edge-colorable. Graphs of the form $G'$ tend to be Hamiltonian. This is true both rigorously -- Hamiltonian graphs have density approaching $1$ among cubic graphs with $n$ labeled vertices (see Robinson and Wormwald) and as a statement about common experience -- the smallest counter-examples have about 36 vertices and are not obvious. MathSciNet recommends this survey for more on Hamiltonianicity of cubic graphs.