Question

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

• A. A multiple of 4
• B. Even
• C. Odd
• D. Congruent to 0 mod 4, or 1 mod 4

Answer 1

The correct option is D Congruent to 0 mod 4, or 1 mod 4

An n-vertex self-complementary graph has exactly half number of edges of the complete graph i.e. $\frac{n(n-1)}{4}\text{~}edges.$

Since n(n - 1) must be divisible by 4, n must be congruent to 0 mod 4 or 1 mod 4.