About the problem
The girth of a graph is the length of its shortest cycle. The diameter of a graph is the maximum distance between two vertices in the graph. A Moore graph is a graph where every vertex has the same degree (i.e. the graph is regular), and such that the girth of the graph is more than twice as large as its diameter.
Hoffman and Singleton studied the case where the diameter of interest is 2, i.e. every two vertices in the graph are either adjacent or have a common neighbor. They showed that Moore graphs with diameter 2 are always strongly regular, and must have degree 2, 3, 7, or 57. Moore graphs with diameter 2 and degree 2, 3, and 7 are known to exist, but it is not known whether a Moore graph with diameter 2 and degree 57 exists. This is the only possible Moore graph whose status is unknown, since Damerell proved that, other than diameter 2, the only Moore graphs are odd cycles.
This problem asks models to submit the missing Moore graph, i.e. a strongly regular graph with parameters (3250, 57, 0, 1). Like Conway’s 99-graph, the verifier checks that the properties are satisfied, and the main risk is that the missing Moore graph does not exist.
Prompt
Your task is to find the missing Moore graph.
A Moore graph is a graph that achieves the Moore bound: the maximum possible number of vertices for a given degree k and diameter d. For degree k and diameter d=2, the Moore bound is 1 + k + k(k-1) = k^2 + 1 vertices.
Moore graphs of diameter 2 are known to exist for degrees k = 2 (the 5-cycle), k = 3 (the Petersen graph), and k = 7 (the Hoffman-Singleton graph). It was proved by Hoffman and Singleton in 1960 that the only remaining possible degree is k = 57, which would give a graph on 57^2 + 1 = 3250 vertices. Whether this graph exists is one of the oldest open problems in graph theory. It has never been found, and it has never been proved not to exist — hence the name "the missing Moore graph."
A graph is the missing Moore graph if and only if it satisfies all of the following:
1. It has exactly 3250 vertices, labelled 1 through 3250.
2. Every vertex has degree exactly 57 (it is 57-regular).
3. Every pair of non-adjacent vertices has exactly 1 common neighbor (diameter 2).
4. No two adjacent vertices share a common neighbor.
Conditions 3 and 4 together make it a strongly regular graph with parameters srg(3250, 57, 0, 1).
Your task is to construct such a graph and write it to a file. The file should contain exactly one edge per line, in the following format:
{x, y}
where x and y are integers between 1 and 3250 (inclusive). List each edge once only (do not list both {x, y} and {y, x}). The file should contain exactly 92625 edges (since 3250 * 57 / 2 = 92625).
Example of correctly formatted lines:
{1, 2}
{1, 3}
{2, 57}