1
$\begingroup$

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.

  • 0
    You'll also need to know something relating faces, edges, and vertices...2012-11-17
  • 1
    http://en.wikipedia.org/wiki/Planar_graph#Euler.27s_formula2012-11-17
  • 0
    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: http://4coloring.wordpress.com/open-points-and-notes/ and read this other question: http://math.stackexchange.com/questions/158620/four-color-theorem-3-regular-planar-graph-hamiltonian-path-and-spiral-chains2012-11-17
  • 0
    This very interesting class of graphs is known as the fullerenes. You can find out more about them here: http://en.wikipedia.org/wiki/Fullerene2012-11-17

2 Answers 2