# How many nodes are there in a 5-regular planar graph with diameter 2?

Undergrad here; I honestly have no idea what to do. I can't even imagine what a 5-regular graph with diameter 2 would look like, let alone a planar one.

-

As a nonplanar example*, there's K8, but without the "perimeter" edges.

*Thanks to KReiser for pointing out my mistake.

-
That's not planar. Planar means it's embeddable into the plane without self-intersection. –  KReiser Jun 24 '12 at 3:42
Too right. Missed that detail :/ Will update my answer to say so. –  bwhite.ee Jun 24 '12 at 3:43

Let's go through and decipher what each of these statements mean.

Planar: embeddable in the plane without self-intersections. By Kuratowski and Wagner, this is equivalent to a graph not having $K_5$ or $K_{3,3}$ as a minor.

5-regular: every node has exactly 5 edges.

Diameter 2: the maximum length of path between any two nodes is 2 (note that it must be achieved- ie there must be two vertices at least two edges apart).

Let's go through and attack this naively. If we need the maximum length of path between any two nodes to be 2, then we need at least 3 nodes. Can we do it with 3 nodes? No, because then we would have 15 as the total degree of the graph, which contradicts the handshaking lemma.

Ok, let's try 4. Since every vertex has to be 2 away from each other vertex, this means we'll need to start with a square. Now, each vertex needs 3 other edges, and we have to add them in a way which keeps the graph planar: connect 3 edges from the top left to the bottom left, and 3 edges from the top right to the bottom right. So this gives us a planar, 5-regular graph of diameter 2.

But now we should check that such a graph cannot be made with more than four nodes. This is a little more interesting than simply finding an example. By the same logic as used to rule out the three-vertex graph, we can rule out all graphs with an odd number of vertices. This means we're left with graphs with an even number of vertices which is at least 6. But in order for such a graph to have diameter 2, it must contain $K_{3,3}$ as a subgraph, and therefore it cannot be planar. Turns out this is false, examples exist as seen in comment.

Thus, there is an example of 4 nodes in a planar, 5-regular, diameter 2 graph.

-
You can get an example with 6 nodes using the 5-cycle as a basis; duplicate all edges and then add one vertex adjacent to each vertex of the cycle. That graph has radius 1 but diameter 2 and is planar. Along the same lines you can take the cube (diameter 3) and add edges across 4 faces to increase the degree of each vertex to 4, then double four more independent edges to give a planar 5-regular graph with graph diameter 2. –  jp26 Jun 24 '12 at 14:39
Thanks for your correction. –  KReiser Jun 24 '12 at 18:16
We have $5n=2m$ since it is 5-regular and every face must be of size 3 or more if there are no multiple edges, so $2m\geq 3f$. Putting these together with Euler's formula we get $$\frac{2m}{3} \geq f = 2 + m - n = 2 + m - \frac{2m}{5}$$ Simplifying we see that $m \geq 30$ and so $n\geq 12$.