Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
Eight people split into two groups of four. Within each group, every pair are friends (two separate cliques of size ), and the only friendship between the groups is a single pair, one person from each group. Can the eight be seated around one circular table so that every pair of neighbors are friends? Report the number of such arrangements, counting two seatings as the same circular arrangement if one is a rotation or reflection of the other.