In this book (I found it from other references, and it was a nice book to study.), there is an exercise that proving the following two statements.
Every graph $G$ with $m$ edges and maximum degree $k$ has a proper $(k+1)$-edge-coloring with each color used $\lfloor \frac{m}{k+1} \rfloor$ or $\lceil \frac{m}{k+1} \rceil$ times.
Every bipartite graph with maximum degree at least $k$ has a $k$-edge-coloring (not necessarily proper) in which at each vertex $v$, each color appears $\lfloor \frac{d(v)}{k} \rfloor$ or $\lceil \frac{d(v)}{k}\rceil$ times.
First one is proved by Fedor Petrov in a very elegant method.
But for second one, it seems that a quite different strategy is needed, and I have yet no idea with how to prove it.
The book only says 'Use graph transformation.' but no other hints.
Would you help me?
Best Answer
There is a proof with a very similar principle than in Petrov's proof. Take an arbitrary coloring. If the property is not respected, you have a vertex $v$ where one of the colors $c_1$ appear strictly over $⌈\frac{d(v)}{k}⌉$, and another color $c_2$ appear less or equal than $⌊\frac{d(v)}{k}⌋$ (or one which appear strictly less than $⌊\frac{d(v)}{k}⌋$ and another which appear more or equal than $⌈\frac{d(v)}{k}⌉$, but the argument is th same). Take the graph composed only of the edges colored by $c_1$ and $c_2$, and orient all $c_1$ edges in the same direction (from one part of the bipartite graph to the other) such that the arcs are leaving $v$. Same with $c_2$ but with arcs entering $v$). Follow a path in the graph starting from $v$, you cannont get stuck at $v$ as there are strictly more outcoming edges than incoming edges. Once you get stuck, you have found a node where the number of incoming arcs is strictly more than the number of outcoming arcs. It is easy to show that swapping colors in the path will strictly decrease the distances to average degree.