Question : Show that in a simple graph with 'n' vertices, has at least two vertices with the same number of degree.
Solution :
(a)If there is no isolated vertices in the graph, then the degrees take values from 1 to (n-1) (as the graph is simple). Then by pigeon-hole principle atleast two vertices has the same degree.
(b) If there is a isolated vertex, then the degrees of the vertices take values from 0 to (n-2) (? why (n-2)) (as the graph is simple). Then by the pigeon-hole principle two vertices has the same degree.
My questions :
(1) In (a) & (b) how do we conclude using the pigeon-hole principle?
(2) In (b) how do we get "If there is a isolated vertex, then the degrees of the vertices take values from 0 to (n-2)"?