Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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$'scancel you are done.

share|improve this answer
    
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

Your Answer

 
discard

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.