15 people are at a party. If in every group of 3 people, at least 2 do not know each other, what is the greatest possible number of pairs of people that know each other?
I've been working on this for days and I've looked around but I can't seem to solve it.
Hint: Represent each person with a vertex, and make two vertices adjacent to one another if and only if the two corresponding people know one another. Then the property that in every group of 3 people at least two do not know each other is equivalent to the resulting graph being triangle-free. Now see Mantel's Theorem.