Let $G$ be a planar graph in which every vertex has degree 4 and there are 10 regions (faces). How many graphs up to isomorphism are there?
We can easily infer from the vertex sum and Euler's formula, that the number of vertices is 8.
I drew one but every other graph that I draw is isomorphic to it, so I suspect there is just one. Proving it is another matter. I tried using the fact that it must have an Eulerian cycle, defining the map from vertex to vertex by the edges in the path, but couldn't see an argument that the map must be well-defined and bijective. I tried using the fact that it must have a Hamiltonian path, and now the map is bijective but I could not see a way to prove that it satisfied the homomorphism property. I also thought about trying to construct an isomorphism by tracing out the graph, but there seemed to be too many choices that one could possibly make.
Best Answer
You are correct; up to isomorphism there is just one 4-regular planar graph with 8 vertices, the square antiprism graph, this guy:
To just see how many there are, we can check e.g. Markus Meringer's list of regular planar graphs and see that there's just one 4-regular planar graph on 8 vertices.
To really demonstrate it, we can follow up on the hint by Ross Millikan in the comments. Each face of the planar embedding has at least three edges on its boundary. On the other hand there are 16 edges, and each edge is in two faces (because there cannot be a cut-edge; this is left as an exercise for the reader 😉.) So the sum of all the face lengths is 32. If all ten faces have length 3, that accounts for 30 already, so there are two "extra" edges to add to faces.
Hence we either have a pentagon and nine triangles, or two quadrilaterals and eight triangles. So you just need to show that the pentagon case, or two quadrilaterals that share an edge, or two quadrilaterals that share a vertex but no edge, can't possibly work.