retagged by
17,307 views
42 votes
42 votes
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
retagged by

6 Answers

Best answer
123 votes
123 votes
A cycle with $n$ vertices has $n$ edges.
Number of edges in cycle $=n$
Number of edges in its complement $=\frac{n(n-1)}{2} - n.$

Fo isomorphism, both graphs should have equal number of edges.
$\begin{align}\text{This gives: }  \\ &\frac{n(n-1)}{2} - n = n. \\ &\Rightarrow n = 5.\end{align}$
edited by
34 votes
34 votes

It is $n=5$ only.

Only $C_{5}$ is isomorphic to its complement.

Here $C_4$ and its complement are not isomorphic because both are having different structures.

Here, $C_5$ is isomorphic to its complement. Just imagine the reorganisation of vertices in the complement of $C_5$, it will become the same as $C_5 $.

edited by
20 votes
20 votes

No of edges in graph + no of edges in complement of graph = n(n-1)/2  // No Of edges in complete graph of N vertices

5 + 5 = n(n-1)/2 // Here in C5 edges are there and in isomorphic graph the no of edges should be equal to no of edges in graph.

so solving it we get n = 5 .

9 votes
9 votes
Another Approach:

(degree of compliment) = (degree of complete graph with given 'n' vertices) - (degree of given graph with 'n' vertices)                                                  

 =>         2 =  (n-1) - 2           ( Given graph = a cycle so degree will be 2 and this will also be the degree of its compliment)
 =>         n = 2 +2 + 1 = 5

Hence, n=5.
edited by
Answer:

Related questions

38 votes
38 votes
9 answers
1
go_editor asked Sep 28, 2014
26,898 views
The maximum number of edges in a bipartite graph on $12$ vertices is____
2 votes
2 votes
2 answers
2
makhdoom ghaya asked Jun 27, 2016
3,411 views
Consider the graph given below as :Which one of the following graph is isomorphic to the above graph ?
29 votes
29 votes
4 answers
3
Arjun asked Sep 25, 2014
10,970 views
Which of the following graphs is isomorphic to