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.
Best Answer
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.