A question on my graph theory exam asked us to find how many $4$-regular, simple planar graphs there are up to isomorphism such that every face, including the outer face, is bounded by three edges.
I was only able to draw one such graph while trying to solve this question, and it looks like this:
$\hspace{2cm}$
My answer that there was only one such graph was correct. Thankfully it was multiple choice, because I'm still not sure how to give a proof of this. I was wondering what a proof of this would look like. Thanks.
For all $n$-vertex, $m$-edge planar graphs with $n$ at least $3$, you have the inequality $m \le 3n-6$. This inequality is tight when the planar graph is a maximal planar graph: a triangulation. That's what is going on here, so we know that $m=3n-6$ for this graph.
Knowing that the graph is $4$-regular gives us another relation between $m$ and $n$, and together those can be used to show that $n=6$ is the only possibility.
Finally, there is only one $4$-regular graph on $6$ vertices up to isomorphism (to see this, note that its complement is a $1$-regular graph on $6$ vertices) and it happens to be planar.