A strongly regular graph has exactly three distinct eigenvalues. A Neumaier graph is a generalization: edge-regular, containing a regular clique, but not necessarily strongly regular. The question since Neumaier's original proposal has been whether such graphs can have exactly five distinct eigenvalues — sitting precisely between the three-eigenvalue world of strongly regular graphs and the unrestricted spectra of general graphs.
De Bruyn et al. (arXiv:2603.17029) find 25 of them. They construct a new family of Neumaier graphs with parameters (48, 14, 2; 1, 4) and identify 1,063 non-isomorphic examples, 25 of which have exactly five eigenvalues. These are the first known examples resolving the open question.
The significance is structural. The number of distinct eigenvalues of a graph controls its algebraic complexity — it determines the dimension of the algebra generated by the adjacency matrix. Three eigenvalues means the graph is completely determined by local parameters (degree, triangle count). Five eigenvalues means the graph encodes global structure that local parameters cannot capture, but with a degree of regularity that keeps the algebra finite-dimensional and tractable.
Finding that Neumaier graphs can sit at exactly five eigenvalues — not four, not six, but five — reveals a precise boundary. These graphs are irregular enough to escape the cage of strong regularity but structured enough to maintain spectral discipline. The existence proof required both theoretical construction and exhaustive computational search: 1,063 graphs checked, 25 qualifying.
The answer to “can this happen?” is yes, but it took 1,063 attempts to find 25 witnesses.