No graph of maximum degree , diameter 2 and vertices exists for . None of maximum degree , diameter 3 and vertices exists for . Conde and Gimbert had excluded 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 17; at diameter 3, was excluded 3, and so was cyclic defect for every 4, 5. Henriksson posted an unreviewed proof for 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 and diameter . The order is at most the Moore bound, for and for . A graph two short of it has defect 2. Five such graphs are known, for at diameter 2 and at diameter 3 9.
For Miller, Nguyen and Pineda-Villavicencio conjectured that none exists at diameter 2 2. Their theorems exclude odd other than and ( an integer), even , and every for which the number of 5-cycles forced on the graph is not an integer, with for even and for odd . 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 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 , , each putting the smaller of the values on lines and on line . 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 , diameter 2 and order exists for .
Theorem 2 (Diameter 3). No graph of maximum degree , diameter 3 and order exists for .
All three results are computer-assisted proofs. For , Theorem 1 rests on one certificate for each pair , indexing the polynomials defined below, with , , for the 1,497 even and the 105 odd of the forms and : 4,705,916,429 pairs. The case 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, , 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 for the least size of a network that puts the largest of inputs on lines. The output lines are forced: the -th smallest ends on line from the top and the largest on the bottom lines. The median of nine needs exactly 19 comparators.
| -th smallest on a line, | largest on lines, | two middle values | |
|---|---|---|---|
| 3 | 2, 3 | 2 | none |
| 4 | 3, 5 | 3, 4 | 4 |
| 5 | 4, 7, 7 | 4, 6 | none |
| 6 | 5, 9, 10 | 5, 8, 8 | 10 |
| 7 | 6, 11, 12, 13 | 6, 10, 11 | none |
| 8 | 7, 13, 14, 16 | 7, 12, 13, 14 | 16 |
| 9 | 8, 15, 16, 19, 19 | 8, 14, 15, 17 | none |
Why it is true
A graph as in Theorem 1 has vertices and is -regular 3. Let be its adjacency matrix, the identity and the all-ones matrix. Then has non-negative integer entries, zero diagonal and row sums 2, since the non-returning walks of length 1 or 2 from a vertex reach the other vertices, each at least once. So 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 of goes with the eigenvalue of , and a cycle of length has eigenvalues . So the eigenvalues of are roots of , with the minimal polynomial of , and the roots of an irreducible have equal multiplicity 1, 2.
Take and suppose is irreducible for , . For it is a quadratic with rational roots only for , , , , respectively, and for at most one . The multiplicities are then forced, apart from the two rational roots, if any, whose multiplicities may differ. A graph needs , with the number of triangles, (proved from the cycle structure of ), and . For even without rational roots, . For or , fixes that difference and then . For it forces , and for it forces . Other odd fail by a parity count of cycles 2.
is reducible only if is a square in , and then the square root is an algebraic integer, so its reduction modulo a prime is a square. Let , let have order in and let be coprime to . If is a quadratic non-residue modulo , then is irreducible. One such per pair is the certificate.
At diameter 3, with vertices, non-backtracking walks of length at most 3 give 4, with and again the adjacency matrix of disjoint cycles. The eigenvalues of are roots of . If this is reducible, has a root in , so a prime at which has no root in is a certificate. With every irreducible, . For some has a rational root, with the root of for , and and then give different values for the difference of two multiplicities. For , , and needs that difference to be .
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 comparators is a family of finite sets of states, the images of those inputs under networks, with the initial state in , no state having the property, and every comparator taking a state of , , to one equal, up to relabelling of lines and, for symmetric problems, complementation, to a state of some , . No network of fewer than comparators then has the property. An upper bound is an explicit network checked on all 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 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 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 at diameter 2 remains a conjecture 2. At diameter 3 the classification is listed as open 9, and remains open so far as we know. The method gives a proof for all at diameter 2 and all at diameter 3 once every and with , is irreducible, and a reducible case may still be excluded by traces, as is. Nothing is shown about the structure of a hypothetical graph beyond regularity, 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 , conjectured that they are irreducible, and verified it with PARI for even from 8 to 50 1. Nguyen and Miller 18 set up for defect 2 and excluded , 8 and infinitely many odd , as reported in 1, and Fajtlowicz 17 had treated the case that is one cycle. Miller, Nguyen and Pineda-Villavicencio gave the spectrum of for any cycle structure of and the theorems above 2. We add prime certificates, which replace PARI for and reach without the structure theorem, and a direct proof of the weaker bound , where the structure theorem of Nguyen and Miller, as quoted in 1, 2, fixes the number of triangles. We re-prove by an exact computation and at diameter 3 by a spectral route.
Delorme and Pineda-Villavicencio used , the polynomials and the integer-root argument when 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 by trace equations and certify irreducibility by primes. Feria-Purón, Miller and Pineda-Villavicencio excluded by counting cycles, and their even- theorem needs diameter at least 4 3. Garbe's abstract states non-existence for odd 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 in certain classes 16. Diameter 3 is girth 7, so a statement for diameter 3 cannot be ruled out, for and 9 in particular. Searches of arXiv, Zenodo, Crossref and the web to 2026-11-15 found no other result for diameter 3 with , or beyond 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 and exceeds for every 6. As , this excludes defect 2 for . 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 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 comparators (14 values), and the two largest take (6 values) 13. The value starts Yao's recursion for the three largest 15. Knuth's exercise 5.3.4-20 gives the upper bound for the four largest and adds that equality probably holds 13, which gives by symmetry, and . Qu, Tasbihi and Kschischang conjectured with a network of 14 comparators or minselectors 14. Tomar's preprint of 2026-10-29 (v1) independently proves for and for 15. These include six of our values, for , and . It says nothing of medians.
References
- 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.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.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.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.M. Miller, "Nonexistence of graphs with cyclic defect", Electron. J. Combin. 18, P71 (2011). doi.org/10.37236/558
- 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.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.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.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.B. Dobbelaere, "List of median selection networks", web page, updated 2026-11-08. bertdobbelaere.github.io/median_networks.html
- 11.A. Paeth, "Non-Interfering Concurrent Exchange (NICE) Networks", arXiv:1808.05212 (2018). arxiv.org/abs/1808.05212
- 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.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.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.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.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.S. Fajtlowicz, "Graphs of diameter 2 with cyclic defect", Colloq. Math. 51, 103 (1987). doi.org/10.4064/cm-51-1-103-106
- 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