Is there a $6$-regular graph of order $25$ and diameter $2$?
According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $n\leq r^2+1$.
When $n=25$, it follows that $r \geq 5$ and since $r$ must be even (the sum of the degrees must be even), it follows that $r\geq 6$.
I was able to build a $8$-regular graph, but not a $6$-regular graph. Is there such a construction?
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths: $$\begin{array}{ccc|ccc}\text{Start}&\text{Step 1}&\text{Step 2}&\text{Start}&\text{Step 1}&\text{Step 2}\\ \hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B \end{array}$$ That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.