Hey, I have a question that looks relatively easy, but I'm not too sure how to go about answering this one.
Any help would be greatly appreciated
A group of 15 people is gathered together for a meeting. Show that at least two people must have the same number of acquaintances at the meeting.
This is a common question in sections on graph theory. By two people being acquaintances we mean a two-way relationship. So in a graph representing the acquaintances in a group a edge joins two vertices(people) that are acquainted.
Theorem: In any simple graph, , there are at least two vertices with the same degree.