A self-complementary graph is a graph which is isomorphic to its graph complement. The numbers of simple
self-complementary graphs on 
, 2, ... nodes are 1, 0, 0, 1, 2, 0, 0, 10, ... (OEIS A000171). The first few of these correspond to
the trivial graph on one node, the path graph 
,
and the cycle graph 
.
Every self-complementary graph is not only connected, but also traceable (Clapham 1974; Camion 1975;
Farrugia 1999, p. 52). Furthermore, all self-complementary graphs have graph
diameter 2 or 3 (Sachs 1962; Skiena 1990, p. 187). For a self-complementary
graph on 
vertices, there is a graph cycle of length 
for every integer 
(Rao 1977; Farrugia 1999, p. 51). As a
result, the graph circumference of a self-complementary
graph on 
vertices is either 
(i.e., the graph is Hamiltonian),
,
or 
(Furrigia 1999, p. 51).
By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., 
edges for a self-complementary graph on 
vertices. Since 
must be divisible by 4, it follows that 
or 1 (mod 4).
There is a polynomial-time condition to determine if a self-complementary graph is Hamiltonian.
The number of self-complementary graphs on 
nodes can be obtained from the "graph polynomial"
derived form Pólya's enumeration theorem used to enumerate the numbers of
simple graphs as 
.
All self-complementary symmetric graphs were identified by Pesiert (2001). Peisert (2001) observed that that graphs which are both symmetric and self-complementary are necessarily strongly regular, arc-transitive, and distance-transitive, and proved that they given by the Paley graphs, Peisert graphs, and one exceptional graoh on 529 vertices that is not isomorphic to either the 529-Paley or 529-Peisert graph.
