Question

Why must there be an even number of vertices of odddegree in an undirected graph?

Short answer

\(2m = \sum\limits_{v \in V} {\deg (v)} \)

Hence, the sum of the degrees must be even, since m is an integer.

Step-by-step solution

Step 1: Explanation

By question three we have

\(2m = \sum\limits_{v \in V} {\deg (v)} \)

Hence, the sum of the degrees must be even, since m is an integer.

Now, since the following hold:

\(\begin{array}{l}even*even = even\\even*odd = odd\\odd \times odd = odd\\even \times odd = even\end{array}\)

It must be true we have an even number of vertices of odd degree, otherwise we would reach a contradiction with the above equalities.