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.
Problem
Source: BMO SL 2023 C3
Tags: combinatorics
03.05.2024 17:46
This probelm is very tricky:one idea kills it Solution:Take the obvious graph interpretation: we have $\deg v\ge 2$ and every cycle doesn't have any chords. Now take the maximal path $v_1v_2\dots v_k$.By maximality all the neighbours of $v_1$ and $v_k$ are in this path. Lemma: $\deg v_1=\deg v_k=2$ Proof: by contreadiction assume $\deg v_1\ge 3$ and assume $v_i$ and $v_j$ are two neighbours $2<i<j\le k$.Then take the cycle $v_1v_2\dots v_j$ and observe it has the chord $v_1v_i$, false !Similar the other case. $\blacksquare$ Now the killer observation is that $v_i$ is the other neighbour of $v_k$ then take the path $v_1\dots v_iv_k\dots v_{i+1}$.It is another maximal path so by the lemma, $\deg v_{i+1}=2$ and so $v_k$ and $v_{i+1}$ have a common neighbour and degree $2$.The end $\blacksquare$.
03.05.2024 18:18
I think that the official solution was something like this. Another possible approach was presented here.