How can I show that the number of vertices of a simple, undirected graph with odd degree is even using a proof by induction.
Any hint would be appreciated I am really stumped here.
Asked
Active
Viewed 89 times
0
-
Does this answer your question? Proving that the number of vertices of odd degree in any graph G is even – JMoravitz Nov 22 '22 at 18:27
1 Answers
0
The sum of the degrees of vertices in a graph is exactly twice the number of edges, and thus even. The sum of the degrees of 'even' vertices is clearly even. Which means that the sum of the degrees of 'odd' vertices must be even as well (else the sum of both would be odd). Since only an even number of odd integers sum up to an even number, it means that there must be an even number of vertices with odd degree.
Boshu
- 1,476