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

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 =
"! " <> nauty <> "geng 10 -d3 -D3 | " <> nauty <> "planarg | " <>
nauty <> "pickg -Z3"];
output =
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)

• It looks like Troy Barcume (also mentioned in the acknowledgements) has (co-)authored only one paper, "On the Decomposition of Graphs Into Cliques", which I cannot access but which seems off-topic for this claim. So I doubt that the proof is published anywhere. Sep 18 at 15:11
• On the other hand, the table here eventually led me to this paper, which I'll wait to post an answer about in case its author would like to do that first. Sep 18 at 15:25
• Ars Comb. recently reopened, but it quickly closed again. Previously, it only offered a print edition, which means many articles are unavailable online. See math.stackexchange.com/questions/4327006/…. It's hard to imagine how the magazine is being managed; it's quite perplexing. In fact, there are some good articles inside. Sep 19 at 3:10
• @MishaLavrov This is weird, the bounds in this table seem far from optimal, the Moore bound gives an upper bound of 27306 for $\Delta = 5$ and $D = 8$ Sep 19 at 13:14
• @MishaLavrov I emailed Professor West, but unfortunately, he said that he couldn't remember where he had seen the statement. So maybe you are right. Sep 21 at 8:07

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[

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
• @Misha Lavrov Thank you. But I don't understand this sentence “ each one has a vertex not incident on an edge in $X$” in your proof (incident on an edge in $X$?) . Could you please provide a more detailed explanation? Sep 24 at 7:47
• If the edges in $X$ are $\{2,3\}$ and $\{7,8\}$, then vertices $2,3,7,8$ are incident on an edge in $X$, but vertices $1, 4, 5, 6$ are not. Sep 24 at 14:39