# Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along with each other, and we can't seat them next to each other.

I thought about a reduction from the $n$-color graph problem (graph coloring) which is NP-complete, but I'm not sure what the reduction is exactly. Can somebody help with that?

• I think you'd have an immediate reduction from the Hamiltonian Cycle problem. $n$-coloring with $n$ diplomats seems not really suitable. – ttnick Jul 31 '18 at 12:14
• @PHPNick I meant k-color where every two diplomats that don't get along with each other are in the same color and we will find a way that every two nodes in every edge have different colors (I'm not sure if it's suitable, but that what I meant). Do you have an idea for a reduction from Hamiltonian cycle? – Barry Jul 31 '18 at 12:54
• Your problem is the Hamiltonian cycle problem in (rather thin) disguise. I encourage you to work this out. – Yuval Filmus Jul 31 '18 at 13:41
• Perhaps you can answer your own question? – Yuval Filmus Aug 5 '18 at 20:18