6
$\begingroup$

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?

$\endgroup$
5
+50
$\begingroup$

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:

[Figure 1]

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.