A self-complementary graph is a graph which is isomorphic to its complement.

The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.

The Rado graph is an infinite self-complementary graph.

A self-complementary graph is a graph in which replacing every edge by a non-edge and vice versa produces an isomorphic graph.

The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem.

All strongly regular self-complementary graphs with fewer than 37 vertices are Paley graphs; however, there are strongly regular graphs on 37, 41, and 49 vertices that are not Paley graphs.