Partition edges of multigraph Given a connected multigraph $ G = (V,E) $ show that if $d_G(x)$ is not even $\forall x 
 \in V $ or $|E|$ is even there exists a partition of $E = A $ $\cup$ $B$ such that: 


$|d_A(x) - d_B(x)| \leq 1 $   $\forall x \in V $   where $ d_A(x) $ is the number of edges in $A$ incident to a vertex $x$ in $G$. 
 A: Let $V_o$ be a set of vertices of $G$ with odd degree. Then $|V_o|$ is even. Let $E’=\{(v_1,v’_1),\dots, (v_k,v’_k)\}$ be an arbitrary partition of $V_o$ into pairs and $G’$ be a multigraph obtained from $G$ by adding $E’$ to its set of edges. Then $G’$ has a Eulerian cycle $C$. We shall walk along $C$ starting from an arbitrary vertex $v’$ of an added edge $e’$, if there is any, or starting from an arbitrary vertex, otherwise, enumerating edges which we walked until we walk the whole $C$. Now let $A’$ (resp. $B’$) be the set of edges of $E\cup E’$ with even (resp. odd) numbers, $A=A’\cap E$, and $B=B’\cap E$. Since $C$ is a cycle, $d_{A’}(v)=d_{B’}(v)$ for any vertex $v\ne v'$ of $G$. Since at most one of edges incident to $v$ belongs to $E’$, then $|d_{A}(v')-d_{B}(v')|\le 1$. If $C$ has even length then the same argument imply that $d_{A’}(v’)=d_{B’}(v’)$ and $|d_{A}(v)-d_{B}(v)|\le 1$. Otherwise $d_{A’}(v’)=d_{B’}(v’)+2$. Since $| E\cup E’|=|C|$ is odd, the conditions imposed on $G$ imply that $E’$ is non-empty. Then exactly one edge of $G'$ incident to $v’$ (namely, the edge $e’$) belongs to $E’$ and $e’\in A’$. Then $$d_A(v’)=d_{A’}(v’)-1=d_{B’}(v’)+1=d_{B}(v’)+1.$$
