Additional random facts.

The Peterson Graph can be obtained by identifying the antipodal points of a dodecahedron and it has $S_5$ as its automorphism group (order 120 of course).

There are a number of geometric constructions of the Hoffman-Singleton Graph (the 25 points and 25 non-vertical lines of an affine plane over $Z_5$ are used in one , the 15 points and 35 lines of projective 3-space over $Z_2$ in another). The automorphism group has order 252000.

A Moore graph of degree 57, if it exists, ~~would have a trivial automorphism group:~~ would have to have a small automorphism group.
**edit** See the comment below from Chris Godsil

Aschbacher, M. "The Non-Existence of Rank Three Permutation Group of Degree 3250 and Subdegree 57." J. Algebra 19, 538-540, 1971.

Here is a good reference from 2010: Search for properties of the missing Moore graph which shows among other things that if such a graph exists then it has automorphism group of order at most 375.

**later** Since we have new interest I'll add some beautiful well known facts.

The triangle graph $T_5$ is the line graph of $K_5$ and is regular of degree 6 with 10 vertices. So $S_5$ acts on it and that is the full automorphism group. As mentioned by N. Elkies, the Peterson graph is the complement of $T_5$. $T_5$ has five maximal cliques $K_4$ corresponding to the 5 vertices. These become the five totally disconnected 4-vertex induced sub-graphs (independent sets) mentioned by R. Bell. If we fix one such independent 4-set, connect one new vertex with each of the six pairs and then connect each of these to the one pair disjoint from it, we get the Peterson Graph. So this is the points and edges of a tetrahedron.

In a Moore graph of order 7 the largest independent sets have 15 vertices. The incidence between these and the other 35 is the same as that between the points and blocks of a certain resolvable Steiner triple system and (equivalently) that between the 15 points and 35 lines of PG(3,2). These descriptions leave some edges unspecified, but:

Consider the 35 triples from $\{a,b,c,d,e,f,g\}$ as labels for 35 vertices and connect each to the four with labels disjoint from its own. There are 30 *heptads* being choices of seven triples no two disjoint (so forming a Fano plane). $S_7$ is transitive on these but $A_7$ has two orbits of size 15. If we use one such orbit to label 15 more vertices and make the obvious connections, we get the Moore graph of order 7.

The Peterson graph has a nice description in terms of the 4 points and 6 edges of a tetrahedron or PG(3,1) if we abuse notation. The Moore graph of order 7 has a nice description in terms of the 15 points and 35 lines of PG(3,2). Now, PG(3,7) has 400 points and 2850 lines and if there is a Moore graph of order 57 (warning! warning! Many would conjecture that there is none!) then it has 400+2850 vertices of which at most 400 could be independent... The fact that a large automorphism group has been ruled out makes this an unpromising approach, but who knows?

whyexactly it is such a mysterious and exciting open problem! $\endgroup$ – Mariano Suárez-Álvarez Jan 30 '12 at 0:18