**Theorem**: Every graph contains an even number of odd vertices.

**Proof**: Let G be a graph of size *m*. Since the sum of the degrees of the vertices of G is even, namely

*2m*, and the sum of the degrees of the even vertices of G is even, it follows that the sum of the

degrees of the odd vertices of G is even. Therefore, G has an even number of odd vertices.

**Question**: Why does knowing the sum of the degrees of even vertices and odd vertices of G follow that G has an even number of odd vertices?

## Best Answer

The sum of the degrees of even vertices, $E$, is even because it is a sum of even numbers. If the sum of the degrees of odd vertices, $O$, were odd, then $E+O$ would be odd. But $E+O=2m$, which is even. So $O$ must be even also. But $O$ is a sum of odd numbers, and the sum of an odd number of odd numbers is always odd.