# Restrictions on the faces of a $3$-regular planar graph

I'm new here and I'm having difficulty with this graph theory question.

Suppose $G$ is a connected $3$-regular planar graph which has a planar embedding such that every face has degree either $5$ or $6$. I need to prove that $G$ has precisely $12$ faces of degree $5$.

I know that a $3$-regular graph is a graph where all the vertices are of degree $3$ and that a planar embedding is a graph that has no edges crossing.

-
You'll also need to know something relating faces, edges, and vertices... –  Erick Wong Nov 17 '12 at 1:51
Hi I was analyzing something similar and I think these may interest you. Search ("Simplified maps of 13 faces do not exist!") whithin this page: 4coloring.wordpress.com/open-points-and-notes and read this other question: math.stackexchange.com/questions/158620/… –  Mario Stefanutti Nov 17 '12 at 16:11

Hint: Let $G(V,\ E)$ satisfy $|V| = n$ and $|E| = m$. Then from Euler's formula we have $$n - m + f = 2$$ Let $f_5$ and $f_6$ denote the number of degree $5$ and $6$ faces respectively. Now apply the Handshaking lemma to relate both the number of vertices and the faces of each degree to the number of edges. Substitute the resulting relations into Euler's formula and see what you get.

-

This very interesting class of graphs is known as the fullerenes. You can find out more about them here: http://en.wikipedia.org/wiki/Fullerene

-
This isn't an answer to the question. –  Graphth Nov 17 '12 at 3:02

The Euler identity for polyhedron:

$$V-E+F=2$$

can be transformed into this (see the details below):

$$F_5+0F_6=12+F_7+2F_8+3F_9+\cdots$$

and for graphs with all faces with degree 5 or 6, it becomes:

$$F_5+0F_6=12$$

If you check the equilibrium of the identify, since $F_6$ face do not influence the equilibrium, a graph is forced to have 12 pentagonal faces and an indefinite number of $F_6$ faces.

As answered by Joseph Malkevitch, fullerenes have these characteristics.

Details:

$$F = F_2+F_3+F_4+\cdots$$ $$2E = 3V = 2F_2+3F_3+4F_4+\cdots$$

Since a region bounded by n edges has n vertices and each vertex belongs to three regions, by Euler's formula $V-E+F=2$ we have:

$$6V-6E+6F = 12$$ $$4E-6E+6F = 12$$ $$6F-2E = 12$$ $$6(F_2+F_3+F_4+\cdots)-(2F_2+3F_3+4F_4+\cdots) = 12$$ $$4F_2+3F_3+2F_4+F_5+0F_6-F_7-2F_8-3F_9-\cdots = 12$$

That becomes:

$$F_5+0F_6=12+F_7+2F_8+3F_9+\cdots$$

-