# $6$-regular graph of order $25$ and diameter $2$

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.