# 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.

-

Simply, sum of even numbers of odd number is an even number (always odd+odd=even and even+odd=odd and even+even=even). As the sum of degree of vertices needs to be even number, number of such vertices must be even. Which @Mike has presented very succinctly.

-
Welcome to this site! The question you just answered is rather old and already has perfectly good answers, to which your post doesn't seem to add much. More value to the site would be added by answering unanswered questions, or giving answers significantly different to the ones already existing. – Pierre-Guy Plamondon Jun 30 at 11:44