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

Answer 1

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

Answer 2

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

Answer 3

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.