A cycle on n vertices is isomorphic to its complement. The value of n is _____.

GATE 2014 · Discrete Mathematics · Graph Isomorphism · medium

Answer: n = 5

1. Edge count condition for self-complementarity: C_n has exactly n edges. For self-complementarity: n = n(n-1)/4.
2. Verify C_5 is self-complementary: C_5 has 5 edges. Its complement K_5 minus C_5 also has 10 - 5 = 5 edges, and every vertex still has degree 2 in the complement. A bijection maps C_5 to its complement, confirming isomorphism.