Ask Mathematics

Friends and strangers at a meeting [closed]

There are N persons present at a meeting. Every two persons are either friends of each other or strangers to each other. No two friends have a friend in common. Every two strangers have two and only two friends in common.
Prove that each person has the same number of friends at the meeting. If this number is 5, find N.

I don’t know how to approach this problem

Strategy proposed by Ross Millikan

I would think of a graph on 𝑁 vertices. Draw an edge between each pair of friends. The graph is triangle free. One graph that meets the conditions is a square, where each person has two friends. A cube does not meet the conditions with each person having three friends as diagonally opposite vertices do not have any friends in common. I would try to draw a graph where each person has three friends.

Leave a Reply

Your email address will not be published. Required fields are marked *