# Why can a $2k$-regular graph be $k$-factored?

From Wikipedia:

If a connected graph is $2k$-regular it may be $k$-factored, by choosing each of the two factors to be an alternating subset of the edges of an Euler tour.

I don't understand why those alternating subsets form $k$-factors.

-
There is a minor error in the statement (mentioned in the comments below), but you should really be more explicit about what it is you don't "see". Do you not know what an Euler tour is? What the "alternating subset" refers to? – Erick Wong May 28 '13 at 17:11

In a connected $2k$-regular graph $G=(V,E)$, you can find a path $\pi=v_0 e_1 v_1 e_2\dots e_n v_0$, taking each edge $e_i$ of the graph exactly once (Eulerian path). Then if you look at the partitions $E_1=\{e_1,e_3,\dots\}$ and $E_2=\{e_2,e_4,\dots\}$, they form a $k$-factorization of $G$. Indeed, each vertex $v$ is adjacent to exactly $k$ edges from $E_1$, and $k$ edges from $E_2$, because every time an edge from $E_1$ enters $v$ in $\pi$, then the next one is from $E_2$ and exits $v$, and vice-versa. However this only works if $e_n\in E_2$, otherwise the above statement is not true for $v_0$. This means that we have to additionally require that $|E|$ is even. $K_3$ is counter-example for the odd case.
Doesn't the graph need to have an even number of edges? $K_3$ is connected $2$-regular but I don't see a $1$-factor. – Erick Wong May 28 '13 at 15:08
You are right there is an issue if $e_1=e_n$. So we need to assume that the number of edges (or equivalently of vertices) is even. I edit the answer. – Denis May 28 '13 at 15:43
Looks good. I think it's okay for $|V|$ to be odd so long as $|E|$ is even (this would mean $k$ is even). – Erick Wong May 28 '13 at 16:00