# Graph Theory proof

I need to make a proof but I can't come to the solution:

For every vertex of oriented graph with vertices $U_{1},U_{2},\ldots,U_{n}$ we've got $s_{+}(U)$ the number of edges, which come to the vertex $U$, and $s_{-}(U)$ the number of edges which leave from the vertex.

Prove that: $\sum_{i=1}^{n} |(s_{+}(U_{i})-s_{-}(U_{i})|$ is even number.

Until now I came to the statement that when we remove absolute values we get number 0.

-
Can you come up with a set $S$ of integers such that $\sum _{s\in S} s = 0$ but $\sum_{s \in S} |s|$ is odd? –  Karolis Juodelė Dec 24 '12 at 14:49
What is the difference between sum with absolute values and sum without absolute values? –  Adam Dec 24 '12 at 14:56

Say $S$ is any set of integers and $\sum _{s\in S} s = 0$. You can then divide $S$ into $S_+ = \{s\in S : s\geq 0\}$ and $S_- = \{s \in S : s < 0\}$. We have $\sum _{s\in S} s = \sum _{s\in S_+} s + \sum _{s\in S_-} s = \sum _{s\in S_+} |s| - \sum _{s\in S_-} |s| = 0$ and thus $\sum _{s\in S_+} |s| = \sum _{s\in S_-} |s|$. Finally, $\sum _{s\in S} |s| = \sum _{s\in S_+} |s| + \sum _{s\in S_-} |s| = 2\sum _{s\in S_+} |s|$. Therefore your result is sufficient to complete the proof.
For any integer $a$, we can check that $|a| \equiv \pm a \equiv a \pmod 2$. Thus: \begin{align*} \sum_{i=1}^{n} |s_{+}(U_{i})-s_{-}(U_{i})| & \equiv \sum_{i=1}^{n} \big( s_{+}(U_{i})-s_{-}(U_{i}) \big) & \text{since } |a| \equiv a \pmod 2 \\ & \equiv \sum_{i=1}^{n} s_{+}(U_{i})- \sum_{i=1}^{n} s_{-}(U_{i}) \\ & = \text{nr edges} - \text{nr edges} \\ & = 0 \pmod 2. \end{align*}