## Even number of Odd-degree vertices

An undirected graph has an even number of odd-degree vertices.

Suppose \( V_o \) and \( V_e \) denote the set of vertices of odd and even degrees respectively. Let \( V \) denote the set of all vertices of the graph and \( V = V_o \cup V_e \).

Then, by the handshaking Theorem, if \( e \) is the number of edges, we know that

$$ 2e = \sum_{v \in V} \text{deg}(v) = \sum_{v \in V_e} \text{deg}(v) + \sum_{v \in V_o} \text{deg}(v) $$

The left hand side of the above equation is clearly even.
So, the right hand side must be even too.

The first term on the right hand side is even, because the degree is even for each of the vertices in \( V_e \).
Therefore, the second term on the right hand side must be even too. Now, the degrees of each of the vertices in \( V_o \) is odd. So, the number of such vertices must be even for the equation to hold.

Thus, there are even number of vertices of odd-degree in an undirected graph.