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.

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.

share|improve this question
    
You'll also need to know something relating faces, edges, and vertices... –  Erick Wong Nov 17 '12 at 1:51
1  
    
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

3 Answers 3

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.

share|improve this answer

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

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

share|improve this answer

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.