On Wikipedia, I have seen a nice proof of Zagier for the existence of representations of primes as sum of two squares:
The proof uses the (trivial) fact that the number of fixed points of an involution of a finite set has the same parity as the cardinality of the set itself.
Do you know any other examples for existence proofs using the parity of fixed points of involutions?