Chordless graph with degrees at least 2
Source: BMO SL 2023 C3
May 3, 2024
combinatorics
Problem Statement
In a given community of people, each person has at least two friends within the community. Whenever some people from this community sit on a round table such that each adjacent pair of people are friends, it happens that no non-adjacent pair of people are friends. Prove that there exist two people in this community such that each has exactly two friends and they have at least one common friend.