[xigency]

For the problem to be NP-Complete, it would have to be both in NP (the one thing that can be agreed on) and NP-hard. For it to be NP-hard, every problem in NP would have to be reducible to it. If we already know that the Hamiltonian circuit verification problem is NP-complete, and that the Secret Santa problem is NP, we de-facto know that S.S. is reducible to the Hamiltonian circuit. So the 'Aha' moment in the third to last paragraph is not new information.

It's true that if every NP problem were reducible to S.S., then it would be NP-hard, and as it can be verified in P time with the S.S. list and the list of people plus relations, and is thus in NP, it would also be NP-complete. It would also suffice to reduce an NP-complete problem to the S.S. problem as pictured here to prove NP-completeness.

But this article doesn't give proof of either and generally points in a different direction, like you said, so the title is really misleading and it would have been better to open the article with a question or discussion.

To summarize, this post by Rod Hilton is pretty useful in understanding the relation between P, NP, NP-hard, and NP-complete: http://www.nomachetejuggling.com/2012/09/14/traveling-salesm...