4
$\begingroup$

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.

3 Answers 3

7

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.

  • 0
    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...2012-06-26
3

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.

  • 0
    Thanks for your correction.2012-06-24
1

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

*Thanks to KReiser for pointing out my mistake.

  • 1
    Too right. Missed that detail :/ Will update my answer to say so.2012-06-24