Thread: Discrete Maths Question

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.

Originally Posted by Storm20

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.

As currently worded, I don't think the question can be answered. What is an acquaintance ....?

yeah that's the problem I was having, it's not worded very clearly. I presume it means show that two people either meet or know two other people at the meeting.

But really....doesn't give us much scope on how to solve it mathematically.

Originally Posted by Storm20

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.