The number of (isomorphism classes of) self complementary graphs on n vertices is the difference between the number of graphs on n vertices with an odd number of edges and the number with an even number of edges.
This is relatively easy to prove with counting arguments, but I'd love to have a combinatorial proof of this...
