Question

In a simple graph G with n vertices is isomorphic to its complement G', then which of the following can be value of n?
a) 10
b) 9
c) 11
d) 15

Answer 1

If a simple graph $G$ with $n$ vertices is isomorphic to its complement $G'$, then it has $4k$ and $4k + 1$ vertices, where $k$ is some natural number. And we have four variants of number of vertices: 10, 9, 11 and 15. In this list only $9 = 4 \cdot 2 + 1$. So, a simple graph $G$ probably has 9 vertices.

So, the answer is b).

**Answer:** b) 9.