Answer to Question #171305 in Combinatorics | Number Theory for Shannon

Question

Why can't a graph with 10 vertices be isomorphic to its complement

Answer 1

A self-complementary graph is a graph which is isomorphic to its complement.

An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges. Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4. So, a 10-vertex graph cannot be self-complementary.