This was a homework problem I had. I\'m trying to work out whether my answer was

Question

This was a homework problem I had. I'm trying to work out whether my answer was correct as we don't get the assignment back before the exam. The problem was: Prove that it is impossible to have a graph in which there are an odd number of odd- degree vertices.

My answer was: The sum of all the degrees in the graph is always equal to twice the number of edges, because an edge between two vertices adds one to the degree of each of those vertexes. Regardless of whether it is even or odd, any number multiplied by two will be an even number, and thus the sum of the degrees has to be even. The sum of the degrees of vertices with even degree is always going to be even, because of basic arithmetic rules. (odd+odd=even; odd+even=odd; even+even=even) Therefore, the sum of the degrees of vertices with odd degree must also be even, because the total number of degrees is even as is the sum of the degrees of vertices with even degree, and the sum of the degree of vertices with odd degree is found by subtracting the latter from the former. Since any two even number added together will yield an even number, by extension any even number subtracted from another even number will yield an even number. Thus, the sum of the degrees of vertices with odd degree is even. Since this is the case, then there has to also be an even number of those vertices, because you have to add together an even number of odd numbers for the sum to be an even number.

Explanation / Answer

Yes, your answer is also correct. There are several ways of doing this by like handshaking, contradiction, induction method and incidence matrix.

i am going to solve this by incidence matrix.

Consider that such a graph exists and consider its incidence matrix. The sum of the numbers in column must be 22 for each edge is incident on exactly 22 vertices. It follows that the sum of all the numbers in the matrix would be an even number.

Now the row sum for odd degree vertices would be odd because each row sums to the degree of the corresponding vertex. Since there are an odd number of odd degree vertices so there will be an odd number of odd row sums following which the sum of all the row sums would be odd. In other words the sum of all the numbers in the matrix would be an odd number. This is a contradiction.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.