The Gateway to Computer Science Excellence
+28 votes
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
in Graph Theory by Veteran (105k points)
retagged by | 4.2k views
Since  given that graph is cyclic what we can deduce is that no. Of vertices= no. Of edges=n

Now, it is isomorphic to its complement so no. Of edges in its complement graph will also be n.

No. Of edges in graph G + No. Of edges in graph G'= no. Of edges in complete graph ( $\frac{n(n-1)}2$ ).

n+n= $\frac{n(n-1)}2$

2n= $\frac{n(n-1)}2 $

4n = n(n-1)




Can you explain how??

this is awesome!

Why not 4.

Take l_l and its complement.

I can not type  its complement here, but try to form it.

Both are isomorphic.

6 Answers

+92 votes
Best answer
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}$
by Boss (17.9k points)
edited by
beautiful  explanation.
if G isomorphic to its G' , mean G is self complementary , no of edges in self complementary graph = n(n-1)/4 =n (here edge of cycle graph)
nice explanation..........
I think this is out of syllabus ?

One another way to solve it:

We know that each vertex v of a  cycle has a degree of 2. Now given that the complement of the cycle should be isomorphic, hence the degree of each vertex in the resulting (complemented) graph must also have a degree of 2. That means originally each vertex v was connected to 2 vertices and not connected to the other 2 vertices.

Hence we have a total of 5 vertices in the original graph (vertex v + two connected vertices + two disconnected vertices).

nice [email protected] mittal 1
Two graphs on n vertices are isomorphic if $K_{n}$ can be divided edge-disjoint copies each of one is isomorphic to one-another.

In short, the isomorphic graphs have exactly $\frac{1}{2}\binom{n}{2}= \frac{n(n-1)}{4}$ edges.

Cycle on n vertices has n edges and this is isomorphic to it's complemet.

So $n$=$ \frac{n(n-1)}{4}$

@Sachin Mittal 1

what I tried in my first go is

1. From maximum possible degree $\binom{n}{2}$ - 2. This will give me the degree of each vertex in complemented graph.

2. As it is isomorphic , I equated it to 2 (as there will be cycle)

I am not getting the answer 😢

Sorry I took $\binom{n}{2}$ as degree.

It can be solved like degree of vertex of complement: (degree of complete graph with n vertices) -2(cycle) = n-1-2= n-3

Now as it is isomorphic and contains cycle n-3=2 hence n=5. 🙂

So, points to be noted.

1. Cycles are defined only for graphs having $n\geq 3$, where $n$ is the no. of vertices.  Why :(

2. Also, the question doesn't explicitly mention if the graph is s1mple and undirected.  So, it's a valid assumption unless otherwise mentioned ?!!

good explanation
+27 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 $.

by Loyal (8.1k points)
edited by
+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 .

by (331 points)
From where you got the above formula

This is General approach. If there is a Graph G which have some edges and if we want to find out the complement of the graph then we will take those edges in complimented graph which are not in Graph G.

Number of Edges in Graph G + number of edges in Graph G'= Maximum Edges possible with given vertices.

Cycle graph is a graph which has n vertices and n edges.

In this Question, they are saying," A cycle on n vertices is isomorphic to its complement"

so the number of edges in Graph G and its complimented Graph is same. Let us suppose, n edges are there.

So according to our formula:

n + n =n(n-1)/2

on solving we get

+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.
by Junior (705 points)
edited by
0 votes
n the vertices in cycle graph(let name as G) than number of edges in this graph(G) is also n(because in cycle graph number of vertices is equal to number of edges).

let Gc is complement of graph then according to question G and Gc are isomorphic.

if G and Gc are isomorphic than they must have equal number of edges and vertices.


so,edges in G=edges in Gc=n

G+Gc=n+n=2n(let name this as eqn "1")

G+Gc=makes a complete graph having "n "vertices

G+Gc=n(n-1)/2  (complete graph with 'n' vertices has n(n-1)/2 edges)

2n=n(n-1)/2  (from eqn 1)

n^2 -5n=0

put n=5 (our eqn get statisfy)
by (295 points)
0 votes
Complement of a graph means, we need to remove the existing edges from the graph and place the new edges which were not earlier among the actual graph.
In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.
When we complement it, each vertex will be connected to remaining n-3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n-3 =2
by Active (1.2k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,365 answers
105,263 users