Let G be a simple graph with n 1 vertices Prove that G has

Let G be a simple graph with n > 1 vertices. Prove that G has two vertices with the same degree.

Solution

let we have a simple graph of 2 vertex implies garaph has maxium 2(2-1)/2 edges = 1

and degree sequence are <0,0> <1,1> are possible in both cases ,two vertex of graph has same degree,

let G be a graph of order of order n , there are n term in degree sequence of G, if no number (integer value ) in the degree sequence repeats , then only possible degree sequence is in the form of <0,1,2,............n-1>

where we know maximum degree sequence of a graph with n vertice is n-1 , but the last vertex of degree n-1 should be adjacent to every other vertex of G, since G is simple Graph,

thus the mimimum degree of every vertex is one ,

A contradiction to the fact that the degree of one vertex is zero .

there fore al least two vertex has same degree in the simple graph of n >1 vertex .

hence proved .