Question

Hence show that the number of odd degree vertices in a graph always even.

Answer 1

Let $V=\{v_1,v_2,\dots,v_n\}$ be the set of vertices and $E$ is the set of edges of the graph $G$.

First let's prove that $\deg v_1+\dots+\deg v_n=2|E|$ by induction on $|E|$.

If $|E|=0$, then the graph contains no edges, $\deg v_i=0$ for all $i=1,2,\dots,n$, and the equality holds. Now assume that the equality is proved for all graphs with $|E|<m$ and consider any graph $G$ with $|E|=m$. Assume that for some i,j the edge $v_iv_j\in E$ and let $G'$ be the graph that remains after deleting the edge $v_iv_j$ from $G$. By the induction hypothesis,

$\deg_{G'} v_1+\dots+\deg_{G'} v_n=2|E'|=2|E|-2$

By the construction, for all $k\ne i,j$ we have $\deg_{G'} v_k=\deg_{G} v_k$, $\deg_{G'} v_i=\deg_{G} v_i-1$ and $\deg_{G'} v_j=\deg_{G} v_j-1$. Hence,

$\deg_{G'} v_1+\dots+\deg_{G'} v_n=\deg_{G} v_1+\dots+\deg_{G} v_n-2=2|E|-2$

Therefore, $\deg v_1+\dots+\deg v_n=2|E|$, as required, and the equality is proved for all finite graphs.

Denote by $r_i$ 1, if $\deg v_i$ is odd, or 0, if else. Then $r_i=\deg v_i-2[\deg v_i/2]$, and the number of odd degree vertices is equal to

$r_1+\dots+r_n=\sum\limits_{i=1}^n(\deg v_i-2[\deg v_i/2])=2|E|-2\sum\limits_{i=1}^n[\deg v_i/2]$

Therefore, it is even.