Studying the four color problem, I was analyzing all possible 3-regular planar graphs of 12 faces, with the additional restriction that graphs that have one or more faces with less than 5 edges, are not to be considered.

Note: It counts as a face also the surrounding area (infinite) of the graph

Using a Java program that builds all possible graphs of this kind, I saw that all have an Hamiltonian path, and that this path is very simple to compute using an algorithm I am implementing in Java: Cahit spiral chain algorithm.

The algorithm is:

  • Start from an external vertex
  • Only to choose the second vertex of the path, move on the external cycle clockwise
  • For all the other vertices that define the path, always move left (each vertex has three edges, one is the edge I am coming from, for the other two "left" and "right" are referred to the planar representation of the graph)
  • If moving left, you end up on a already visited vertex, move right

Here is the question:

Is this an obvious observations? Is there a basic theorem that implies the existence of an Hamiltonian path for graphs of this kind (3-regular planar graphs of 12 faces ...)?

  • $\begingroup$ Maybe it might be of interest to you, that the smallest cubic 3-connected planar graph has $38$ vertices, see Barnette-Bosák-Lederberg Graph. It has $21$ faces. $\endgroup$ – draks ... Jun 15 '12 at 12:44
  • $\begingroup$ Hi, draks. Thanks for the answer, but can you help me to understand how does it relate to my question? Does it mean (imply) that all 3-regular graphs with 20 vertices have Hamiltonian paths? $\endgroup$ – Mario Stefanutti Jun 16 '12 at 21:48
  • $\begingroup$ as far as I understand it, yes, if they are 3-connected. $\endgroup$ – draks ... Jun 17 '12 at 9:35

Euler's formula states that

$$V - E + F = 2$$

which holds for any finite, connected, planar graph with $V$ vertices, $E$ edges and $F$ faces. Since each vertex has degree $3$, the total degree is $3V$ and the number of edges is half of this, since each edge contributes $2$ to the total degree. So $$V-\frac{3V}{2}+12 = 2 $$ and therefore: $$ V = 20$$ The total degree is then $3V=60$ and the number of edges is half of this $E=30$. Since each face is made up of at least $5$ edges, each face is made of exactly $5$ edges. The $3$-regular graph with these properties is the Dodecahedron, which is well-known to be Hamiltonian. Indeed, this is the subject of Hamilton's own Icosian game.

  • $\begingroup$ Yes, all these graphs have 20 vertices and 30 edges. One question about your answer. You wrote that "The 3-regular graph with these properties is the Dodecahedron". Yes, but that is just one of the possible graphs, right? $\endgroup$ – Mario Stefanutti Jun 15 '12 at 13:14
  • $\begingroup$ +1 straight answer, @MarioStefanutti if you have other graphs than this, could you add one to your question? $\endgroup$ – draks ... Jun 15 '12 at 14:12
  • $\begingroup$ Some graphs I was talking about are in this video: youtube.com/watch?v=MyEn2B-hAag&feature=g-upl $\endgroup$ – Mario Stefanutti Jun 15 '12 at 17:42
  • $\begingroup$ @draks: Is the only graph with these characteristics a Dodecahedron? $\endgroup$ – Mario Stefanutti Jun 16 '12 at 21:50
  • $\begingroup$ @MarioStefanutti: It seems intuitive that all 3-regular graphs with 20 vertices, 30 edges and 12 pentagonal faces will be isomorphic to the dodecahedron, but I am not sure. $\endgroup$ – Daniel Pietrobon Jun 17 '12 at 8:06

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.