Question

In a finite graph the number of vertices of odd degree is always ______

(a) even

(b) odd

(c) even or odd

(d) infinite

This question was addressed to me during an interview for a job.

Origin of the question is Graphs in section Graphs of Discrete Mathematics

Answer 1

Correct choice is (a) even

Easy explanation: In any finite graph, sum of degree of all the vertices = 2 * number of edges.

Sum of degree of all the vertices with even degree + sum of degree of all the vertices with odd degree = 2 * number of edges. Now, even number  + sum of degree of all the vertices with odd degree = even number. It is possible if and only if number of odd degree vertices are even.