There could be several graphs opting for being the eighth one, but in particular the 57-regular Moore graph (we will denote this graph by M57) could be the 8th triangle free strongly regular graph. However, the existence of this M57 graph is an open problem as well.
M57: attempt 1
A first attempt to search for this M57 graph can be done by deriving all properties and wait till the graph shows up. This simple, but not at all useless attempt has brought us some facts and insight.
First we have a look at some other Moore graphs. For example, any odd cycle forms a Moore graph with degree 2, and any clique forms a Moore graph with diameter 1. The other known Moore graphs are:
- The Petersen graph with degree 3, diameter 2, and girth 5.
- The Hoffman-Singleton graph with degree 7, diameter 2, and girth 5.
With these graphs in mind, the follwing is very interesting. In 1960, a theorem called the The Hoffman-Singleton theorem, states that any Moore graph with girth 5 must have degree 2, 3, 7, or 57.
The graphs with degree 2, 3, and 7 are the pentagon, Petersen graph, and Hoffman-Singleton graph, respectively. A proof can be found in Biggs, 2003 (see references).
A note of interest of our conjecture: every Moore Graph of diameter 2 is a triangle-free strongly regular graph. So if the fourth one exists, it is the 57-regular Moore Graph of diameter 2, this would add another to the list.
Assuming the M57 graph does exist, some calculations can already be done.
- The number of vertices n of a k-regular Moore graph should be k2+1, where k=57 here. So M57 would have 3250 vertices.
- The graph is undirected en 'highly symmetric', i.e. every vertice has the same properties about neighbours. This gives us the opportunity to reorder the graph without disturbing its uniqueness.
All this describes the graph very good, but still says nothing about how likely it is that the graph actually exists.
M57: attempt 2
With the facts of the first attempt, a more constructive try is what is necessary. This next attempt to construct M57 I didn't found literally in the an article. However, the basics are, despite increasing the number of vertices and edges, the same as in 'Rick's Tricky Six Puzzle: S5 Sits Specially in S6', written in 2009 by Alex Fink and Richard Guy (see references).
Construction in a nutshell
To construct such a graph G, we can do the following steps:
- Connect 2 arbitrart vertices, a and b, this two vertices form the first level.
- Connect to both vertices 56 disjoint other vertices, a1, ... , a56 and b1, ... , b56 respectively, these form the second level.
- The third level contains the 'totals', ai,j with i, j = 1,...,56. Connect each vertex ai to ai,j for i, j = 1,...,56.
- This are all the vertices: 2 + 56 + 56 + 562 = 3250.
- The next step is to connect bj to ai,j for i, j = 1,...,56.
Now we only have to connect each ai,j to 55 other ai,j's in a good way. This good way is the hard part of the construction though, we do know that up to reordening the vertices (which has no effect in a graph) this is the only way to make a proper construction.
The automorphism group on K56
The graph G has ( 3 250 * 57 ) / 2 = 92 625 edges and therefor there are 92 625 automorphisms on G (since the vertices of G form a set, as a categorie, there is no structure to preserve).
By fixing a--b there are 56! automorphisms on G by permutating the vertices a1, ... , a56 (the vertices b1, ... , b56 change automaticly, by construction).
The 56! automorphisms on G form a group, the symmetric group S56. This group is isomorphic to the automorphism group on K56 under composition of morphisms. K56 is the complete graph with 56 vertices. A graph is complete if every pair of vertices is adjacent.
Remark that that the 57-regular Moore graph can not be vertex-transitive (proved by P. J. Cameron, Automorphisms of graphs in: Selected topics in graph theory, Volume 2, eds. L. W. Beineke and R. J. Wilson (Academic Press, London) 1983, pp. 89-127), but this says notting yet about edge transitivity. A semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. A semi-symmetric graph must be bipartite, and its automorphism group must act transitively on each of the two vertex sets of the bipartition. In a regular bipartite graph Kn,m n=m, and therefor should a graph with 3250 vertices (a property of a 57-regular Moore graph) be K1625,1625, so 1625-regular, which causes a contradiction. So neither the graph can be edgetransitive.
Comparing with the Hoffman-Singleton graph
Now notice, written down as a remark in 'Rick's Tricky Six Puzzle: S5 Sits Specially in S6', that "The symmetric group $ S_6 $ is the only finite symmetric group that supports a (nontrivial) outer automorphism" [11; 14, Theorem 7.3]. This might give reason to let the construction of M57 necessarily fail, but unfortunately I cannot tell if this is true. And if so, how.