Prove that a simple graph with n _ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex of n-1 degree

Question

Prove that a simple graph with n >_  2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex of n-1 degree

Thanks

Reiny · Answer

I don't understand what you mean by a vertex having a 'degree'.

Matt · Answer

It means that it is attached to that many other vertexes, say if a vertex is attached to two other vertex by lines then it has degree 2

Reiny · Answer

Matt, I am afraid you have me stumped on that one, I have never encountered that kind of geometry before. Perhaps if you repost your question some of the other math tutors could help you.