Question 61

Properties of Graph and its Complement:

• A cycle graph $C_n$ on $n$ vertices has exactly $n$ edges (for $n \ge 3$).
• The complete graph $K_n$ has $\frac{n(n - 1)}{2}$ edges.
• The complement graph $\overline{C_n}$ has:
  $$|E(\overline{C_n})| = \frac{n(n - 1)}{2} - n.$$

Isomorphism Condition:

• Isomorphic graphs must have identical numbers of edges:
  $$n = \frac{n(n - 1)}{2} - n.$$
  $$2n = \frac{n(n - 1)}{2}.$$
• Since $n \ge 3$, divide both sides by $n$:
  $$2 = \frac{n - 1}{2} \implies n - 1 = 4 \implies n = 5.$$

Verification:
For $n = 5$, $C_5$ has 5 edges and $\overline{C_5}$ has $\frac{5 \times 4}{2} - 5 = 5$ edges. The complement of a pentagon is a pentagram, which is also a 5-cycle. Hence $C_5 \cong \overline{C_5}$.