{
  "id": "enwiki-001375259210",
  "slug": "degree-diameter-problem",
  "title": "Degree diameter problem",
  "qid": "",
  "lead": "In graph theory, the degree–diameter problem asks for the maximum possible number n_{d,k} of vertices in a finite simple undirected graph of maximum degree at most d and diameter at most k . A breadth-first search gives a general upper bound known as the Moore bound. Exact equality in the Moore bound is exceptional. Apart from complete graphs, odd cycles, and the degree-one cases, the only known graphs attaining it are the Petersen graph and the Hoffman–Singleton graph; the only unresolved nontrivial parameter pair for equality is degree 57 and diameter 2. The exact value of n_{d,k} is unknown for most pairs (d,k) . A 2026 preprint by Wouter Cames van Batenburg and Samuel Korsky reports a proof that, for every fixed positive integer k , : \\lim_{d\\to\\infty}\\frac{n_{d,k}}{d^k}=1. This resolves a conjecture of Béla Bollobás and shows that, for every fixed diameter, the Moore bound is asymptotically tight as the degree tends to infinity.",
  "body": "In graph theory, the degree–diameter problem asks for the maximum possible number n_{d,k} of vertices in a finite simple undirected graph of maximum degree at most d and diameter at most k . A breadth-first search gives a general upper bound known as the Moore bound. Exact equality in the Moore bound is exceptional. Apart from complete graphs, odd cycles, and the degree-one cases, the only known graphs attaining it are the Petersen graph and the Hoffman–Singleton graph; the only unresolved nontrivial parameter pair for equality is degree 57 and diameter 2. The exact value of n_{d,k} is unknown for most pairs (d,k) . A 2026 preprint by Wouter Cames van Batenburg and Samuel Korsky reports a proof that, for every fixed positive integer k , \\lim_{d\\to\\infty}\\frac{n_{d,k}}{d^k}=1. This resolves a conjecture of Béla Bollobás and shows that, for every fixed diameter, the Moore bound is asymptotically tight as the degree tends to infinity. n_{d,k}=\\max\\bigl\\{|V(G)|:\\Delta(G)\\leq d,\\ \\operatorname{diam}(G)\\leq k\\bigr\\}, where \\Delta(G) denotes the maximum degree of G . The elementary cases are n_{d,1}=d+1,\\qquad n_{1,k}=2,\\qquad n_{2,k}=2k+1. They are attained by complete graphs, a single edge, and odd cycles, respectively. To obtain an upper bound, fix a vertex v . There are at most d vertices at distance one from v , and at most d(d-1)^{i-1} vertices at distance i , since each vertex other than v has at most d-1 edges leading farther away from v . Consequently, n_{d,k}\\leq M_{d,k}=1+d\\sum_{i=0}^{k-1}(d-1)^i, where M_{d,k} is the Moore bound. Equivalently, M_{d,k}= \\begin{cases} 1+d\\displaystyle\\frac{(d-1)^k-1}{d-2},&d\\geq3,\\\\[6pt] 2k+1,&d=2,\\\\ 2,&d=1. \\end{cases} For every fixed k , M_{d,k}=d^k+O_k(d^{k-1}) as d\\to\\infty . \\delta(G)=M_{d,k}-|V(G)| is called its defect. Moore graphs have defect zero. Graphs of small positive defect are studied as finite approximations to Moore graphs. For d=2 , the exact value is n_{2,k}=2k+1 . For every fixed d\\geq3 , Bollobás and Fernandez de la Vega showed that almost every d -regular graph on n vertices has diameter (1+o(1))\\log_{d-1}n as n\\to\\infty . Together with the Moore bound, this gives n_{d,k}=(d-1)^{k+o(k)} as k\\to\\infty for each fixed d\\geq3 . Thus random regular graphs provide constructions with the optimal exponential growth rate. This result does not determine the asymptotic ratio n_{d,k}/M_{d,k} . \\mu_k=\\liminf_{d\\to\\infty}\\frac{n_{d,k}}{d^k}. The 2013 survey by Miller and Širáň recorded that \\mu_1=\\mu_2=\\mu_3=\\mu_5=1 and that \\mu_4\\geq\\frac14. For every fixed k\\geq2 , Bollobás conjectured that \\limsup_{d\\to\\infty}\\frac{n_{d,k}}{d^k}=1. A stronger variant replaced the limit superior by the limit inferior. In their 2026 preprint, Wouter Cames van Batenburg and Samuel Korsky report a proof of the full limit \\lim_{d\\to\\infty}\\frac{n_{d,k}}{d^k}=1 for every fixed positive integer k . Equivalently, \\mu_k=1 and \\lim_{d\\to\\infty}\\frac{n_{d,k}}{M_{d,k}}=1 for every fixed k . Their construction uses regular graphs whose vertices are partial flags in vector spaces over finite fields. The preprint is accompanied by a Lean 4 formalization of its central theorem chain, including the asymptotic theorem. M^{\\rightarrow}_{d,k}=1+d+d^2+\\cdots+d^k = \\begin{cases} \\displaystyle\\frac{d^{k+1}-1}{d-1},&d>1,\\\\[6pt] k+1,&d=1. \\end{cases} A digraph attaining the bound is called a Moore digraph. Moore digraphs exist only in the elementary cases d=1 , represented by directed cycles, and k=1 , represented by complete digraphs. Restricted forms of the degree–diameter problem have been studied for Cayley graphs, vertex-transitive graphs, bipartite graphs, planar graphs, graphs embeddable on a fixed surface, and several other graph classes.",
  "categories": [
    "23118434",
    "23603337",
    "26199120",
    "29176239",
    "29264960"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1375259210",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789579214.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001375259210",
    "type": "webpage",
    "title": "Degree diameter problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/degree-diameter-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001375259210",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1375259210",
    "note": "Immutable snapshot enwiki-001375259210"
  }
}