Triangle free strongly regular graphs
Status open high confidence
As of 2026, exactly seven triangle-free strongly regular graphs are known (the 5-cycle, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Higman-Sims, and the $(77,16,0,4)$ Higman-Sims subgraph), and the question of whether an eighth exists remains open. The most natural candidate is the hypothetical Moore graph of degree 57, which would give a strongly regular graph with parameters $(3250, 57, 0, 1)$; a 2020 claimed proof of its non-existence was shown to be flawed (Faber and Keegan, 2022), and the existence question remains one of the most famous open problems in algebraic graph theory.
Cited literature (2)
-
Refutes a 2020 claimed proof that no Moore graph of degree 57 exists, showing the underlying system of equations has solutions in each diagonal block, and reformulates the existence question as: the Moore graph exists if and only if a certain family of permutation systems with specific properties has no solutions.
-
Comprehensive monograph on strongly regular graphs covering all known triangle-free examples and the open problem of whether an eighth exists, including a complete table of feasible parameter sets with up to 1300 vertices.
Reviewer notes. Several additional post-2007 papers were found in search results but could not be verified due to HTTP 403 responses from MDPI and ScienceDirect: 'The Moore Graph of Diameter 2 and Degree 57 via Cyclic Derangements' (Smith & Montemanni, Axioms 2026, reportedly proving that constructions using only a cyclic group of derangements are impossible), 'Potential Subgraphs of the Missing Moore Graph' (MDPI 2024), and 'The missing Moore graph as an optimization problem' (ScienceDirect 2023). These could not be cited per protocol. The Faber-Keegan paper is the sole directly verifiable post-2007 contribution; it confirms the problem remains open.
Discussion
A regular graph $ G $ is strongly regular if there exist integers $ \lambda, \mu $ so that every pair of adjacent vertices have exactly $ \lambda $ common neighbors, and every pair of nonadjacent vertices have exactly $ \mu $ common neighbors. To eliminate degeneracies, we shall further assume that $ \mu \ge 1 $ . If $ G $ is $ k $ -regular and $ |V(G)| = n $ , then we say that $ G $ is a $ (n,k,\lambda,\mu) $ strongly regular graph. There are exactly seven triangle-free strongly regular graphs known: The five cycle, the Petersen Graph , The Clebsch Graph, the Hoffman-Singleton Graph , The Gewirtz Graph, the Higman-Sims Graph, and a $ (77,16,0,4) $ strongly regular subgraph of the Higman-Sims graph. Every Moore Graph of diameter 2 is a triangle-free strongly regular graph, so if there is a 57-regular Moore Graph of diameter 2, this would add another to the list. See Andries Brouwer's graph descriptions for more on these graphs.
Bibliography
-
[G]C. D. Godsil, Problems in Algebraic Combinatorics , Electronic Journal of Combinatorics, Volume 2, F1 Problems in Algebraic Combinatorics