---
tag: 2G7061NXSP
kind: problem
name: Degree diameter problem
aliases: [degree-diameter]
sources:
  - wikipedia: en:19726161@r1375259210
    locator: Degree diameter problem
    note: adopted
    mention: wikipedia://en/19726161
    sections: [Problem]
same_as:
  wikidata: Q5251835
  wikipedia: Degree diameter problem
inventory: [60KS8P8BWT]
---

## Problem

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.