Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the number of edges incident with that vertex in any two color classes differ by at most one.
Assume $p \ge 2$.
This is what I've been able to deduce: let $d_1, d_2,...,d_n$ be the degrees of the $n = |V|$ nodes of $G$. Because $p \mid d_1, p \mid d_2,...,p \mid d_n$, we can conclude that $p \mid 2*|E|$. Knowing that $p \nmid |E|$, we further conclude that $2 \mid p$, so $p$ and $d_1, d_2,...,d_n$ must be even. Having deduced this information, I tend to believe that the coloring must be somehow related to the Euler tour of the graph (because $G$ is an Eulerian graph). But I don't know how to continue my reasoning.
Any help will be strongly appreciated! Thanks!