Here is a physical implementation of the more efficient version: en.wikipedia.org/wiki/Lehmer_sieve

There are a lot of arguments in Diophantine equations using primes congruent to $1 \mod{6}$, primes congruent to $5 \mod{6}$, and two sporadic elements. Or you can have collections of families $\mod{n}$, with sporadic prime divisors of $n$. Maybe the most common: "Let $p$ be in the odd prime family..."

@Nate: Both players have the option to use either colour, so the number of sequences (with $m={n \choose 2 }=|E|$) is $2^m \cdot m!$. That's $3.7$ billion for $n=5$, though you can immediately drop a factor of $2m$ and make a few further simplifications from symmetries. It's small enough to brute force with $k=3$ (the hard part was combining moves into a readable strategy), but $k=4$, $n \leq 17$ is a long way off.

Do you allow mirror images of the tile?

@Felix: Yes, you're right, the edges could already be there. This only works when you don't care if the regular graph is simple.

@Felix: There are an even number of vertices, so you can pair them up and add an edge for each pair. Their degrees all increase by one, and the other set is unchanged, so you get a regular graph.

Whichever one you choose, your referee will prefer the other one and let you know it. Then after you change it, or don't, you'll find out the journal you submitted it to has an unwritten house rule about exactly these situations and you'll have to choose that way.

$2071$ for abcd?

I think this can be extended to multiples of $6$ in the 3 dimensional case, and to the 4 dimensional case, with $n=8$, by doing half of the black cells in each pair 1-5, 2-6, etc., then instead of returning to $(1,1,1,1)$, switch the sign of the $1$ or $3$ movement to return to a square with sum $2$ (mod $4$), and do it all over again. It will take some more care to make the path closed.

I just noticed this might not be closed, so you'll want to make careful choices when jumping between boards. A path from $(1,1,1)$ that ends at $(2,3,4)$ can go to $(5,2,6)$, and then use a path that ends at $(3,1,3)$. From there, go to $(2,4,5)$ and use a path that ends at $(4,3,2)$. So all you need is the existence of $6x6$ tours that include moves $(1,1)\rightarrow(2,3)$, $(5,2)\rightarrow(3,1)$, and $(2,4)\rightarrow(4,3)$.

@Joseph, re: black-cell path: the black cells of the 6^3 cube admit a tour, using standard knight's tours of 6x6 boards for the first two coordinates, and hopping between boards in the third coordinate. That is, starting at $(1,1,1)$, use a 2D knight's tour, moving to $(x,y,4)$ for black squares, and back to $(a,b,1)$ for the white squares. Then go on to do 2&5, and 3&6 the same way, getting to those planes by making any move that lands there, and starting at that point in the 6x6 knight's tour.