MathDB

5

Part of 2019 OMMock - Mexico National Olympiad Mock Exam

Problems(1)

n people at a party and friendship

Source: Mexico National Olympiad Mock Exam 2019 P5

10/16/2019
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.
combinatoricsgraph theoryfriendly