Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.