1
$\begingroup$

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 ...)?

  • 0
    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](http://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html). It has $21$ faces.2012-06-15
  • 0
    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?2012-06-16
  • 0
    as far as I understand it, yes, if they are 3-connected.2012-06-17

1 Answers 1

5

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.

  • 0
    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?2012-06-15
  • 0
    +1 straight answer, @MarioStefanutti if you have other graphs than this, could you add one to your question?2012-06-15
  • 0
    Some graphs I was talking about are in this video: http://www.youtube.com/watch?v=MyEn2B-hAag&feature=g-upl2012-06-15
  • 0
    @draks: Is the only graph with these characteristics a Dodecahedron?2012-06-16
  • 0
    @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.2012-06-17
  • 0
    @Daniel. I'm verifying if all graphs (I have 10980 cases) are all isomorphic and, so far (I tried some random graphs), they all are. Let me check some other cases and I will accept your answer! But now that you made me notice that, it seems intuitive and I am pretty convinced they are. Thanks!2012-06-19
  • 0
    @Daniel. I verified them with Mathematica and all those graphs are isomorphic!2012-06-22