(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian circuit of this graph (visit each edge exactly once).
One solution is to run the DFS-based algorithm that can find a Eulerian circuit in any Eulerian graph (a graph with all vertices of even degree).
However, I'm hoping it's possible to use the nice structure of $K_{2n+1}$ to avoid constructing the graph and running the algorithm. Is there a way to construct one such circuit in O(n) time with O(1) memory?
Motivation: The motivation behind this is an algorithm which receives a list L and needs to calculate $B(A(x), A(y))$ for each unordered pair ${x,y}$ of distinct elements of L (I'm only considering unordered pairs since $B(u,w)=B(w,u)$). The result of operation A is very large and takes almost half of the available memory. Such a circuit will allow me to minimize the number of calls to operation $A$.
Note: This is a sort of "undirected" version of generating a de-Bruijn sequence. I once heard it's possible to generate a de-Bruijn sequence with constant memory, but I don't know how to do that.
Best Answer
Yes it is possible.
Number the vertices $1,2, \dots 2n+1$.
Consider the sequence $1, 2n, 2, 2n-1, 3, 2n-2, \dots, n,n+1$, ignore $2n+1$ at the moment.
This gives a hamiltonian path in $K_{2n}$.
Now add $1$ to each vertex $\mod 2n$, to get $2,1,3,2n,4, 2n-1 \dots, n+1, n+2$. This can be visualized as writing the numbers $1,2, \dots, 2n$ in a circle and rotating the path. (see figure below).
Repeat this process of adding $1$, $n$ times. This gives you a set of $n$ edge-disjoint hamiltonian paths in $K_{2n}$. (We can show that by proving that (wlog) $1$ is first adjacent to $2n$, then $2,3$, then $4,5$ etc)
To each of these paths, add $2n+1$ at the end and join back to the first vertex of the path.
This gives you an Euler tour of $K_{2n+1}$ which starts and ends at vertex $2n+1$.
This can be computed in constant memory.
Note that this basically follows the (classic/folklore) construction that $K_{2n+1}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles. See this for instance, Modern Graph Theory, page 16.
In case that book is not accessible, here is a snapshot of the relevant part of that page: