1
$\begingroup$

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.

  • 0
    What is the difference between sum with absolute values and sum without absolute values?2012-12-24

2 Answers 2

2

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.

0

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*}