What graphs have k-Eulerian circuits without backtracking? Yesterday I asked about k-Eulerian circuits and which graphs have them.
What I mean by k-Eulerian circuits is a sequence of edges $\{e_i\}_{i=1}^n$ such that $e_i$ and $e_{i+1}$ are connected to a common node, $e_1$ and $e_n$ are connected to a common node, and that for each $e \in E$, where $E$ is the collection of edges in the graph, there exists exactly $k$, distinct $i_j$, such that $e=e_{i_j}$ for $j=1,\dots, k$.
It was explained to me that the theory of Eulerian circuits applies to multigraphs and hence gives an easy answer to what graphs have $k$-Eulerian circuits.
My new question is, what graphs have 2-Eulerian circuits (general answer for $k$-Eulerian is fine too) without backtracking? That is, in our sequences of edges, which sequences have no duplicate terms in a row. Or specifically, $e_i \neq e_{i+1}$ and $e_1 \neq e_N$ for all $i = 1, \dots , N$.
I am thinking about knots around a sphere or regular polyhedra and backtracking doesn't make for good knots.
 A: First consider the case when $k$ is odd.  As stated by @N.S. in response to your previous question, in order for $G$ to have any $k$-Eulerian circuit (even allowing backtracking), $G$ itself must have an Eulerian circuit.  To get a $k$-Eulerian circuit without backtracking, simply split the Eulerian circuit at some vertex, and then splice together $k$ copies of this split circuit.
For example, if the original circuit is $e_1, e_2, e_3, e_4$, which we have split between $e_1$ and $e_4$, then the corresponding $3$-Eulerian circuit would be $e_1, e_2, e_3, e_4, e_1, e_2, e_3, e_4, e_1, e_2, e_3, e_4$.  Note that this cannot have any backtracking, since any two consecutive edges belong together in the original circuit.

Hence we need only consider the case when $k$ is even, say $k = 2 \ell$.  In this case, I claim that $G$ admits a $k$-Eulerian circuit without backtracking if and only if $G$ is connected with minimum degree $\delta(G) \ge 2$.
To see the necessity, if $G$ has a $k$-Eulerian circuit, then it is of course connected.  Now suppose there is some vertex $v$ of degree $1$, and say its only edge is $e$.  At some point in the $k$-Eulerian circuit we must use the edge $e$ to reach the vertex $v$.  However, the only possibility to continue the circuit is then to use the edge $e$ again, and so this circuit must involve backtracking.

Now suppose $G$ is a connected graph with minimum degree at least $2$; we need to show it has a $k$-Eulerian circuit without backtracking.  We will prove a slightly more general lemma, for which we first introduce a couple of definitions.
Let $M$ be a multigraph (both loops and parallel edges allowed).  An even equipartitioning at vertices is, for every vertex of $M$, a partition of its incident edges into at least two parts, all of equal and even size.
Given a connected multigraph $M$ with an even equipartitioning at vertices, and an Eulerian circuit $C$ of $M$ (which must exist, since $M$ is connected and has even degrees), we say $C$ has a clash at $v$ if there are two consecutive edges $e$ and $f$ of $C$ such that $v$ is the common vertex between $e$ and $f$, and $e$ and $f$ belong to the same part in the partition for the vertex $v$.
We can now state the lemma.

Lemma: Let $M$ be a connected multigraph with an even equipartitioning at vertices.  Then $M$ has an Eulerian circuit without any clashes.

This lemma, which we shall soon prove, may not be the simplest to parse, but it does imply the result almost immediately.
Given our graph $G$, let $M$ be the multigraph obtained by replacing every edge of $G$ with $k$ parallel copies.  Create an even equipartitioning at vertices by grouping together all the parallel edges into parts.  Since there are $k$ copies of each edge, all parts have size $k$, which is even.  Since every vertex $v$ has $\deg_G(v) \ge \delta(G) \ge 2$, there will be at least two parts at each vertex.  Hence this is indeed an even equipartitioning at vertices.
Hence we may apply the lemma to $M$, and thus find an Eulerian circuit of $M$ without clashes.  An Eulerian circuit of $M$ is simply a $k$-Eulerian circuit of $G$.  A clash is simply backtracking, since it requires using the same edge twice consecutively.  Hence the lemma gives us a $k$-Eulerian circuit without backtracking.

Proof of Lemma
We first prove the lemma when the partition at every vertex has exactly two parts, which will (rather nicely, if I do say so myself) imply the general case.  In this special case, we will in fact only require that at every vertex, the two parts have equal size.
Note that every vertex has even degree (since its incident edges are divided into two equal parts), and so $M$ has an Eulerian circuit $C$.  Take a circuit with the fewest clashes.  If it has no clashes, we are done.
Otherwise suppose there are some clashes, and let $v$ be a vertex where some of the clashes occur.  Call the two parts of the partition at $v$ $R$ and $B$, and let $k = |R| = |B|$.  If we cut the circuit $C$ every time it visits the vertex $v$, we get $k$ subcircuits $C_1, C_2, ..., C_k$, each starting and ending at $v$.  Note that all that matters is which parts their first and last edges (with respect to leaving/entering $v$) come from.  Hence every subcircuit $C_i$ can be reduced to an ordered pair $(R,R), (B,B)$ or $(R,B)$, depending on which parts its first and last edge come from [if it is $(B,R)$, reverse it to get $(R,B)$].
Since there are $k$ edges in both $R$ and $B$, there must be a total of $k$ $R$'s and $k$ $B$'s.  This means that there are the same number of $(R,R)$ subcircuits as there are $(B,B)$ subcircuits.  Arrange the subcircuits as follows:
$$ \underbrace{(R,R), (B,B), (R,R), (B,B), ..., (R,R), (B,B)}_{\textrm{if any}}, \underbrace{(R,B), (R,B), ..., (R,B)}_{\textrm{if any}}. $$
Putting the subcircuits together in this order gives a new Eulerian circuit $C'$ of $M$.  This has no clashes at $v$, as the edge of one subcircuit that returns to $v$ is always from the opposite part of the edge of the next subcircuit that leaves $v$.  Since this rearrangement does not create any new clashes at other vertices (those pairs of consecutive edges lie within some subcircuit, and hence remain the same), $C'$ has fewer clashes than $C$, contradicting our choice of $C$.
This proves the lemma in the special case where every vertex had exactly two parts in its partition.  We now solve the general case.
Note that $M$ is again Eulerian, since now at every vertex the parts have even size.  We again take an Eulerian circuit $C$ with the fewest clashes.  If it has no clashes, then we are done.  Otherwise let $v$ be a vertex where some clashes occur.  Suppose there are $d$ parts, all of size $k$, in the partition at $v$, say $S_1, S_2, ..., S_d$.  We can again split $C$ each time it visits $v$ to get $\frac12 dk = d\ell$ subcircuits $C_1, C_2, ..., C_{d\ell}$ that start and end at $V$.
Now each of the subcircuits can be represented by a pair $(i,j)$, $1 \le i \le j \le d$, if its first edge (starting from $v$) is from $S_i$ and the last edge (returning to $v$) is from $S_j$ [if necessary, reverse the subcircuit].
We can now form an auxiliary multigraph $H$ with vertices $[d] = \{1, 2, ..., d\}$.  For every circuit of the type $(i,j)$, put an (undirected) edge from $i$ to $j$ (if $i = j$, this is a loop at $i$).  Colour all of these edges red.
Now add the following blue edges: $\ell$ copies of the edge $\{i,i+1\}$, $1 \le i \le d-1$, together with $\ell$ copies of $\{d,1\}$.
Observe that $H$ is connected, by virtue of the blue edges, and every vertex $i$ is incident to exactly $k$ red edges (since there are $k$ edges in $S_i$, each of which corresponds to one end of a subcircuit) and exactly $k$ blue edges.  Let $R$ be the set of red edges and $B$ the set of blue edges, $H$ satisfies the conditions of the special case of our lemma, and so we can find an Eulerian circuit $C_H$ of $H$ without any clashes.
That $C_H$ has no clashes means that the circuit alternates between red and blue edges.  The red edges correspond to the subcircuits in $M$ of our original Eulerian circuit $C$.  We put them together in the order given by the auxiliary circuit $C_H$, thus getting a new Eulerian circuit $C'$.
We claim that $C'$ has no clashes at $v$.  Indeed, note that any consecutive edges through $v$ in $C'$ correspond to two neighbouring subcircuits in $C'$, say $C_a$ and $C_b$, which correspond to two red edges in $C_H$ with one blue edge between them.  However, all blue edges go between different vertices, corresponding to different parts among $S_1, S_2, ..., S_d$, and so the last edge of $C_a$ must belong to a different part than the first edge of $C_b$.  Hence these consecutive edges in $C'$ do not give a clash.
As before, we also do not create any new clashes at other vertices, since we are only changing pairs of consecutive edges that go through the vertex $v$.  This means that $C'$ has fewer clashes than $C$, contradicting our choice of $C$.
This concludes the proof of the lemma.

Closing remarks
Apologies for the long wall of text, which I hope is somewhat understandable (some pictures would probably have helped, but I do not have any at hand).  I suspect there might be a simple inductive proof that I am missing, but I did have fun working this out, so thanks for asking the question!
