-
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
, the maximum vertex degree is
.
Thus any degree sequence if distinct values must be:
.
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?