Generalization of Euler Circuits that Visit Each Edge $k$-times

Question

It is known that a graph has an Eulerian circuit if and only if each node has even degree. Two questions: (1) What is the term used to describe a cycle (if the right term) that visits each edge in a graph exactly $k$ times? (2) What are the necessary and sufficient conditions for such a cycle to exist in a graph?

To clarify the property in (1), I am talking about 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 two, distinct $i$ and $j$ such that $e=e_i=e_j$.

I know that the even degree condition is not necessary in the case $k=2$. Take any tree, pick the root node for example, and follow the perimeter of the graph as represented in the plane:

I seem to be able to find a path in on a cube as well in the case $k=2$.

My motivation for asking this question is recreational. I am thinking about knots that can be tied on or around polyhedra.

Answer 1

The Euler theorem is true in any multigraph.

To solve your problem, replace each edge in $G$ with $k$ identical edges, to get a multigraph $M$. Then, your question is: When does $M$ have an Eulerian circuit?

Assuming $G$ is connected, by Euler theorem an Eulerian circuit exists if and only if for each vertex $v$ we have $$\deg_M(v) \mbox{ is even }$$

Since $$deg_M(v)=k \cdot \deg_G(v)$$ the answer is simple:

If $G$ is connected then

• For even $k$ there is always a $k$-Eulerian circuit.
• For odd $k$ there exists a $k$-Eulerian circuit if and only if all vertices have even degree if and only if $G$ has an Eulerian circuit.

Answer 2

I think it's always possible if $k$ is even and your graph $G$ is connected. I'd draw a picture to illustrate but im on my phone at the moment.

I think you can make some kind of inductive argument. Pick any vertex $v$ and consider all the connected components of $G-v$. Find $k$-Eulerian cycles (or whatever you want to call them) for each connected component. I think using those cycles, the edges incident to $v$, and $v$ itself, you can piece together a $k$-Eulerian cycle for the whole graph.