Problem

Source: 2021 Junior Macedonian Mathematical Olympiad P1

Tags: graph theory, combinatorics



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 $A$ be a fixed student. Show that there exist students $B$ and $C$ such that there are exactly two friendships in the group $\{ A,B,C \}$. Proposed by Mirko Petrushevski