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.