Proving that the number of vertices of odd degree in any graph G is even

Solution 1:

I'm posting Mike's comment as an answer, since he won't.

The sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even, the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.

Solution 2:

Let G be a graph with $'e'$ edges and $'n'$ vertices $v_1,v_2,v_3,...,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$. Hence, $$\sum_{i=1}^n\text{degree}(v_i)= 2e.$$ Let the degrees of first $r$ vertices be even and the remaining $(n-r)$ vertices have odd degrees,then clearly,$\sum_{i=1}^{r}\text{degree}(v_i)= even $.Since,$$\sum_{i=1}^n\text{degree}(v_i)= \sum_{i=1}^r\text{degree}(v_i)+\sum_{i=r+1}^n\text{degree}(v_i)$$ $\implies$ $\sum_{i=1}^n\text{degree}(v_i)- \sum_{i=1}^r\text{degree}(v_i)=\sum_{i=r+1}^n\text{degree}(v_i)$

$\implies$ $\sum_{i=r+1}^n\text{degree}(v_i)$ is even.($WHY?$)

But, the for $i=r+1,r+2,...,n$ each $d(v_i)$ is odd. So, the number of terms in $\sum_{i=r+1}^n\text{degree}(v_i)$ must be even.

In lucid words,$(n-r)$ is even.

Hence the result.

Solution 3:

We represent $G$ by a symmetric relation on the set of points $P$, which we also call $G$, so $$G = \{(a,b), (b,a) : \text{there is an edge between } a \text{ and } b\}$$ Clearly, $\#G |2$ where $\#G$ is the number of elements in $G$. Now $$\deg (a) = \# \{(a,x): (a,x) \in G\}$$ Since we have $$\sum_{a\in P} \deg(a) = \sum_{a\in P} \# \{(a,x): (a,x) \in G\} = \#\{(x,y) : (x,y) \in G\} = \# G$$ We know $$\sum_{a\in P} \deg (a) | 2$$ From number theory we have $$\sum_{j=1}^n a_j |2 \Leftrightarrow \#\{a_j : a_j \not|\, 2\}|2$$ (the number of odd numbers in a sum is even, iff the sum is even) and setting $a_j = \deg(b_j)$ with $b_j \in P$ an enumeration of $P$, the statement follows.

Solution 4:

Suppose we have an arbitrary graph with $l$ vertices. Suppose we have $n$ vertices with odd degree. Let's consider what happens when we connect(or remove) an edge between any two vertices, there're two possibilities:

1) The two vertices are both of even(or odd) degree: Suppose both vertices are even degree. Connecting(or removing) an edge between them will increase the degree of both vertices by $1$ (or decrease in case of removing an edge), therefore both vertices will become odd degree, and $n$ will increase by $2$.

Similarly, if the two vertices were initially odd degree, then connecting(or removing) an edge will turn both of the vertices into even degree, and $n$ will decrease by $2$.

2) One vertex is odd while the other is even. In this case, connecting(or removing) an edge will turn the odd vertex into an even one, and the odd vertex becomes even. Therefore $n$ will remain unchanged.

From this we learn that the number of odd degree vertices $n$ can only increase/decrease in steps of $2$(or remain unchanged) as we create(remove) edges.

Now when we construct any graph we wish, we start with our vertices isolated from each other with not a single connection(edge). Therefore, initially $n=0$(all vertices are of even degree since not a single edge connects them) , and as we make connections, it can only increase/decrease in steps of $2$, therefore $n$ will remain even.

Solution 5:

Hint: What is the sum of the degrees of all vertices?