MathDB
Inequaity with n people if k >= d [ILL 1977]

Source:

January 11, 2011
combinatorics proposedcombinatorics

Problem Statement

In a company of nn persons, each person has no more than dd acquaintances, and in that company there exists a group of kk persons, k≥dk\ge d, who are not acquainted with each other. Prove that the number of acquainted pairs is not greater than [n24]\left[ \frac{n^2}{4}\right].
Back to ProblemsView on AoPS