Skip to main content
2 of 3
fixed construction
user49822
  • 2.2k
  • 1
  • 13
  • 19

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

user49822
  • 2.2k
  • 1
  • 13
  • 19