Must every vertex have the same degree?

Yes in this setting, but that condition alone is insufficient.

Are the distances physical lengths?

No. The standard graph property uses shortest-path edge counts.

Does the property depend on how the graph is drawn?

No. It depends on adjacency and the resulting graph distances.

AI Glossary / Graphs and symbolic AI / Intermediate

Distance-Regular Graphs

Definition

Distance-regular graphs are connected graphs whose local connection counts around pairs of vertices depend on their graph distance rather than on the particular vertices chosen. They have a strong uniformity across distance layers. In the simple undirected setting, this is more restrictive than ordinary regularity, which requires only that every vertex have the same number of neighbors.

What it means

Choose a starting vertex and group all vertices by their shortest-path distance from it. For a vertex in one layer, count its neighbors in the preceding, same, and following layers. In a distance-regular graph, those counts follow the same pattern for every eligible pair at the same distance, regardless of the starting vertex.
The property concerns connections, not the appearance of a drawing. A graph laid out as a neat geometric shape may fail the condition, while a distorted drawing of a qualifying graph still qualifies. The supplied term refers to NetworkX's distance-regularity check for simple undirected graphs.

How it works

Let x and y be vertices at distance i. Count the neighbors of y that are at distance i minus 1 from x; call this c_i. Count those at distance i plus 1 from x; call this b_i. In a distance-regular graph, these counts depend only on i. The remaining neighbors are at distance i from x, with count a_i.
If every vertex has degree k, then a_i + b_i + c_i = k. The b and c values can be summarized by an intersection array. Checking the property requires consistency across the relevant vertex pairs, not merely observing a plausible pattern around one conveniently chosen vertex. Shortest-path distance here is the number of edges, rather than an arbitrary geometric or weighted length.

Three practical examples

A graph-theory exercise uses a cycle or hypercube to study how distance layers organize a network.
An algorithm test uses a graph with known distance-regular structure to check calculations of layer counts and intersection arrays.
A network-design study examines a highly uniform abstract topology before separately evaluating routing demands, capacity, and physical implementation.

Think of it this way

Think of a building design where the pattern of connections one step nearer to, or farther from, any chosen room follows the same rule at each distance. The analogy captures uniformity, but real buildings rarely satisfy such exact combinatorial conditions. Equal corridor lengths or a symmetric floor plan alone would not establish the property.

Worked example

Take the cycle A - B - C - D - A. Every vertex has degree 2, and the diameter is 2. Starting from A, layer 0 is {A}, layer 1 is {B,D}, and layer 2 is {C}.
At distance 0, A has two neighbors in the next layer, so b_0 = 2. At distance 1, B has one neighbor A in the preceding layer and one neighbor C in the following layer, so c_1 = 1 and b_1 = 1. D has the same counts. At distance 2, C has both B and D in the preceding layer, giving c_2 = 2 and b_2 = 0. The same pattern holds when any other vertex is chosen as the starting point.
The intersection array is therefore {2,1;1,2}. There are no same-layer neighbors in this example, so each a_i is zero. If a new leaf E is attached only to A, A's degree becomes 3 and E's becomes 1. The modified graph is not even regular and therefore cannot be distance-regular.

Illustrative case study

At fictional Cedar Networks, a team uses a four-cycle as a small reference graph while checking a topology-analysis tool. It records the expected layer counts before running the implementation. Adding a leaf creates an intentionally negative test whose failure is easy to explain.
The team keeps this structural test separate from performance simulations, because a distance-regular topology does not automatically optimize the traffic pattern it expects. This fictional case illustrates using a mathematical property as a precise test condition. It does not claim a production-network benefit or endorse a particular topology.

Common misconceptions and mistakes

Equal degrees are necessary but not sufficient. Ordinary regular graphs can have different distance-layer patterns around different vertex pairs. Likewise, a visually symmetric drawing is not a proof, and checking only one root can miss a failure elsewhere.
Do not confuse distance-regular with every pair being equally distant. The four-cycle has pairs at distance 1 and at distance 2. Nor should it be treated as synonymous with distance-transitive: that stronger symmetry notion involves graph automorphisms. Finally, connectivity is part of the definition used here. A collection of separate copies does not become one connected distance-regular graph merely because each copy has the property.

Business use

For most businesses, distance-regularity is a specialist structural concept rather than a direct performance metric. It can help describe a proposed abstract network or create controlled test cases for graph software. Any operational conclusion still needs the relevant load, cost, reliability, and physical constraints. Preserve the distinction between a proof of a combinatorial property and evidence that the network meets the actual service requirement.

Check your understanding

Why does attaching a single leaf to A disprove distance-regularity immediately?

Answer: The resulting graph has unequal vertex degrees. Distance-regularity requires ordinary regularity as a necessary condition.

Related terms

Diameter
Hypercube (communication pattern)
Regular graph
graph distance
distance layer
intersection array
hypercube
cycle graph
strongly regular graph
distance-transitive graph

Learn next

Learn intersection arrays next. Repeat the layer-count calculation for a small cube graph and check the counts from more than one vertex. Then find an ordinary regular graph whose distance-layer counts fail the stronger condition.

Sources

Primary source: NetworkX official distance-regularity implementation and embedded documentation, https://networkx.org/documentation/stable/_modules/networkx/algorithms/distance_regular.html ; official overview, https://networkx.org/documentation/stable/reference/algorithms/distance_regular.html . The four-cycle calculation and fictional case are original illustrations.

Previous: Distance map Next: Distant supervision