Youshow that the number of vertices with odd degree in a graph is always eve

To prove that the number of vertices with odd degree in a graph is always even, we can follow these steps:

Step 1: Assume we have a graph with n vertices. Step 2: Let's consider the sum of the degrees of all the vertices in the graph. Step 3: By the Handshaking Lemma, we know that the sum of the degrees of all the vertices is equal to twice the number of edges in the graph. Step 4: Therefore, the sum of the degrees of all the vertices is an even number. Step 5: Now, let's suppose that there are k vertices with odd degree in the graph. Step 6: The sum of the degrees of these k vertices is an odd number since it is the sum of odd numbers. Step 7: Since the sum of the degrees of all the vertices is even, the sum of the degrees of the remaining (n-k) vertices must also be even. Step 8: The sum of the degrees of the remaining (n-k) vertices is the sum of even numbers. Step 9: In order for the sum of even numbers to be even, the number of even numbers must be even. Step 10: Since the sum of the degrees of the remaining (n-k) vertices is even, the number of vertices with even degree must be even. Step 11: Therefore, the number of vertices with odd degree in the graph (k) must be even as well. Step 12: Hence, we have proven that the number of vertices with odd degree in a graph is always even.