Question

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

Answer 1

Let G be a graph with e edges and n vertices v₁,v₂,v₃,...,v_n.

Since each edge is incident on two vertices, it contributes 2 to the sum of degree of vertices in graph G. Thus the sum of degrees of all vertices in G is twice the number of edges in G:$∑^n_{i=1}degree(v_i)=2e$

Let the degrees of first r vertices be even and the remaining (n−r) vertices have odd degrees, then:

$∑^n_{i=1}degree(v_i)=∑^r_{i=1}degree(v_i)+∑^n_{i=r+1}degree(v_i)$

$\implies ∑^n_{i=1}degree(v_i)+∑^r_{i=1}degree(v_i)$

$\implies ∑^n_{i=r+1}degree(v_i)$ is even.

But, the for $i=r+1,r+2,...,n$ each $d(v_i)$ is odd. So, the number of terms in

$∑^n_{i=r+1}degree(v_i)$ must be even. So, $(n-r)$ is even.