# Proving that the number of vertices of odd degree in any graph G is even

I'm having a bit of a trouble with the below question

Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$.
Prove that the number of vertices of odd degree in any graph $G$ is even.

-
The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices. –  Mike Aug 12 '12 at 21:24
@Mike: that's an answer, not a comment! –  Ben Millwood Aug 12 '12 at 21:34
@BenMillwood Heh. Not sure how formal of a proof that is. That's why I left it as a comment and not an answer. –  Mike Aug 12 '12 at 21:48
@Mike What's informal about it? Not enough instances of $G$, $v$, and $2n+1$? Don't fall into the trap of thinking that good mathematics has to be riddled with symbols. –  Austin Mohr Aug 13 '12 at 3:26

I'm posting Mike's comment as an answer, since he won't.

The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.

-

Hint: What is the sum of the degrees of all vertices?

-

We represent $G$ by a symmetric relation on the set of points $P$, which we also call $G$, so $$G = \{(a,b), (b,a) : \text{there is an edge between } a \text{ and } b\}$$ Clearly, $\#G |2$ where $\#G$ is the number of elements in $G$. Now $$\deg (a) = \# \{(a,x): (a,x) \in G\}$$ Since we have $$\sum_{a\in P} \deg(a) = \sum_{a\in P} \# \{(a,x): (a,x) \in G\} = \#\{(x,y) : (x,y) \in G\} = \# G$$ We know $$\sum_{a\in P} \deg (a) | 2$$ From number theory we have $$\sum_{j=1}^n a_j |2 \Leftrightarrow \#\{a_j : a_j \not|\, 2\}|2$$ (the number of odd numbers in a sum is even, iff the sum is even) and setting $a_j = \deg(b_j)$ with $b_j \in P$ an enumeration of $P$, the statement follows.

-