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\}, and suppose every person in LL is friends with every person in RR (and no one is friends within their own group) — the complete bipartite graph K3,3K_{3,3}. Counting two seatings around a circular table as the same arrangement if one is a rotation or reflection of the other, how many circular seatings have every neighbor pair friends?