GATE 2014 CS (CS2) – Question 61
A cycle on n vertices is isomorphic to its complement. Find n.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5 to 5
Explanation
Every vertex of C_nhasdegree2, while its complement hasdegree n−3. Isomorphism requires2=n−3, hence **n=5**. The complement of C5is indeed another5cycle, so the necessary degree condition is attained.