Graph Theory question? Assuming that friendship is always mutual, prove that in any group of n  2 persons, there are at least 2 persons with the same number of friends in the group.
How do I answer this question with a graph ?
 A: You can view this as a question about simple graphs, but it will boil down to the pigeon hole principle. Suppose everyone has a different number of friends, so listing those numbers in order yields $\{ 1,...,n-1\}$ or $\{ 0,1,...,n-2\}$ (depending on what kind of assumptions you want to make). Regardless, you have $n-1$ possibilities with $n$ people.
A: This is a very fun question that comes up in any introductory graph theory course. To approach it, first we need to model the situation with a graph.
For any party, we can create a graph where the vertices represent the people at the party and there is an edge between two vertices if the two corresponding people know each other(assume no stalkers, aka if a knows b then b also knows a) Then the degree of each vertex tells you the number of people that person knows at the party. This for any party with $n$ people, we get a graph on $n$ vertices.
If there was a party where no two people know the same number of people, then there would be a graph where no two vertices have the same degree. For a graph of order $n$, there are $n$ realizable degrees, $0$ through $n-1$. Thus each of these degrees must show up in our graph of this party. If we have a degree of $n-1$, then that vertex is adjacent to every other vertex, including he vertex of degree $0$, a contradiction! Thus, no such graph exists!
Therefore at any party, there are at least two people who know the same number of people.
An interesting extension of this problem, since there isn't a non-trivial fully "irregular" graph, what about a nearly irregular one? It ends up for each $n\geq 2$, there exists exactly two graphs that have only two vertices of the same degree, and they are complementary. 
A: This is already on the internet here:
http://puzzlesland.com/mathprob/graph-samedeg.html
