Prove that it is impossible to have a graph in which there a

Prove that it is impossible to have a graph in which there are an odd number of odd- degree vertices.

Solution

We represent GG by a symmetric relation on the set of points PP, which we also call GG, so

G={(a,b),(b,a):there is an edge between a and b}G={(a,b),(b,a):there is an edge between a and b}

Clearly, #G|2#G|2 where #G#G is the number of elements in GG. Now

deg(a)=#{(a,x):(a,x)G}deg(a)=#{(a,x):(a,x)G}

Since we have

aPdeg(a)=aP#{(a,x):(a,x)G}=#{(x,y):(x,y)G}=#GaPdeg(a)=aP#{(a,x):(a,x)G}=#{(x,y):(x,y)G}=#G

We know

aPdeg(a)|2aPdeg(a)|2

From number theory we have

j=1naj|2#{aj:aj/|2}|2j=1naj|2#{aj:aj|2}|2

(the number of odd numbers in a sum is even, iff the sum is even) and setting aj=deg(bj)aj=deg(bj) with bjPbjP an enumeration of PP, the statement follows.