The Missing Moore Graph

Gul Abdulnabi Agha, University of Illinois at Urbana-Champaign

Usage Details

This project aims to construct—or prove that it does not exist—the Moore Graph with girth 5 and degree 57. The existence of this graph has been an open question in graph theory since the 60s, yet various properties have been proven to hold, assuming it does, in fact, exist. We propose to formulate its construction as a state space search problem, and find it through exhaustive search. A naive implementation would take an exponential number of unnecessary steps; however, preliminary work shows that we can take advantage of its properties to prune the search tree enough, so that the exploration becomes, in fact, feasible. Still, the sheer size of the remaining exploration space renders the use of a supercomputer necessary to solve this problem.