
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.

I hope that this does not disappoint, but I am not giving you more that hints.
In a simple graph of order $\displaystyle n$, the maximum vertex degree is $\displaystyle n1$.
Thus any degree sequence if distinct values must be: $\displaystyle 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.

1 Attachment(s)
thanks for the help, i tried and thats what i got, is that correct?