# Discrete Maths Question

• Jan 14th 2009, 08:51 PM
Storm20
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.
• Jan 15th 2009, 04:41 AM
mr fantastic
Quote:

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 ....?
• Jan 15th 2009, 04:55 AM
Storm20
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.
• Jan 15th 2009, 07:49 AM
Plato
Quote:

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, \$\displaystyle |V|\ge 2\$, there are at least two vertices with the same degree.