Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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
    
Yes indeed, I must be more careful! –  Denis May 28 '13 at 16:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.