This example is for me sheer wizardry: Given a class of relational structures of the same type, all with finite underlying universes and including one with a one-element universe, such a class has unique cancellation as well as unique kth roots (AxC iso BxC implies A iso B, A^k iso B^k implies A iso B). Lovasz came up with the results in the 1960's, and for me the only explanation to the magic is that he came up with the proof first and then the statements later. I hope that kind of magic is allowed for an answer.

Gerhard "Ask Me About System Design" Paseman, 2011.08.29