You may have heard about the open problem on Moore graphs which is one of the most famous problems in Algebraic Graph Theory. Here is a brief synopsis…
A Moore graph is a regular graph which is extremal in the sense that its number of vertices is large compared to its degree
Theorem: Any Moore graph with diameter 2 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, and these are the unique such diameter 2 graphs with these degrees. The last case, degree 57, is unsolved; we still do not yet know whether such a graph exists!
What we do know is that a Moore graph of diameter 2 and degree 57 is vertex-intransitive and the automorphism group has order not divisible by 4. In fact, an involutary automorphism must fix 56 points. Not much more could be said until very recently, and I want to make special mention of a recent preprint of Martin Mačaj and Jozef Širáň. They prove that the automorphism group must have size at most 375.
So what do you think? Does a Moore graph of diameter 2 and degree 57 exist?Does a Moore graph of diameter 2 and degree 57 exist?