Let G be a 4 regular connected planar graph (with a planar embedding), where all faces are either degree 3 or degree 4.

Then determine the number of faces of degree 3.

Also, now suppose that every vertex in G is incident with 1 face of degree 3, and 3 faces of degree 4. Determine the number of vertices, edges, and faces of degree 4 in G.

I think this question is solved using Euler's formula, $v-e+f=2$, but I'm not entirely sure how to use that to solve the problem. I know that $e=2v$, but what else can be figured out from the question? Thank you in advance!


1 Answer 1


Hints: Let $f_i$ denote the number of faces of degree $i$. Then you have $f=f_3+f_4$ and $2e=3f_3+4f_4$ (counting edges along the boundary of each face counts each edge twice). Now play with these equations, the $2v=e$ that you know, and Euler's formula to calculate $f_3$.

For the second part, you now know the value of $f_3$. If it is the case that every vertex is contained in exactly one face of degree $3$, then argue that $v=3f_3$. You can now use the above equations to find $e$ and $f_4$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .