Research · White paper · Chip design

Graphs two below the Moore bound, and the median of nine inputs

No graph of maximum degree dd, diameter 2 and d2−1d^2-1 vertices exists for 6≤d≤30006\le d\le3000. None of maximum degree dd, diameter 3 and d3−d2+d−1d^3-d^2+d-1 vertices exists for 4≤d≤1504\le d\le150. Conde and Gimbert had excluded 6≤d≤506\le d\le50 1, and Miller, Nguyen and Pineda-Villavicencio all but 362 of the degrees from 51 to 3000, by our count 2. At diameter 2, Fajtlowicz excluded cyclic defect for d≠3d\ne3 17; at diameter 3, d=4d=4 was excluded 3, and so was cyclic defect for every dd 4, 5. Henriksson posted an unreviewed proof for d≥1025d\ge1025 on 2026-11-13 6. We found no other earlier result in searches to 2026-11-15, but could not read Garbe's paper 7.

Separately, the median of nine inputs needs exactly 19 comparators in a comparator network. A 19-comparator network was published by 1996 8. In searches of arXiv, Zenodo and the web to 2026-11-15 we found no earlier proof that it is minimal, and we could not read every original source.

The question

The degree-diameter problem, from the design of interconnection networks 2, asks for the largest finite simple graph of maximum degree dd and diameter kk. The order is at most the Moore bound, d2+1d^2+1 for k=2k=2 and d3−d2+d+1d^3-d^2+d+1 for k=3k=3. A graph two short of it has defect 2. Five such graphs are known, for 3≤d≤53\le d\le5 at diameter 2 and d=3d=3 at diameter 3 9.

For d≥6d\ge6 Miller, Nguyen and Pineda-Villavicencio conjectured that none exists at diameter 2 2. Their theorems exclude odd dd other than l2+l−1l^2+l-1 and l2+l+3l^2+l+3 (ll an integer), even d≢1(mod3)d\not\equiv1\pmod 3, and every dd for which the number N5N_5 of 5-cycles forced on the graph is not an integer, with N5=(d−2)(d4+2d2−2d−25)/10N_5=(d-2)(d^4+2d^2-2d-25)/10 for even dd and (d2−1)(d3−2d2+3d−8)/10(d^2-1)(d^3-2d^2+3d-8)/10 for odd dd. These theorems draw on a structure theorem of Nguyen and Miller 18, as quoted in 2, which we did not re-verify. This leaves 362 degrees from 51 to 3000, 295 even and 67 odd. At diameter 3 the classification is listed as open 9. Cyclic defect means that the matrix BB of the proof sketch below is a single cycle.

A median filter replaces each pixel by the median of its 3×3 neighbourhood, and hardware finds it with a comparator network 8: a sequence of comparators [i:j][i:j], i<ji<j, each putting the smaller of the values on lines ii and jj on line ii. The size is the number of comparators, and a comparator with an unused output counts once, so counts of min and max operations measure something else. Smith asserted without proof that 19 is the least size for the median of nine.

What we found

Theorem 1 (Diameter 2). No graph of maximum degree dd, diameter 2 and order d2−1d^2-1 exists for 6≤d≤30006\le d\le3000.

Theorem 2 (Diameter 3). No graph of maximum degree dd, diameter 3 and order d3−d2+d−1d^3-d^2+d-1 exists for 4≤d≤1504\le d\le150.

All three results are computer-assisted proofs. For 7≤d≤30007\le d\le3000, Theorem 1 rests on one certificate for each pair (d,i)(d,i), ii indexing the polynomials Fi,dF_{i,d} defined below, with 5≤i≤d2−15\le i\le d^2-1, i≠6i\ne6, for the 1,497 even dd and the 105 odd dd of the forms l2+l−1l^2+l-1 and l2+l+3l^2+l+3: 4,705,916,429 pairs. The case d=6d=6 is an exhaustive exact computation over 2,573 cycle structures and 4,910 multiplicity assignments. Theorem 2 rests on 127,129,765 pairs, one of which, (4,10)(4,10), is reducible and is excluded by a trace argument.

We also computed the least size of a comparator network for 45 selection problems with 3 to 9 inputs, writing top(n,t)\mathrm{top}(n,t) for the least size of a network that puts the tt largest of nn inputs on tt lines. The output lines are forced: the tt-th smallest ends on line tt from the top and the tt largest on the bottom tt lines. The median of nine needs exactly 19 comparators.

nntt-th smallest on a line, t=1,2,…t=1,2,\dotstt largest on tt lines, t=1,2,…t=1,2,\dotstwo middle values
32, 32none
43, 53, 44
54, 7, 74, 6none
65, 9, 105, 8, 810
76, 11, 12, 136, 10, 11none
87, 13, 14, 167, 12, 13, 1416
98, 15, 16, 19, 198, 14, 15, 17none
Least number of comparators, 23 + 19 + 3 = 45 values; medians in bold. Larger tt follow by symmetry.

Why it is true

A graph GG as in Theorem 1 has n=d2−1n=d^2-1 vertices and is dd-regular 3. Let AA be its adjacency matrix, II the identity and JJ the all-ones matrix. Then B=A2+A−(d−1)I−JB=A^2+A-(d-1)I-J has non-negative integer entries, zero diagonal and row sums 2, since the d2d^2 non-returning walks of length 1 or 2 from a vertex reach the other d2−2d^2-2 vertices, each at least once. So BB is the adjacency matrix of disjoint cycles, a double edge counting as a cycle of length 2 2. Off the all-ones vector an eigenvalue λ\lambda of AA goes with the eigenvalue μ=λ2+λ+1−d\mu=\lambda^2+\lambda+1-d of BB, and a cycle of length LL has eigenvalues 2cos⁡(2πk/L)2\cos(2\pi k/L). So the eigenvalues of AA are roots of Fi,d(x)=fi(x2+x+1−d)F_{i,d}(x)=f_i(x^2+x+1-d), with fif_i the minimal polynomial of 2cos⁡(2π/i)2\cos(2\pi/i), and the roots of an irreducible Fi,dF_{i,d} have equal multiplicity 1, 2.

Take d≥7d\ge7 and suppose Fi,dF_{i,d} is irreducible for 5≤i≤d2−15\le i\le d^2-1, i≠6i\ne6. For i=1,2,3,4,6i=1,2,3,4,6 it is a quadratic with rational roots only for d=l2+l−1d=l^2+l-1, l2+l+3l^2+l+3, l2+l+2l^2+l+2, l2+l+1l^2+l+1, l2+ll^2+l respectively, and for at most one ii. The multiplicities are then forced, apart from the two rational roots, if any, whose multiplicities may differ. A graph needs tr A=0\mathrm{tr}\,A=0, tr A3=6τ\mathrm{tr}\,A^3=6\tau with τ\tau the number of triangles, τ<n/6\tau<n/6 (proved from the cycle structure of BB), and tr AB2≥0\mathrm{tr}\,AB^2\ge0. For even dd without rational roots, tr A=−(d2−2d−2)/2≠0\mathrm{tr}\,A=-(d^2-2d-2)/2\ne0. For d=l2+l+2d=l^2+l+2 or l2+ll^2+l, tr A=0\mathrm{tr}\,A=0 fixes that difference and then tr AB2<0\mathrm{tr}\,AB^2<0. For d=l2+l−1d=l^2+l-1 it forces τ=n/6\tau=n/6, and for d=l2+l+3d=l^2+l+3 it forces tr A3<0\mathrm{tr}\,A^3<0. Other odd dd fail by a parity count of cycles 2.

Fi,dF_{i,d} is reducible only if 4d−3+8cos⁡(2π/i)4d-3+8\cos(2\pi/i) is a square in Q(cos⁡(2π/i))\mathbb Q(\cos(2\pi/i)), and then the square root is an algebraic integer, so its reduction modulo a prime is a square. Let p≡1(modi)p\equiv1\pmod i, let ww have order ii in Fp\mathbb F_p and let jj be coprime to ii. If 4d−3+4(wj+w−j)4d-3+4(w^j+w^{-j}) is a quadratic non-residue modulo pp, then Fi,dF_{i,d} is irreducible. One such pp per pair (d,i)(d,i) is the certificate.

At diameter 3, with n=d3−d2+d−1n=d^3-d^2+d-1 vertices, non-backtracking walks of length at most 3 give g(A)=J+Bg(A)=J+B 4, with g(x)=x3+x2−(2d−2)x+1−dg(x)=x^3+x^2-(2d-2)x+1-d and BB again the adjacency matrix of disjoint cycles. The eigenvalues of AA are roots of Hi,d=fi(g(x))H_{i,d}=f_i(g(x)). If this is reducible, g(x)−2cos⁡(2π/i)g(x)-2\cos(2\pi/i) has a root in Z[2cos⁡(2π/i)]\mathbb Z[2\cos(2\pi/i)], so a prime p≡1(modi)p\equiv1\pmod i at which g(x)−(wj+w−j)g(x)-(w^j+w^{-j}) has no root in Fp\mathbb F_p is a certificate. With every Hi,dH_{i,d} irreducible, tr A=−(d3−d2−2d−2)/3≠0\mathrm{tr}\,A=-(d^3-d^2-2d-2)/3\ne0. For d∈{5,6,8,10,12,27,31,35,39}d\in\{5,6,8,10,12,27,31,35,39\} some g(x)−μg(x)-\mu has a rational root, with μ=2,−2,−1,0,1\mu=2,-2,-1,0,1 the root of fif_i for i=1,2,3,4,6i=1,2,3,4,6, and tr A=0\mathrm{tr}\,A=0 and tr A2=nd\mathrm{tr}\,A^2=nd then give different values for the difference of two multiplicities. For (4,10)(4,10), f10(g)=(x2+3x+1)(x4−x3−9x2+9x+11)f_{10}(g)=(x^2+3x+1)(x^4-x^3-9x^2+9x+11), and tr A=0\mathrm{tr}\,A=0 needs that difference to be −38/7-38/7.

For selection, a network has the required property on all real inputs if and only if it has it on all 0-1 inputs, and the 0-1 inputs of one to three fixed weights decide it. A lower bound of KK comparators is a family of finite sets L0,…,LK−1L_0,\dots,L_{K-1} of states, the images of those inputs under networks, with the initial state in L0L_0, no state having the property, and every comparator taking a state of LkL_k, k≤K−2k\le K-2, to one equal, up to relabelling of lines and, for symmetric problems, complementation, to a state of some LjL_j, j≤k+1j\le k+1. No network of fewer than KK comparators then has the property. An upper bound is an explicit network checked on all 2n2^n 0-1 inputs.

How it was checked

A standalone C program of about 160 lines per diameter tests, for every pair, primality, the order of ww and the residue or root condition. A second checker, written separately with different algorithms, recomputed all 4,705,916,429 and all 127,129,765 certificates and reproduced the stored exceptions exactly. Exact factorisation of 20,158 pairs found no reducible polynomial that a certificate accepted. Corrupted certificates are rejected, and the five known defect-2 graphs satisfy the identities. The case d=6d=6 was recomputed by separate code. For selection, separately written code reproduced all 45 values, and a separately written checker accepted all 45 certificates and rejected corrupted copies of two of them.

A separate automated review, by an AI model, re-derived the hand proofs line by line; the second checkers and the review were also written by AI models, so they are independent in code and algorithm, not in kind of author. The proofs have not been peer reviewed, and no human has reviewed the diameter checkers line by line.

What it does not show

Non-existence for all d≥6d\ge6 at diameter 2 remains a conjecture 2. At diameter 3 the classification is listed as open 9, and 151≤d≤1024151\le d\le1024 remains open so far as we know. The method gives a proof for all d≥7d\ge7 at diameter 2 and all d≥4d\ge4 at diameter 3 once every Fi,dF_{i,d} and Hi,dH_{i,d} with i≥5i\ge5, i≠6i\ne6 is irreducible, and a reducible case may still be excluded by traces, as (4,10)(4,10) is. Nothing is shown about the structure of a hypothetical graph beyond regularity, BB and the triangle bound, or about diameter 4 or more.

The selection sizes say nothing about depth or about adaptive selection, which can need fewer comparisons.

Earlier and parallel work

Conde and Gimbert gave a non-existence criterion in terms of irreducibility of the polynomials Fi,dF_{i,d}, conjectured that they are irreducible, and verified it with PARI for even dd from 8 to 50 1. Nguyen and Miller 18 set up A2+A−(d−1)I=J+BA^2+A-(d-1)I=J+B for defect 2 and excluded d=6d=6, 8 and infinitely many odd dd, as reported in 1, and Fajtlowicz 17 had treated the case that BB is one cycle. Miller, Nguyen and Pineda-Villavicencio gave the spectrum of AA for any cycle structure of BB and the theorems above 2. We add prime certificates, which replace PARI for 7≤d≤507\le d\le50 and reach d=3000d=3000 without the structure theorem, and a direct proof of the weaker bound τ<n/6\tau<n/6, where the structure theorem of Nguyen and Miller, as quoted in 1, 2, fixes the number of triangles. We re-prove d=6d=6 by an exact computation and d=4d=4 at diameter 3 by a spectral route.

Delorme and Pineda-Villavicencio used g(A)=J+Bg(A)=J+B, the polynomials Hi,dH_{i,d} and the integer-root argument when BB is one cycle, and excluded that case at diameter 3 4, and Miller at every diameter at least 3 5. We treat every cycle structure of BB by trace equations and certify irreducibility by primes. Feria-Purón, Miller and Pineda-Villavicencio excluded d=4d=4 by counting cycles, and their even-dd theorem needs diameter at least 4 3. Garbe's abstract states non-existence for odd dd at diameter 4 and similar statements for defect 2 7. We could not read the paper. A secondary description lists its results for girths 9, 13, 17, 21, 25 and 29 and, for degrees 3, 7 and 9, for girths 2s+12s+1 in certain classes 16. Diameter 3 is girth 7, so a statement for diameter 3 cannot be ruled out, for d=7d=7 and 9 in particular. Searches of arXiv, Zenodo, Crossref and the web to 2026-11-15 found no other result for diameter 3 with 5≤d≤1505\le d\le150, or beyond d=50d=50 at diameter 2 apart from 2.

Henriksson posted on 2026-11-13, and revised on 2026-11-15, a computer-assisted proof that the defect at diameter 3 is at least of order d\sqrt d and exceeds d−1/8\sqrt{d-1}/8 for every d≥1025d\ge1025 6. As 1024/8=4\sqrt{1024}/8=4, this excludes defect 2 for d≥1025d\ge1025. It states that AI models took part, that the proof was checked in Lean 4 and that it has not been independently reviewed. We have not examined it. Ours adds every dd from 4 to 150, below the cutoff of the preprint, and the diameter-2 range.

Smith's 1996 article shows a 19-comparator network as the minimum exchange network, without a proof 8. Dobbelaere's list marks it optimal and cites Smith 10. Paeth derives a 19-link network from the 3×3 design of his 1990 chapter and claims no optimality for it 11. We found no earlier proof of minimality in searches of arXiv, Zenodo and the web to 2026-11-15. Knuth's section 5.3.4 and Yao's thesis reached us only through Tomar 15, and Paeth's 1990 chapter and a 1994 paper of Chakrabarti and Wang 12, whose network a 2017 Stack Overflow question says reduces to Smith's, not at all, so priority of the proof is not established.

Of the 45 values, 24 were known or expected. Selecting the minimum or the maximum takes n−1n-1 comparators (14 values), and the two largest take 2n−42n-4 (6 values) 13. The value top(6,3)=8\mathrm{top}(6,3)=8 starts Yao's recursion for the three largest 15. Knuth's exercise 5.3.4-20 gives the upper bound 3n−103n-10 for the four largest and adds that equality probably holds 13, which gives top(7,3)=11\mathrm{top}(7,3)=11 by symmetry, top(8,4)=14\mathrm{top}(8,4)=14 and top(9,4)=17\mathrm{top}(9,4)=17. Qu, Tasbihi and Kschischang conjectured top(8,4)=14\mathrm{top}(8,4)=14 with a network of 14 comparators or minselectors 14. Tomar's preprint of 2026-10-29 (v1) independently proves top(n,3)\mathrm{top}(n,3) for 4≤n≤184\le n\le18 and top(n,4)\mathrm{top}(n,4) for 6≤n≤126\le n\le12 15. These include six of our values, top(n,3)\mathrm{top}(n,3) for 6≤n≤96\le n\le9, top(8,4)\mathrm{top}(8,4) and top(9,4)\mathrm{top}(9,4). It says nothing of medians.

References

  1. 1.J. Conde and J. Gimbert, "On the existence of graphs of diameter two and defect two", Discrete Math. 309, 3166 (2009). doi.org/10.1016/j.disc.2008.09.017
  2. 2.M. Miller, M. H. Nguyen and G. Pineda-Villavicencio, "On the nonexistence of graphs of diameter 2 and defect 2", J. Combin. Math. Combin. Comput. 71, 5 (2009). www.guillermo.com.au/pdfs/BothDegrees.pdf
  3. 3.R. Feria-Purón, M. Miller and G. Pineda-Villavicencio, "On graphs of defect at most 2", Discrete Appl. Math. 159, 1331 (2011), arXiv:1010.5658. arxiv.org/abs/1010.5658
  4. 4.C. Delorme and G. Pineda-Villavicencio, "On graphs with cyclic defect or excess", Electron. J. Combin. 17, R143 (2010), arXiv:1010.5841. arxiv.org/abs/1010.5841
  5. 5.M. Miller, "Nonexistence of graphs with cyclic defect", Electron. J. Combin. 18, P71 (2011). doi.org/10.37236/558
  6. 6.A. Henriksson, "Lowering the Moore bound for diameter three by order √d", Zenodo, v2, 2026-11-15; v1, "An unbounded Moore deficit at diameter three", 2026-11-13, doi:10.5281/zenodo.24190386. doi.org/10.5281/zenodo.24235473
  7. 7.F. Garbe, "On graphs with excess or defect 2", Discrete Appl. Math. 180, 81 (2015). doi.org/10.1016/j.dam.2014.07.022
  8. 8.J. L. Smith, "Implementing Median Filters in XC4000E FPGAs", Xcell 23, 16 (Xilinx, Q4 1996). users.utcluj.ro/~baruch/media/resources/Image/xl23_16.pdf
  9. 9.M. Miller and J. Širáň, "Moore graphs and beyond: a survey of the degree/diameter problem", Electron. J. Combin. DS14 (2013). doi.org/10.37236/35
  10. 10.B. Dobbelaere, "List of median selection networks", web page, updated 2026-11-08. bertdobbelaere.github.io/median_networks.html
  11. 11.A. Paeth, "Non-Interfering Concurrent Exchange (NICE) Networks", arXiv:1808.05212 (2018). arxiv.org/abs/1808.05212
  12. 12.C. Chakrabarti and L.-Y. Wang, "Novel sorting network-based architectures for rank order filters", IEEE Trans. VLSI Syst. 2, 502 (1994). doi.org/10.1109/92.335027
  13. 13.D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., section 5.3.4 and exercise 5.3.4-20 as replaced in the 2003 errata (Addison-Wesley, 1998), as quoted in 15. www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780201896855
  14. 14.Y. Qu, A. Tasbihi and F. R. Kschischang, "Constituent automorphism decoding of Reed–Muller codes", arXiv:2409.03700 (2024). arxiv.org/abs/2409.03700
  15. 15.T. S. Tomar, "Exact sizes of networks that select the three or four largest of n elements", Zenodo, v1, 2026-10-29. doi.org/10.5281/zenodo.23783464
  16. 16.T. B. Jajcayová, S. Filipovski and R. Jajcay, "Improved lower bounds for the orders of even girth cages", Electron. J. Combin. 23, P3.55 (2016). doi.org/10.37236/6015
  17. 17.S. Fajtlowicz, "Graphs of diameter 2 with cyclic defect", Colloq. Math. 51, 103 (1987). doi.org/10.4064/cm-51-1-103-106
  18. 18.M. H. Nguyen and M. Miller, "Structural properties of graphs of diameter 2 with maximal repeats", Discrete Math. 308, 2337 (2008), not read by us. doi.org/10.1016/j.disc.2006.09.057