MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
There is notable lack of clarity (and capitalization). – Gjergji Zaimi Aug 15 '10 at 4:31
thank you for reading my query. Please advise me on what is unclear.? Isnt the question "does the colorability of planar Hamiltonian graphs imply all planar graphs are colorable" clear? Shall I capitalize all beginings of sentences? – robert carlson Aug 15 '10 at 16:00
I don't see what most of the first paragraph has to do with the question. – HJRW Aug 15 '10 at 17:50
Also, by 'colorable', do you mean '4-colorable'? – HJRW Aug 15 '10 at 17:51
I suppose I should have asked two questions 1)Are all planar Hamiltonian graphs 4 colorable ? 2)If so, then are does this imply all planar graphs are 4 colorable? Then the first paragraph is about reducing Hamiltonian planar graphs to compositions of trees which reduces the first question to the mutual edge colorability of any two trees. (This presupposes you know Taits theorem that 4 coloring faces is equivalent to 3 coloring the edges.) The second question I have not made any real headway on, so I have no discussion , only the question. – robert carlson Aug 16 '10 at 3:47
up vote 6 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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