[Math] Prove that graph with odd number of odd degree vertices does not exist

Question

I need to prove that it is impossible to have a graph in which there are
an odd number of odd degree vertices. What is the easiest way to formally prove this? I feel that I can prove it just by explaining that the sum of the degree of a graph must be equal to twice the number of edges, which implies that there must be a total even degree, but this isn't very formal.

I'm thinking proof by contradiction, but I'm not too sure where to begin.

Answer 1

You need to prove a little lemma:

(1) Sum of evens is even.

(2) Sum of odd number of odds is odd.

Prove (1) by factoring out a $2$, and prove (2) by induction on the number of terms. Then we can prove what you want.

$E(G)=\{v\in V(G):d(v)\text{ is even}\}$

$O(G)=\{v\in V(G):d(v)\text{ is odd}\}$

$\sum_{v\in V(G)} d(v) =\sum _{v\in E(G)}d(v)+ \sum _{v\in O(G)}d(v)$ is even.

$\sum _{v\in E(G)}d(v)$ is also even, so $\sum _{v\in O(G)}d(v)=\sum_{v\in V(G)} d(v)-\sum _{v\in E(G)}d(v)$ is even.

Therefore $\mid O(G)\mid$ is even.