I'm working on a project for a class and as part of that project I (previously) decided to do the following problem from our textbook, Combinatorics and Graph Theory 2nd ed. by Harris, Hirst, & Mossinghoff.
Find a 4-regular planar graph, and prove that it is unique.
(Now that I'm posting this I will be using a different problem for my project whether I get help on this or not.) The issue I'm having is that I don't really buy this. "4-regular" means all vertices have degree 4. A "planar" representation of a graph is one where the edges don't intersect (except technically at vertices). Below are two 4-regular planar graphs which do not appear to be the same or even isomorphic. The first one comes from this post and the second one comes from this post.
What's going on? Am I just missing something trivial here?
Best Answer
Even if we fix the number of vertices, the (connected) $4$-regular planar graph of that order (number of vertices) may not be unique. According to work by Markus Meringer, author of GENREG, the only orders for which there is a unique such graph are likely to be $n=6,8,9$.
An antiprism graph with $2n$ vertices can be given as an example of a vertex-transitive (and therefore regular), polyhedral (and therefore planar) graph.
The pentagonal antiprism looks like this:
There is a different (non-isomorphic) $4$-regular planar graph with ten vertices, namely the elongated square dipyramid:
Non-isomorphism of the graphs can be demonstrated by counting edges of open neighborhoods in the two graphs. The open neighborhood of each vertex of the pentagonal antiprism has three edges forming a simple path. In the elongated square dipyramid some open neighborhoods have two edges that form a path and some have four edges that form a cycle.
Notes about the small odd vertex cases
The only $4$-regular graph on five vertices is $K_5$, which of course is not planar.
Nonexistence of any $4$-regular planar graph on seven vertices was the topic of this previous Question.
Uniqueness of the $4$-regular planar graph on nine vertices was mentioned in this previous Answer. The elegant illustration below, the dual of the Herschel graph, is from David Eppstein: