Self Complementary Graphs

Self Complementary Graphs

 Definition: A graph $G = (V(G), E(G))$ is said to be Self Complementary if $G$ is isomorphic to its complement, that is $G \cong \bar{G}$.

For example, the following graph $G$ and its complement are isomorphic as both can be "unravelled" into a path graph:

Note that for a graph to isomorphic to another in general, then the number of vertices in both graphs must be the same. Of course, this is no problem for complement graphs since they have the same vertex set. Additionally, for a graph to be isomorphic to another, the number of edges in both graphs must be the same. Hence if $\mid E(G) \mid \neq \mid E(\bar{G}) \mid$, then $G$ is not isomorphic. We also note that if:

(1)
\begin{align} \quad \mid E(G) \mid \neq \mid E(\bar{G}) \mid \neq \frac{n(n-1)}{4} \end{align}

Then the graph is NOT complementary. Notice that all we did was take the number of edges in the complete graph and divide it by $2$.