I'm having a bit of a trouble with the below question
Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$.
Prove that the number of vertices of odd degree in any graph $G$ is even.
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.
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.
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.
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.
To prove that the number of odd vertices in a simple graph is always even, we can use the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is twice the number of edges.
Let's denote the number of odd-degree vertices as 'x'. Since the sum of the degrees of all vertices is even (twice the number of edges), we have:
2 * (sum of even degrees) + x = 2 * (number of edges)
The sum of even degrees is always even because the sum of even numbers is even. Therefore, we can rewrite the equation as:
Even + x = 2 * (number of edges)
Now, let's consider the right side of the equation. The product of 2 and the number of edges is always even because 2 multiplied by any number gives an even result.
Even + x = Even
For the left side of the equation to be even, 'x' must be even as well. This means that the number of odd-degree vertices in a simple graph must be even.
Hence, we have proven that the number of odd vertices in a simple graph is always even.
The degree or valency or order of any vertex is the number of edges or arcs or lines connected to it. The sum of degrees of any graph can be worked out by adding the degree of each vertex in the graph.
The sum of degrees is twice the number of edges. Therefore, the sum of degrees is always even. The sum of an odd number of odd numbers is always equal to an odd number and never an even number(e.g. odd+odd+odd=odd or 3*odd).
Taking into account all the above rules and/or information, a graph with an odd number of vertices with odd degrees will equal to an odd number. Since it is not possible to draw a graph if its sum of degrees is odd, this graph cannot be drawn.
A different proof could use a recurrence over the number e of edges in the graph. Suppose $e=0$, then for any graph the number of odds vertices is even (there are none). Now suppose for $e=k$ any graph has an even number of odds vertices. Let's prove it's also true for $e=k+1$ . Consider a graph $G$ with $e=k+1$, then if you remove one edge, say, between node $A$ and $B$, you get a graph $G'$ with an even number of odds vertices ( by hypothesis). Now if you add back the edge, there are three cases: either $A$ and $B$ are both odd vertices (in $G'$) in which case they both become even, and the number of odd vertices remains even in $G$. Or $A$ and $B$ are both even in which case they both become odd, and the number of odd vertices is still even in $G$. Finally $A$ is odd and $B$ is even (or inverse), then adding back the edge doesn't change the number of odd vertices, which means it is still even in $G$, which finishes the proof.
Simply, sum of even numbers of odd number is an even number (always odd+odd=even and even+odd=odd and even+even=even). As the sum of degree of vertices needs to be even number, number of such vertices must be even. Which @Mike has presented very succinctly.
Here is a proof by induction on the number of vertices. Consider first the base case when there is no vertex. Then the number of vertices of odd degree (or of any degree) is zero, which is even. Suppose now that it has been established that the number of vertices of odd degree of any graph with $k$ vertices is even. Let us add one new vertex to any such graph. Any new edge drawn from the new vertex to an old (existing) vertex will change the parity of both the old and the new vertex. Thus, the number of odd vertices will diminish by two, remain unchanged, or increase by two. In any case, the parity of the number of vertices of odd degree will be unchanged, as will be the case when no new edge is added. Therefore, the result has been extended from the case of $k$ vertices to that of $k+1$ vertices. The general result follows by induction.
