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