# If $G=(V,E)$ is a planar graph, all vertex degrees are $3$, all faces are of five/six edges, how many five-edged faces are there?

Given a graph $G = (V,E)$, a planar graph where every vertex has degree $3$ and all faces are five-edged or six-edged. How many five-edged faces are there?

It was a question in one of our previous exams, the answer is $12$, but I have no clue on how to solve it. I mean, I can have as many faces as I want, why is it limited to $12$ and $12$ only?

-
You can have as many faces as you want? Have you actually tried to come up with one with (say) $0$ five-sided faces? –  Chris Eagle Jun 21 '13 at 17:40
if I draw a 6-edged face and given that every vertex is of degree 3, I still can and have to draw infinite 6-edged faces... I don't know. What's the direction to solve this? –  TheNotMe Jun 21 '13 at 17:43
Possible duplicate of Restrictions on the faces of a 3-regular planar graph –  Vedran Šego Jun 21 '13 at 17:49

Since the graph is planar

$$V-E+F=2 \,.$$

As each vertex has degree $3$, by Handshaking lemma we have $2E=3V$.

Let $f_1$ be the number of $5$ edged faces and $f_2$ be the number of $6$ edges faces. Then

$$2E=5f_1+6f_2 \,.$$ $$f_1+f_2=F \,.$$

From here we get $$2E=6F-f_1 \,.$$

Thus, plugging everything in the first relation, you get:

$$\frac{2E}{3}-E+\frac{2E+f_1}{6}=2 \,.$$

Since all $E$'s cancel you are done.

-
I have trouble understanding how do we get $2E = 5f_1 + 6f_2$? I understand that $5f_1 + 6f_2$ is the total number of edges in those faces, but not all edges belong to two faces (some are on the outer edge of the graph), right? The other question didn't explain that either. –  Vedran Šego Jun 21 '13 at 17:59
@VedranŠego Don't forget that the outside is also a face, is the infinite face. The formula $V-E+F=2$ counts the infinite face too. Because of this, all edges belong to exactly $2$ faces. –  N. S. Jun 21 '13 at 18:02
ALL edges belong to two faces, don't forget that there is the infinite face. –  TheNotMe Jun 21 '13 at 18:03
Thank you N.S. :) –  TheNotMe Jun 21 '13 at 18:04
I'm sorry, can you explain again how you got $2E = 5f_1 + 6f_2$ please? –  TheNotMe Jun 21 '13 at 18:08