MathDB
n people at a party and friendship

Source: Mexico National Olympiad Mock Exam 2019 P5

October 16, 2019
combinatoricsgraph theoryfriendly

Problem Statement

There are n≥2n\geq 2 people at a party. Each person has at least one friend inside the party. Show that it is possible to choose a group of no more than n2\frac{n}{2} people at the party, such that any other person outside the group has a friend inside it.
Back to ProblemsView on AoPS