Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?

Question

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".

6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. Barcume proved that no such graph has more than 12 vertices.)

What is the original reference for Barcume's result, and how can it be proven?

PS: Another interesting observation is that upon reviewing the book's solution, I found the first example to be incorrect as its diameter is 4, not 3.

---

Misha Lavrov's answer is nice. By the way, for all (e.g., 10-vertex) 3-reguler planar graphs with diameter 3, we can also use nauty:

geng 10 -d3 -D3 | planarg | pickg -Z3

Similarly, we can call Nauty in Mathematica.

nauty = "D:\\nauty_win\\";
stream = 
  OpenRead[
   "! " <> nauty <> "geng 10 -d3 -D3 | " <> nauty <> "planarg | " <> 
    nauty <> "pickg -Z3"];
output = 
 Reap[While[(line = ReadLine[stream]) =!= EndOfFile, 
    Sow[ImportString[line, "Graph6"]]]][[2, 1]]

---

But now I do not understand the statement from Misha Lavrov: each one has a vertex not incident on an edge in X. For example, we chose $X=\{\{2,7\},\{3,8\}\}$. Then $V(G_1)=\{2,3,5,6\}$ and $V(G_2)=\{1,4,7,8\}$. But each vertex in $G_i$ is incident on an edge in $X$. Do I miss something? (Now, I understand; see the comments below the answer)

Answer 1

As mentioned in the comments, it seems unlikely that Troy Barcume's result, whatever it was, is published anywhere.

On the other hand, we have the paper The Complete Catalog of 3-Regular, Diameter-3 Planar Graphs by Robert Pratt, which solves the problem by an exhaustive search. The search space is finite by the Moore bound: in any $3$-regular graph with diameter $3$, there are at most $1 + 3 + 3\cdot 2 + 3 \cdot 2^2 = 22$ vertices. Moreover, the Hoffman and Singleton paper On Moore Graphs with Diameters 2 and 3 shows that for regular graphs with diameter $2$ and $3$, only finitely many cases achieve the moore bound, and this is not one of them; therefore the maximum number of vertices is $20$.

---

It has been a while since 1996; we have much faster computers, and software like plantri. So I decided to see if we could make the exhaustive search easier to replicate.

Let's begin by showing that any large $3$-regular planar graph with diameter $3$ is $3$-edge-connected. (Or, equivalently, $3$-vertex connected; edge and vertex connectivity are equal for $3$-regular graphs.)

Suppose not: let $G$ be $3$-regular with diameter $3$, and suppose there is some set $X \subseteq E(G)$, with $|X| \le 2$, such that $G-X$ has two components, $G_1$ and $G_2$. If either $G_1$ or $G_2$ had only $1$ or $2$ vertices, they would not be able to get enough edges for $G$ to be $3$-regular. So each has at least $3$ vertices, which means that each one has a vertex not incident on an edge in $X$. Let $v_1 \in V(G_1)$ and $v_2 \in V(G_2)$ be two such vertices. Since the diameter of $G$ is $3$, there must be a $v_1 - v_2$ path of length $3$ or less. The edge from $X$ on that path must be the middle edge, which means that both $v_1$ and $v_2$ must be adjacent to an endpoint of an edge in $X$. With this constraint, there can only be at most $4$ such vertices in each of $G_1$ or $G_2$; together with the endpoints of edges in $X$ (also at most $4$) there can be at most $12$ vertices in $G$. (Moreover, either all vertices in $G_1$ are adjacent to endpoints of both edges in $X$, or else all vertices in $G_2$ are; this rules out $12$ vertices, too.)

Why do we want $3$-connectivity? Because now the dual of $G$ is, first of all, uniquely defined; second, it is a planar triangulation. If $G$ has at most $20$ vertices, then it has at most $30$ edges, so its dual has at most $12$ vertices.

Here is some Mathematica code that runs plantri (well, assuming you separately have plantri) to search the $12$-vertex planar triangulations to see if any of their duals have diameter $3$:

plantri = StartProcess[{"C:/graphtools/plantri", "12", "-d", "-g"}];
Timing[Length[output = Reap[
  While[(line = ReadLine[plantri]) =!= EndOfFile, 
  Sow[ImportString[line, "Graph6"]]]][[2, 1]]]]
Tally[GraphDiameter /@ output]

This outputs two things. First, something like {42.9375, 7595}, which says that in less than 43 seconds, plantri found $7595$ triangulations on $12$ vertices. Second, {{6, 4313}, {5, 3210}, {7, 72}}, which says that the diameters of their duals range from $5$ to $7$, and certainly none of them have diameter $3$.

We can repeat this with $12$ replaced by $11$, $10$, $9$, and finally $8$ (an $8$-vertex planar triangulation has $18$ edges, so its dual is a $12$-vertex $3$-regular graph). It is not until the very end that we see any graphs with diameter $3$, and then Select[output, GraphDiameter[#] == 3 &] produces