Finding paths covering all edges in complete digraphs

I'm writing a test suite for a state machine where every state is reachable from every other state except itself by exactly one step, so the state graph of the system is a complete digraph. I'd like to test every possible state transition / edge in the graph. However, each state transition is somewhat costly, which is why I'd like to minimise the number of transitions while still covering all edges. That is, I want to find a path starting from an arbitrary vertex in the graph that'll return to that original vertex after traversing every edge exactly once.

Using intuition and straight up guessing, I came up with the following approach:

Given a list of states (a, b, c, d, and e, for the purpose of an example), generate all rotations of that list, e.g.:

a b c d e
b c d e a
c d e a b
d e a b c
e a b c d

Consider the first element of each rotation to be the state we're currently in, and the other elements to be the "todo list" of other states we still need to reach from there.

a: b c d e
b: c d e a
c: d e a b
d: e a b c
e: a b c d

Now, given any starting state (a for the purpose of the example), you seem to always be able to find a path covering all edges by visiting the next unvisited state in the "todo list" of whichever the current state is. Following that path in the example yields:

a -> b
b -> c
c -> d
d -> e
e -> a
a -> c
c -> e
e -> b
b -> d
d -> a
a -> d
d -> b
b -> e
e -> c
c -> a
a -> e
e -> d
d -> c
c -> b
b -> a

My questions about this are:

Does this approach always work (regardless of the number of states)? Some experimentation and intuition seems to suggest that it does, but I'd like to better understand why.
Are there any symmetries in the path other than the obvious one of the second half being the reverse of the first half, but with the directions reversed? Having to only compute half of the path to get the entire one is nice, but I'm curious if there's perhaps more optimisations that could be done.
Which other operations also lead to an ideal path? Rotating all the "todo lists" further by an arbitrary amount still gives a minimal cycle from what I can tell and I imagine reversing/transposing will as well, but I'm curious if those are the only operations preserving the desirable property.
Which other problems is this isomorphic to? My (maybe-)solution feels a little convoluted and somewhat arbitrary, and I feel like there are almost certainly better mental models to reason about this problem.

Solution

There are trivial solutions for 1 and 2 vertices.

Say we have a solution for k vertices, and we want a solution for k+1 vertices.

Let 'A' be the solution for k vertices, which will be a list of vertices with repetition representing the order in which they're visited to traverse every arc once. So for 2 vertices, one valid arrangement would be [1,2,1].

Let 'x' be the new vertex, and let 'z' = A[-1] be the last vertex of A.

Then the solution including x is A, followed by alternating x's and elements of {1-k} \ {z}, and ending with a final x, z once we're done.

Example

[1, 2, 1] # trivial solution for 2.
[1, 2, 1, 3, 2, 3, 1] # 2 => 3
[1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1] # 3 => 4
[1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1] # 4 => 5

etc...

This is linear in the output, which is the number of arcs, or for n nodes, O(n * (n-1)) = O(n^2)

Ruby Code:

def f(n)
  return [1] if n == 1
  arr = [1,2,1]
  3.upto(n) do |i|
    2.upto(i-1) do |j|
      arr.append(i)
      arr.append(j)
    end
    arr.append(i)
    arr.append(1)
  end
  puts arr.to_s
end

f(5) = [1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1]
f(7) = [1, 2, 1, 3, 2, 3, 1, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3, 5, 4, 5, 1, 6, 2, 6, 3, 6, 4, 6, 5, 6, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7, 6, 7, 1]

Q1) I think your method is sound. The only way it can fail is if you traverse all the arcs in and out of your starting node before traversing all other arcs. You don't need to worry about other nodes since indegree == outdegree, so any node you can enter you can also leave. Assuming we take your approach but with numbers, we start at 1, so our grid is:

1) 2, 3, ..., n
2) 3, 4, ..., n, 1
3) 4, 5, ..., n, 1, 2
...
n) 1, 2, ..., n-1

There are n-1 arcs into 1. One of them is from 2, which we only hit after entering 2 n-1 times. But to do that, we need to get the node visited from 3, which requires visiting 3 n-1 times, and so on...

This is an idea sketch not a proof, but I think this could be extended to a proof showing that before you visit 1 n-1 times, you need to visit every other vertex n-1 times, and there are no duplicate arcs possible in your approach, so every arc has been traversed exactly once.