# Simple graph with at least two vertices

hello

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
Staff Emeritus

HallsofIvy
Homework Helper
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?

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

i

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.

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.