Simple graph with at least two vertices

[hyderman]

hello

please help by exaplaining this question in steps thank much

Show that in a simple graph with at least two vertices there must be
two vertices that have the same degree. use the Pigeonhole principle.

 

[cristo]

You must show your work before we can help you. Have you thought about the question? Have you tried following the hint?

 

[HallsofIvy]

Have you at least drawn a picture? What happens if you try to draw a graph with exactly two vertices, each vertex having different degree?

 

[hyderman]

thanx for replyng i did draw a graph but i still can't understand the whole question
i know that Each vertices is connected to either 0, 1, 2, ..., n−1 other vertices but i cannot get the whole idea

please help
i

 

[tim_lou]

so let's say you have n vertices. As you said, assume they all have different degree, then they must be,
0,1,2...n-1.

however, how can a vertex have zero degree while another vertex have n-1 degree (connecting to ALL other vertices)? contradiction.

 

[tim_lou]

a more interesting question would be:

let there be n people in a party. Alex is in the party, and he knows that all the other people make different number of handshakes, how many handshakes does Alex make?

this classic handshake problem is closely related to this situation.

 

[hyderman]

please explain more in details

 

[hyderman]

okey can you tell me ur opinion on this thanx

Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, ..., n−1 other vertices. If any of the vertices is connected to n−1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus, it is impossible to have a graph with n vertices where one vertex has degree 0 and another has degree n−1. Thus the vertices can have at most n−1 different degrees, but since there are n vertices, at least two must have the same degree.