Question

A simple graph that is isomorphic to its complement is self-complementary. (i) Prove that, if \(G\) is self-complementary, then \(G\) has \(4 k\) or \(4 k+1\) vertices, where \(k\) is an integer. (ii) Find all self-complementary graphs with four and five vertices. (iii) Find a self-complementary graph with eight vertices.

Short answer

Any self-complementary graph \(G\) has \(4k\) or \(4k+1\) vertices, where \(k\) is an integer. There is one self-complementary graph with four vertices (two disconnected edges) and one with five vertices (a four-vertex cycle with one connected to a fifth vertex). An example of a self-complementary graph with eight vertices could be two four-vertex cycles which share a single vertex.

Step-by-step solution

Prove number of vertices in a self-complementary graph

Let \(G\) be a self-complementary graph with \(n\) vertices and \(m\) edges. Since \(G\) is its own complement, the edges of its complement graph would be \(n(n-1)/2 - m\). But \(G\) isomorphic to its complement implies \(m = n(n-1)/2 - m\). Therefore, \(2m=n(n-1)\). This equation must hold for some integer \(n\), which will be either even (say \(4k\)) or odd (say \(4k+1\)), for some integer \(k\). Let's separate these two cases.

Prove for \(n=4k\)

Assuming \(n = 4k\) for some integer \(k\), we substitute \(n\) in \(2m=n(n-1)\) we get that \(2m=4k(4k-1)\), which can further be reduced to \(m=4k(2k-1)\), which is an integer. This indicates that \(n = 4k\) is a valid result.

Prove for \(n=4k+1\)

Similar to Step 2, assuming \(n = 4k+1\) for some integer \(k\), we substitute \(n\) in \(2m=n(n-1)\) we get that \(2m= 4k^2+4k+1-(4k+1)\), which can be simplified to \(m=2k^2+k\), which is integral. Hence, \(n = 4k+1\) is also a valid result.

Find self-complementary graphs with four vertices

Identifying all by drawing them, one can identify that there is a single self-complementary graph with four vertices. It is constituted of two disconnected edges.

Find self-complementary graphs with five vertices

By drawing and identifying all, one can identify that there is a single self-complementary graph with five vertices. It is in the form of a four-vertex cycle with one of the vertices connected to the fifth vertex.

Find a self-complementary graph with eight vertices

One possible self-complementary graph with eight vertices consist of two four-vertex cycles which share a single vertex.