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.


No such simple graph can exist, the smallest 5-regular planar graph is the icosahedron and it has diameter 3 (the distance between the green and yellow vertex is 3). I proved that there are actually only two simple planar 5-regular graphs with diameter less than 4 in my paper in Ars Combinatoria (Volume CVI, July, 2012). See my webpage about extremal regular planar graphs for other examples of different degrees and diameters.

Icosahedron with distances coloured

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$.

If you are allowing loops (not just multiple edges) then the best possible is 10 vertices, achieved by adding loops to the vertices of valency 3 in this graph: 10 vertices, diameter 2, maximum degree 5

Any graph with more vertices would lead (upon removal of multiple edges or loops) to a simple planar graph of maximum degree at most 5 with diameter 2 but the largest such graph is proven by Yang, Yuansheng, Lin, Jianhua, Dai, Yongjie (J. Comput. Appl. Math. 144 (2002) 349-358) to have 10 vertices, such as the example above.

  • $\begingroup$ Thanks for your response. I don't need to know the smallest graph however, I just need some sort of bound for the number of nodes in such a graph. I've been given a hint that it is less than 27, but there is a tighter bound to be found. $\endgroup$ – Charlie Jun 26 '12 at 7:10
  • $\begingroup$ hi @Charlie, the graph with 10 vertices and 4 loops is the largest possible non-simple planar graph with diameter 2. No graph with maximum degree 5 and diameter 2 can have more than 26 = 1 + 5 + 5 * 4 vertices simply by counting a vertex's neighbours and its neighbour's neighbours. Given that structure most vertices are at a distance 4 apart unless you start adding edges between them, and that gets tricky to do and preserve planarity... $\endgroup$ – jp26 Jun 26 '12 at 9: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.

  • 1
    $\begingroup$ 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. $\endgroup$ – jp26 Jun 24 '12 at 14:39
  • $\begingroup$ Thanks for your correction. $\endgroup$ – KReiser Jun 24 '12 at 18:16

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

*Thanks to KReiser for pointing out my mistake.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.