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?

enter image description here enter image description here

  • $\begingroup$ Yes, I agree. We need something more than just $4$-regular and planar to make the graph unique. You give examples with $8$ vertices and with $12$ vertices. I can think of planar $4$-regular graphs with $10$ and with infinitely many vertices. $\endgroup$ – hardmath Dec 3 '16 at 4:11
  • $\begingroup$ One thought would be to check the textbook's definition. While you and I take $4$-regular to mean simply each vertex having degree $4$ (four edges at each vertex), it is possible the book defined it to mean something stronger. $\endgroup$ – hardmath Dec 3 '16 at 4:15
  • $\begingroup$ @hardmath, thanks, that's all the confirmation I need. Re: definition in the book, it just says "A graph $G$ is regular if every vertex has the same degree. $G$ is said to be regular of degree $r$ (or $r$-regular) if $\deg(v) = r$ for all vertices $v$ in $G$." I wonder if there's some "we make such-and-such assumption only for this section" that I missed.. $\endgroup$ – user307169 Dec 3 '16 at 4:18
  • $\begingroup$ I added an image of the smallest such graph to this recent Question. $\endgroup$ – hardmath Dec 3 '16 at 4:25
  • $\begingroup$ The only thing I can imagine is that once you fix the order (the number of vertices) of the 4-regular planar graph then it might be unique. $\endgroup$ – Laars Helenius Dec 3 '16 at 4:40

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:

pentagonal antiprism

There is a different (non-isomorphic) $4$-regular planar graph with ten vertices, namely the elongated square dipyramid:

elongated square bipyramid

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:

dual Herschel graph

| cite | improve this answer | |

I know I asked this a while ago, but since this question seems to attract attention every now and then I figured I should post this.

I found a working errata link for this book (I previously couldn't) and it turns out the question was missing some information. http://www.appstate.edu/~hirstjl/bib/CGT_HHM_2ed_errata.html

Here's the relevant portion of the link, emphasis on missing parts mine:

  • p. 80, exercise 10 of section 1.5.2 should read: "Find a 4-regular planar graph with triangular regions, and prove that it is unique."
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy