Degree diameter problem¶

Maximize the number of vertices in a finite graph subject to simultaneous maximum-degree and diameter bounds, comparing constructions with the breadth-first Moore upper bound.

Version: v2 · 2026-09-19 · History
Domain-specific #: 1635
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Extremal Graph Order Under Degree and Diameter → Mathematics
Aliases: Degree–diameter problem, Degree/diameter problem

Core Idea¶

The degree–diameter problem asks, for positive integers \(d\) and \(k\), for the maximum possible order \(n(d,k)\) of a finite simple undirected graph whose maximum degree is at most \(d\) and whose diameter is at most \(k\). The objective is vertex count; degree and diameter are simultaneous constraints. Variants for directed, bipartite, planar, vertex-transitive, or other graph classes must be labeled because their bounds and extremizers differ.

A breadth-first expansion from one vertex gives the Moore bound. For \(d>2\), at most \(1+d\sum_{i=0}^{k-1}(d-1)^i\) vertices can lie within distance \(k\): one root, at most \(d\) neighbors, and at most \(d-1\) new branches at each later level.

How would you explain it like I'm…

The Biggest Town Puzzle

Imagine building a town where each house can have at most 3 roads coming out of it. And from any house, you must reach any other house in at most 2 road trips. The puzzle is: what is the biggest number of houses your town can have?

Most Dots, Few Lines, Short Trips

Think of a network of dots and lines. You set two limits: each dot may touch at most d lines, and any dot must be able to reach any other in at most k steps. The Degree diameter problem asks for the biggest number of dots such a network can have. You can get a ceiling by starting at one dot and counting how many new dots you could reach at each step if nothing ever overlapped. Real networks almost always have overlaps, so they usually fall short of that ceiling.

Largest Graph Under Degree and Distance Limits

The Degree diameter problem asks, for whole numbers d and k, for the largest number of vertices in a simple undirected graph where each vertex has degree at most d and the diameter (the longest shortest path between two vertices) is at most k. The goal is to maximize the number of vertices; degree and diameter are both constraints. Counting outward from one vertex like a tree gives an upper limit called the Moore bound: one vertex, up to d neighbors, and at most d−1 new branches from each vertex after that. Graphs that exactly hit this limit, called Moore graphs, are rare exceptions. It is different from just measuring a graph's diameter, and from the cage problem, which asks for the smallest graph with a given degree and girth.

For positive integers d and k, the Degree diameter problem asks for n(d, k), the maximum order of a finite simple undirected graph with maximum degree at most d and diameter at most k. A breadth-first count from any vertex gives the Moore bound: for d > 2, at most 1 + d Σ_{i=0}^{k−1} (d−1)^i vertices lie within distance k, since the root has at most d neighbors and each later vertex contributes at most d−1 new branches. Cycles and collisions stop most graphs from reaching this tree count, and graphs meeting it with equality, Moore graphs, are exceptional rather than typical. Research proceeds from above, proving tighter impossibility bounds, and from below, constructing large graphs, often algebraically or by computer search. Published tables of largest known graphs are mostly lower bounds, not exact values, unless optimality has been proved. Variants such as directed, bipartite, planar or vertex-transitive versions have different bounds and extremal graphs and must be labeled; directed diameter requires strong reachability and a different Moore expression. The problem is distinct from the cage problem (minimum order at fixed regular degree and girth), and "maximum degree at most d" is weaker than being d-regular, though extremal examples are often regular.

Scope of Application¶

The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Degree diameter problem itself, not metaphors based only on resemblance.

Extremal graph theory. Determining exact values or bounds for selected degree–diameter pairs.
Network topology. Designing many-node networks with bounded port count and hop distance.
Algebraic constructions. Using groups, finite fields, and incidence geometry to build large graphs.
Computational search. Finding record graphs or excluding candidates for small parameters.
Restricted graph classes. Studying planar, bipartite, Cayley, or vertex-transitive variants.
Asymptotic analysis. Comparing growth in d or k with Moore-order scaling.

Clarity¶

A clear account of Degree diameter problem must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. State directedness, simplicity, degree convention, diameter convention, and any restricted graph class. Distinguish exact optimum, lower bound from construction, upper bound, and asymptotic statement. Derive the correct Moore bound for exceptional cases such as d equal to two. Provide an adjacency, algebraic, or cited construction before claiming a record lower bound.

Manages Complexity¶

Degree diameter problem manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: graph class supplies finite simple undirected graphs provide the default feasible objects.; degree bound supplies no vertex may have degree exceeding \(d\).; diameter bound supplies every pair of vertices must be connected by a path of length at most \(k\).; order objective supplies the number of vertices is maximized.; moore upper bound supplies breadth-first counting supplies a universal feasibility ceiling..

Abstract Reasoning¶

Fix \(d\), \(k\), and the admissible graph class.
Derive the breadth-first Moore ceiling for those conventions.
Check known equality obstructions and stronger upper bounds.
Construct or retrieve a graph and verify maximum degree, connectivity, diameter, and order.
Compare its order with the current certified upper bound.
Use symmetry or algebraic structure to reduce verification without assuming optimality.
Report exactness only when lower and upper bounds coincide.

Knowledge Transfer¶

The strict upward abstraction is Optimization. Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints. Within extremal graph order under degree and diameter, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Degree diameter problem after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.

Relationships to Other Abstractions¶

Current abstraction Degree diameter problem Domain-specific

Parents (1) — outgoing typed relations

Degree diameter problem is a kind of Optimization Prime

Degree Diameter Problem instantiates Optimization because it seeks the maximum graph order among objects satisfying simultaneous degree and diameter constraints.

Hierarchy path (1) — routes to 1 parentless root

Degree diameter problem → is a kind of Optimization

Neighborhood in Abstraction Space¶

Degree diameter problem sits in a sparse region of the domain-specific corpus (76^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Extremal Graph Theory & Bounds (7 abstractions)

Nearest neighbors

Cage (Graph Theory) — 0.87
Well-covered graph — 0.83
Dense Graph — 0.82
Matching — 0.82
Even-hole-free graph — 0.82

Computed from structural-signature embeddings · 2026-10-25