Self-complementary graph

This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties

Definition

An undirected graph is termed self-complementary if it is isomorphic to its complement, namely, the graph obtained on the same vertex set by putting edges precisely where the given graph does not have edges.

Facts

• If $G$ is a self-complementary graph with $n$ vertices for $n$ finite, the number of edges in $G$ is ${\frac {1}{2}}{\binom {n}{2}}={\frac {n(n-1)}{4}}$.
• For a natural number $n$ to be such that there exists a self-complementary graph on $n$ vertices, a necessary condition is that ${\binom {n}{2}}$ be even, which is equivalent to $n$ being either 0 or 1 mod 4.
• For a natural number $n$ to be such that there exists a self-complementary regular graph on $n$ vertices, a necessary condition is that $n$ be 1 mod 4. The reason is that the degree of every vertex must be $(n-1)/2$, forcing $n$ to be odd, and the previous observation thus forces $n$ to be 1 mod 4.