Comment by ryansloan

We were just talking about this at the office this week and came to a similar conclusion. However, someone pointed out later that you could have a valid Secret Santa configuration that was not a Hamiltonian Path - you could have two (non-overlapping) paths and still have a valid secret santa: For people A B C D E F, you could have the graph covered by two separate circuits:

A->B->C->A

D->E->F->D

Unfortunately real-life intervened and we didn't have time to decide if this was an NP complete problem or not...