(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):


* Images of these graphs are here: <http://4coloring.wordpress.com/2013/01/26/four-color-theorem-simplified-maps-and-fullerenes/>



Question about 3-regular graphs with a restriction (also fullerene and four color theorem)
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


<https://oeis.org/A081621>


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


