MathCastle
Graph TheoryChallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Challenge problem

Split 66 people into two groups of three, L={1,2,3}L=\{1,2,3\} and R={4,5,6}R=\{4,5,6\}, with everyone in LL friends with everyone in RR and no other friendships — K3,3K_{3,3}, which does have Hamiltonian cycles (for example 1,4,2,5,3,61,4,2,5,3,6 and back to 11). What is the minimum number of people who must leave the group so that NO circular seating of the remaining people has every neighbor pair friends?