Question

Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?

(a) 4

(b) 0

(c) 2

(d) 5

I have been asked this question in my homework.

The above asked question is from Graphs Properties in section Graphs of Discrete Mathematics

Answer 1

Right answer is (c) 2

The best explanation: We know that sum of degrees of all vertices = 2X no of edges. Say number of edges is E. Degree of last vertex is x, 1+2+3+4+5+6+7++8+9+x = 2XE

=>45+x = 2XE

Now putting options we get answer 0 or 5

But one vertex of degree 9 means it connected to all other vertexes. So, the degree must be 5.