As many points as two steps allow

The densest graph without a square asked how many edges a graph can carry with no cycle of four. Forbid triangles as well, and the graph has girth at least five: no cycle shorter than five edges. A graph of girth five is sparse by necessity, and the natural extremal question turns inside out. Instead of asking how many edges fit, fix how many neighbours each point has and ask how many points the graph must have — or, in the other direction, how many it can have if every point must be close to every other.

Take a graph in which every point has exactly $d$ neighbours and every point can be reached from every other in at most two steps. Stand at one point. It has $d$ neighbours, each of those has $d - 1$ further neighbours, and that is everything within two steps. So there are at most

$$1 + d + d(d - 1) = d^2 + 1$$

points, with equality exactly when the $d(d-1)$ points two steps away are all different — that is, when the graph has no triangle and no four-cycle, girth five. This is the Moore bound, named after Edward F. Moore, who asked in the late 1950s which graphs meet it.

Graphs that meet it are called Moore graphs, and there are astonishingly few. The pentagon meets it with $d = 2$: five points, $1 + 2 + 2$. The Petersen graph meets it with $d = 3$: ten points. The graph in the figure, found by Alan Hoffman and Robert Singleton in 1960, meets it with $d = 7$: fifty points. And that is all — with one possible exception that has resisted every attempt for sixty years.

Seen from one point #

The bound is a breadth-first count, and a Moore graph laid out from one of its points shows the count literally.

In the Petersen graph, the top point’s three neighbours each have two further neighbours, and the six points reached that way are all different and are all the remaining points. Every edge of the graph is either on a path down from the top or runs within the bottom row, joining two points that are each two steps from the top. Those bottom-row edges are what make every point within two steps of every other: a point in the bottom row reaches the others through them.

The Hoffman–Singleton graph does the same with seven neighbours and forty-two points two steps away. The figures check every claim by computation: every point has the stated degree, a search from every point finds no cycle shorter than five, and the layers from a point have sizes $1$, $d$ and $d(d-1)$ with nothing left over. The bound is not approached; it is met with no room to spare, and meeting it forces a structure so rigid that it almost never exists.

Why two steps and girth five go together #

The two conditions in the bound look independent — one about distance, one about cycles — and a Moore graph is exactly where they meet. A graph with every point within two steps of every other has diameter two; a graph with no cycle shorter than five has girth five. For a graph of degree $d$, diameter two forces at most $d^2 + 1$ points, and girth five forces at least $d^2 + 1$, by the same breadth-first count read the other way: from any point, the $d(d-1)$ points two steps away must all be distinct if there are no short cycles.

So a Moore graph is simultaneously the largest graph of its degree and diameter and the smallest of its degree and girth. Most graphs fail both bounds by a wide margin. Triangle-free graphs, which the edge that forces a triangle found can be as dense as a complete bipartite graph, are far from girth five; the complete bipartite graph has four-cycles everywhere. Pushing girth up to five while keeping every point within two steps is a demand so tight that it pins down the number of points exactly.

Pentagons and pentagrams #

The Hoffman–Singleton graph has a construction that fits on a line, due to Keith Robertson. Take five pentagons, numbered $0$ to $4$, each with vertices numbered $0$ to $4$ round the cycle, and five pentagrams — five-pointed stars, each vertex joined to the two vertices two places away round the circle — numbered the same way. Join vertex $j$ of pentagon $h$ to vertex $h \cdot i + j$ of pentagram $i$, all numbers taken modulo $5$.

Each pentagon vertex then has two neighbours in its pentagon and one in each of the five pentagrams: seven. Each pentagram vertex likewise. The multiplication $h \cdot i$ is what prevents short cycles: two pentagon vertices can share a neighbour in at most one pentagram, because a pair of equations $h \cdot i + j = h' \cdot i + j'$ determines $i$ when $h \ne h'$, and arithmetic modulo the prime $5$ guarantees it. The construction is a small piece of finite geometry in disguise, of the kind the orders a plane cannot have built projective planes from.

Why only four degrees #

The proof that nothing else exists is an eigenvalue argument, and it is one of the classic applications of linear algebra to a counting problem.

Let $A$ be the adjacency matrix of a Moore graph with degree $d$: rows and columns indexed by the points, with a $1$ where two points are joined. The $(u, v)$ entry of $A^2$ counts the walks of length two from $u$ to $v$, the fact two graphs the eigenvalues cannot tell apart built on. In a Moore graph, that count is $d$ on the diagonal, $0$ for joined points (no triangles), and exactly $1$ for points not joined (they are two steps apart by exactly one path). So

$$A^2 + A - (d-1)I = J,$$

where $J$ is the matrix of all ones. This single identity determines the eigenvalues. The all-ones vector gives eigenvalue $d$. Every other eigenvector is orthogonal to it, so $J$ annihilates it, and its eigenvalue $\lambda$ satisfies $\lambda^2 + \lambda - (d-1) = 0$:

$$\lambda = \frac{-1 \pm \sqrt{4d - 3}}{2}.$$

The two values occur with multiplicities $a$ and $b$ that must add to $d^2$ — the number of points less one — and must make the trace of $A$, which is nought since no point is joined to itself, come out right: $d + a\lambda_1 + b\lambda_2 = 0$. Those two equations fix $a$ and $b$. And multiplicities must be whole numbers.

If $\sqrt{4d - 3}$ is irrational, the two multiplicities must be equal, which forces $d = 2$ — the pentagon. If it is a whole number $s$, the trace equation becomes a condition that $s$ divides $15$, so $s$ is $1$, $3$, $5$ or $15$, and $d = (s^2 + 3)/4$ is $1$, $3$, $7$ or $57$. Setting aside the trivial $d = 1$, the only possible degrees are $2$, $3$, $7$ and $57$. The figure computes the multiplicities for every degree from $2$ to $60$ and finds them whole at exactly those four.

The divisibility step is worth writing out, because it is where the whole classification happens. With $s = \sqrt{4d - 3}$, the eigenvalues are $(-1 \pm s)/2$ and $d = (s^2 + 3)/4$. The trace condition $d + a\lambda_1 + b\lambda_2 = 0$, with $a + b = d^2$, simplifies to $(a - b)s = d^2 - 2d$. Substituting $d = (s^2 + 3)/4$ and clearing denominators leaves

$$s^4 - 2s^2 - 16(a - b)s = 15.$$

Every term on the left is a multiple of $s$, so $s$ must divide $15$. The four divisors of $15$ are $1$, $3$, $5$ and $15$, giving $d = 1$, $3$, $7$ and $57$. The number $15$ is not chosen; it falls out of the algebra, and with it the entire list.

Hoffman and Singleton published this in 1960, together with the graph for $d = 7$ and a proof that it is unique. For $d = 57$ the argument allows a graph with $3{,}250$ points; it does not produce one.

The pentagon, where the square root is irrational #

The case $d = 2$ is the one that escapes the divisibility argument, and it is worth seeing why. A graph of degree two is a union of cycles, and a Moore graph of degree two must have $2^2 + 1 = 5$ points, all within two steps of one another: the pentagon. Its eigenvalues are $2$ and the two roots of $\lambda^2 + \lambda - 1 = 0$, which are $(-1 \pm \sqrt 5)/2$ — the golden ratio’s reciprocal and its negative partner — each with multiplicity two.

Here $\sqrt{4d - 3} = \sqrt 5$ is irrational, so the two eigenvalues are conjugate irrationals, and the only way the trace can come out rational is for them to appear equally often. That forces $a = b$, and $a + b = d^2$ with the trace condition then forces $d = 2$. Every other degree needs $4d - 3$ to be a perfect square, and from there the divisibility by fifteen takes over. The pentagon is the one Moore graph whose spectrum is irrational, and the golden ratio sits in it for the same reason it sits in the regular pentagon’s diagonals.

Longer cycles, and the graphs from geometry #

The question generalises: fix the degree and the girth, and ask for the smallest graph — a cage. The breadth-first count gives a Moore bound for every girth, and the cages can be compared with it.

For three neighbours per point, the bound is met at girths $3$, $4$, $5$, $6$, $8$ and $12$, and at no other. The cases of even girth have a beautiful source. The Heawood graph, with fourteen points and girth six, is the incidence graph of the projective plane of order two — the seven points and seven lines of the Fano plane, each point joined to the lines through it — and the plane hiding in the squares met that plane among Latin squares. The Tutte–Coxeter graph, girth eight, is the incidence graph of a generalised quadrangle, and the Benson graph, girth twelve, of a generalised hexagon. Walter Feit and Graham Higman proved in 1964 that such geometries exist only for these few shapes, which is why the even-girth Moore graphs stop at twelve.

For odd girth greater than five, Eiichi Bannai and Tatsuro Ito, and independently Robert Damerell, proved in 1973 that no Moore graphs exist at all except the odd cycles themselves. The pentagon, the Petersen graph, the Hoffman–Singleton graph and the missing one are the only Moore graphs of odd girth beyond the trivial ones.

The Petersen graph’s other lives #

The Petersen graph turns up so often that it has become the standard counterexample of graph theory, and its role as a Moore graph explains some of its other appearances.

It is the Kneser graph on the pairs from five things: one point for each of the ten pairs, two points joined when their pairs share nothing. Several colours on every vertex and its predecessor coloured exactly this family and found that three colours are needed. It cannot be drawn in the plane without crossings, yet contains no stretched copy of $K_5$, since no point has four neighbours; five spokes squeezed into K5 contracted its spokes and found $K_5$ anyway. And it is a Moore graph: the most points a graph of degree three can have if every point is within two steps of every other.

These are not three coincidences. A graph that is extremal in one sense is usually extremal in several, because extremality forces symmetry and symmetry makes a graph special in every direction at once. The Petersen graph has 120 symmetries, as many as the ways of permuting five things, since each permutation of the five things permutes the ten pairs.

Designing networks two steps wide #

The Moore bound is also a practical question. A network of computers or switches, each connected to $d$ others, should have every node close to every other, and the degree–diameter problem asks for the largest network with degree $d$ and every node within $k$ steps of every other. The Moore bound caps the answer, and for diameter two and degree seven the Hoffman–Singleton graph achieves it.

For the degrees where no Moore graph exists, the best known networks fall short of the bound, and the gap is the subject of an active search. For diameter two and degree three the best is the Petersen graph itself; for larger degrees, graphs with close to $d^2$ points are known from constructions based on finite fields, and tables of the largest known graphs for each degree and diameter are maintained and improved by computer searches. The Moore graphs are the ideal these networks aim at, and their near-nonexistence is the reason the tables are full of approximations.

Why rigidity makes existence rare #

The pattern across these results is that meeting a counting bound exactly forces an algebraic identity — here $A^2 + A - (d-1)I = J$ — and the identity forces integrality conditions that almost nothing satisfies.

The same phenomenon appeared in the orders a plane cannot have, where a projective plane of order $n$ forced the matrix identity $NN^{\mathsf T} = nI + J$, and the Bruck–Ryser theorem turned that into a condition on sums of squares that rules out orders six, fourteen and infinitely many others. In both cases the counting is easy and the conclusion is drastic: a structure that is perfectly efficient must be perfectly regular, and perfect regularity is a strong arithmetic constraint. The eigenvalues are where the arithmetic shows.

What the figures can and cannot show #

The graphs are built and checked, not quoted. The Petersen and Hoffman–Singleton graphs are constructed from their rules, and their degrees, girths and breadth-first layers are computed; the claim that they meet the Moore bound is verified, not assumed.

The degree restriction is computed from the formula for every degree to sixty. That the four survivors are the only ones for all degrees is the divisibility argument, which the figure illustrates and does not replace.

The cage sizes are quoted. The smallest graphs of girth seven and above were found by long computer searches and by constructions, and are taken from the published record; only the Moore bounds beside them, and the Petersen graph’s place in the table, are computed here.

Still open: the graph of degree 57 #

A Moore graph of degree $57$ would have $3{,}250$ points, each with $57$ neighbours, no triangles, no four-cycles, and every point within two steps of every other. The eigenvalue argument allows it: its eigenvalues would be $57$, $7$ and $-8$, with multiplicities $1$, $1{,}729$ and $1{,}520$, all whole numbers.

The multiplicity $1{,}729$ is, as it happens, the number Ramanujan called interesting from a hospital bed: the smallest number that is a sum of two cubes in two different ways. It has no known connection to the graph; it is simply what the arithmetic produces.

Whether it exists is unknown, and it is one of the best-known open problems in graph theory. What is known is a list of things it cannot be. Graham Higman showed that it cannot be vertex-transitive — its symmetries cannot carry every point to every other — and Michael Aschbacher showed in 1971 that it cannot have a rank-three symmetry group. Later work by Martin Mačaj and Jozef Širáň bounded the size of its symmetry group to a few hundred at most. So if the graph exists it is nearly without symmetry, which is exactly what makes it hard to find: every successful construction of a Moore graph so far, including Robertson’s, has leaned on a large group of symmetries, and this one would have to be built without one.

Efficiency that almost never happens #

The habit worth keeping is to ask what exactness costs.

The Moore bound is easy to prove and easy to nearly meet: many graphs come close. Meeting it exactly turns a count into an equation, and the equation into eigenvalues, and the eigenvalues into a condition that only four degrees satisfy. Three of the four are realised by graphs of unusual beauty, and the fourth is a single question — whether a perfectly efficient graph on 3,250 points can exist without any of the symmetry that every other perfect structure has needed.