# Math Help - a graph problem

1. ## a graph problem

1- Show that in a simple graph G having at least two vertices, there must be two distinct vertices having the same degree.

2- Use the result of 1 to show that in any group of at least two people there must be two people who know the same number of people in the group.

2. I hope that this does not disappoint, but I am not giving you more that hints.
In a simple graph of order $n$, the maximum vertex degree is $n-1$.
Thus any degree sequence if distinct values must be: $0,1,2, \cdots ,n - 1$.
But, if the graph has a vertex of degree zero, we can drop it.
Recall that the sum of the degrees is twice the number of edges.

Try to find a contradiction in all that.

2) Follows trivially from #1.

3. thanks for the help, i tried and thats what i got, is that correct?