A n-regular graph is a graph in which every vertex has degree n . The diameter of a graph is the length of the longest distance in the graph. What is the largest number of vertices a planar n-regular graph with diameter d can have? Here are the best known bounds for small n and d . Click on the links for pictures.

---

Largest planar n-regular graph with diameter d

n \ d	1	2	3	4	5	6
1	2	none	none	none	none	none
2	3	5	7	9	11	13
3	4	6	12	18, 30	28, 62	36, 122
4	none	9	16, 33	27, 96	44, 291	81, 867
5	none	none	16, 52	28, 248	62, 984	124, 3928

---

Back to Eric's Combinatorial Geometry Page.