Does a regular multigraph of even degree possess a set of cycles containing each vertex precisely once?
[In a regular multigraph every vertex has the same degree. No loops are allowed but more than one edge can join two vertices.]
This result is true for regular multigraphs with small numbers of vertices. See for example one of the solutions to Symmetric matrix as a sum of symmetric matrices. Is it true in general?
Best Answer
Yes; this result is one of the ones known as Petersen's theorem.
Assume $G$ is connected; if not, you can work with just one component of $G$ at a time. Then $G$ has an Eulerian tour $C$. By choosing one of the two directions around $C$, and then orienting each edge of $G$ according to which way $C$ goes along it, we get a directed graph. If $G$ was $2k$-regular, then every vertex of the directed version has in-degree and out-degree $k$.
We can encode a directed graph with $n$ vertices $v_1, v_2, \dots, v_n$ as a bipartite graph with $2n$ vertices $u_1, u_2, \dots, u_n$ and $w_1, w_2, \dots, w_n$: replace a directed edge $(v_i,v_j)$ by an edge $u_iw_j$ in the bipartite graph. If we do that to the directed graph we got, we get a $k$-regular bipartite graph.
In a $k$-regular bipartite graph, there is a perfect matching, by Hall's theorem: if $S$ is a set of vertices on one side of the graph and $N(S)$ their neighbors on the other side, then $$k|S| = \sum_{v \in S}\deg(v) = |E(S,N(S))| \le \sum_{w \in N(S)} \deg(w) = k|N(S)|$$ so $|S| \le |N(S)|$. (Key idea: summing the degrees out of $S$ counts all the edges between $S$ and $N(S)$, and summing the degrees out of $N(S)$ counts all those edges and possibly some others, if $N(S)$ has any edges to vertices not in $S$.)
The edges of the perfect matching form a subgraph of $G$ which visits each vertex exactly twice, so they give us the set of cycles we wanted. (In the multigraph case, a $2$-edge cycle is possible.)