MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

(Crossposted from math.stackexchange.)

Studying all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (computer program) that many hypothetically possible graphs, that by Euler's identity may exist ($F5 = 12 + F7 + 2F8 + 3F9 + ...$), do not actually exist. Using a VF2 algorithm to filter out isomorphic maps being created, I also noticed that not so many graphs as I expected exist. And that one general category of graphs, that always represents a simplified 3-regular graph, is that of fullerenes (with 12 faces F5 and an arbitrary number of F6). Here is a list of what I found, so far, for each class of graphs, from 12 faces to 20 faces (surrounding area included).

The question is: Since the computation of maps with 17, 18, 19, 20 faces (simplified and not containing isomorphic graphs) it is taking very long time (days of CPU time on a PC), is this sequence already known?

  • 12 faces: 1 (only 1 graph exists)
    • On 3 dimensional space (sphere) it is a dodecahedron
    • It is a fullerene: 20-fullerene dodecahedral graph
  • 13 faces: 0 (no simplified graphs exist with 13 faces)
    • The hypothetical (by Euler's identity) map of 12 F5 and 1 F6 does not exist
  • 14 faces: 1 (12 F5 + 2 F6)
    • The hypothetical (by Euler's identity) map of 13 F5 and 1 F7 does not exist
    • It is a fullerene: GP (12,2) Generalized Petersen graph
  • 15 faces: 1 (12 F5 + 3 F6)
    • The hypothetical (by Euler's identity) map of 14 F5 and 1 F8 does not exist
    • It is a fullerene: 26-Fullerene
  • 16 faces: 3 (Two graphs are 12 F5 + 4 F6. The other has 14 F5 + 2 F7)
    • The hypothetical (by Euler's identity) map of 14 F5 and 2 F7 does exists
    • The other two are fullerenes
  • 17 faces: ???
  • 18 faces: ???
  • 19 faces: ???
  • 20 faces: ???

ADD (28/Jan/2013):

share|cite|improve this question
The question was… – Gerry Myerson Jan 29 '13 at 4:32
up vote 7 down vote accepted

Use Brinkmann & McKay's program "plantri"...

You will discover that there are

3 on 16 faces (as you said), 4 on 17 faces, 12 on 18 faces, 23 on 19 faces, 73 on 20 faces

and then going to Sloane's online encylopaedia you discover

So in short, the answer to your question is "yes, the sequence is fairly well known".

share|cite|improve this answer
Thanks. So fast! I'm going to try this program right away. – Mario Stefanutti Jan 29 '13 at 9:58
Thanks again. Plantri is really a great program and it is so fast. Where my program takes 1 minute to elaborate all graphs of 15 faces, Plantri is istantaneous. – Mario Stefanutti Feb 8 '13 at 22:20

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.