a graph problem

[saihat]

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.

and i answered that by the answer in the attachment, is that correct?

 

[daon]

Assuming the graph is connected: Since the graph (having n >= 2 nodes) is simple, each node has at most degree (n-1). That means at least two must share the same degree. For if not, there are n distinct natural numbers between 1 and (n-1), which is obviously false. This is a direct application of the pigeonhole principle.

If it is not connected, apply the above to the connected component(s) (if any). If there are no connected components, there are two having degree 0.