Originally Posted by

**Aryth** Ok, here's a proof of this theorem using the graphs:

Let $\displaystyle G = (V,E)$ be an unweighted, undirected graph.

Lets look at the sum of the degrees of its vertices (I'll call it M, though it is often referred to as K):

$\displaystyle M = \sum_{v\in V} deg_G (v)$

Applying the double-counting, each edge $\displaystyle e \in E$ will be counted twice, once for each each vertex to which it is incident.

As a result, the sum MUST be twice the number of edges of G.

$\displaystyle M = 2E$, which is even.

Now, all we do is take out the sum of all the degrees of vertices that are even to get the sum of all the odd degree vertices:

$\displaystyle \sum_{v \in V} deg_G (v) - \sum_{v \in V: deg_G (v) = 2m} deg_G (v) = \sum_{v \in V: deg_G (v) = 2m + 1} deg_G (v)$

This result on the right hand side must still be even, since it is the difference of two even numbers.

Because the sum is of exclusively odd terms, then there must be an even number of them for the sum on the right side to be even, thus the desired result is achieved.