Answer to Question #272404 in Discrete Mathematics for Amu Raj

Question

1. Proof that an undirected graph has an even number of vertices of odd degree.

Answer 1

Lets define graph G = (V, E), where V - set of verticles, E - set of edges. Since each edge connects two verticles(technically, the loop connects verticle with itself, but it increases the degree of verticle by 2, so that doesn't ruin the logic as we will se), then

$\sum_{v \in V} deg(v) = 2|E|$ - sum of degrees of all verticles equals to doubled number of edges, so this sum is even.

Let $V_1\subset V$ , $V_2\subset V$ be a subset of all verticles with even and odd degree number respectively, then $\sum_{v \in V_1} deg(v)$ is obviously even. Since $\sum_{v \in V_1} deg(v)+\sum_{v \in V_2} deg(v)=\sum_{v \in V} deg(v)\implies \sum_{v \in V_2} deg(v)=\sum_{v \in V} deg(v)-\sum_{v \in V_1} deg(v)$

Then $\sum_{v \in V_2}$ is even. Every value in that sum(if it is not empty) is odd, then amount of values must be even. Amount of values in that sum is amount of verticles with odd degree number. If that sum is empty, then the amount of verticles with odd degree is 0 - still even number

The statement has been proven