No matter what you do, there will always be friends in different rooms
Source: 2021 Junior Macedonian Mathematical Olympiad P1
June 8, 2021
graph theorycombinatorics
Problem Statement
At this year's Olympiad, some of the students are friends (friendship is symmetric), however there are also students which are not friends. No matter how the students are partitioned in two contest halls, there are always two friends in different halls. Let be a fixed student. Show that there exist students and such that there are exactly two friendships in the group .Proposed by Mirko Petrushevski