How many Euler circuits are there in the complete directed graph on N vertices? More interesting to me, how many equivalence classes under reversal and relabeling?
| N | circuits: n(n-2) (n-2)!n | classes |
| 3 | 3 | 1 |
| 4 | 256 | 6 |
| 5 | 972000 | 4089 |
| 6 | 247669456896 | 171454588 (I expected >171992678, but am not motivated to inquire further) |
I made models of the six cases on four vertices (and tried to put them on Thingiverse and Thangs, but no images show up). The vertices are those of a tetrahedron, of course. I knew from the start that the corners of the path ought to be rounded, to make it easier to follow; my favorite design so far is a Fourier series (six components) that matches the derivative at the midpoint of each edge. They look like martian game-pieces. I was surprised to find that all of them have u-turns.
Loosening the rules, to allow the path to include an edge twice in the same direction, gives 15 more classes (of which three have no u-turns). I may have those printed later in a contrasting color.
