In graph theory, the degree diameter problem is the problem of finding the largest possible graph for a given maximum degree and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer. The table below gives current progress on this problem (excluding the case of degree 2, where the largest graphs are cycles with an odd number of vertices).
Table of the orders of the largest known graphs for the undirected degree diameter problem
Below is the table of the vertex numbers for the best-known graphs (as of June 2024) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, and thus finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem. Some general constructions are known for values of d and k outside the range shown in the table.
2 3 4 5 6 7 8 9 10 3 10The Petersen graph. 20Optimal graphs proven optimal by . 38Optimal graph found by and proven optimal by . 70Graph found by . 132Graphs found by Geoffrey Exoo from 1998 through 2010. 196 360Graph found by Jianxiang Chen in 2018. 600 1250Graph found by . 4 15 41Graph found by . 104Graph found by Nishant Bhakar in 2026 with Claude Fable assistance 364Graphs found by . 746Graph found by Francesc Comellas in 2026 with OpenAI GPT-5.6 Sol assistance 1 320Graphs found by Eyal Loz in 2006 3 243 7 766Graphs found by Dharunish Yugeswardeenoo in 2026 using OpenAI GPT-5.6 Sol and Claude Fable 5 Max assistance 18 369 5 24 72 252 650Graphs found by Rithwik Gupta in 2026 with AI-assisted computational searches 2 794 5 894Graphs found by Michel de Messieres in 2026 with Claude assistance 17 602 57 840Graphs found by 187 056 6 32Optimal graph found by and proven optimal by . 120 441 1 518 7 984 20 400 78 561 331 387Graph found by . 1 254 594 7 50The Hoffman–Singleton graph. 170 684 2 758 12 264Graphs found by . 56 952 254 268 1 224 680 6 007 230 8 57Graphs found by . 253Graph found by Margarida Mitjana and Francesc Comellas in 1995, and independently by . 1 100 5 334 39 792 137 082 744 878 4 243 860 24 914 017 9 74 585 1 640 8 802Graph found by Mark Marosi in 2026 with Claude assistance 76 113 298 840 1 857 060 12 439 224 71 808 556Graphs found by Chenxudong in 2026 10 91 650 2 485 33 397 135 056 605 280 4 387 740 30 480 377 221 662 027 11 106 715 3 235 36 563 182 618 1 152 900 9 260 784 72 933 102 600 380 000 12 133Graphs found by . 791 5 832Graphs found by Ryosuke Mizuno in 2026 using ChatGPT 41 699 359 772Graphs found by . 2 007 474 17 358 227 159 046 249 1 506 256 891 13 162McKay–Miller–Širáň graph found by . 868 6 611 50 750 534 234 3 528 248 35 140 224 304 076 768 3 077 200 700 14 183 1 094 8 303 88 452 816 294 6 200 460Graphs found by . 58 498 013 600 134 477 7 041 746 199 15 189 1 539 11 780 100 000 1 424 472 9 372 402 92 554 668 1 171 998 164 10 012 349 898 16 216 1 920 16 384Graph found by a team of 6 people in 2026 using URSA (an agentic tool) 147 456 1 779 528 14 882 658 140 559 416 2 025 135 681 12 951 452 377
Entries without a footnote were found by Rishabh Rajiv in 2026 using agentic coding systems. In all other cases, the footnotes in the table indicate the origin of the graph that achieves the given number of vertices:
References
External links The Degree-Diameter Problem on CombinatoricsWiki.org. Francesc Comellas' degree-diameter problem page with records regularly updated as of 2026 Eyal Loz's degree-diameter problem page (archived 2016.) Geoffrey Exoo's degree-diameter record graphs page (archived 2015.)