The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.6k views
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
asked in Graph Theory by Veteran (101k points)
retagged by | 2.6k views
+15
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)

4n=n^2-n

$n^{2}$-5n=0

n(n-5)=0

n=5.
0
five
0
Can you explain how??
0
0

this is awesome!

4 Answers

+64 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}$
answered by Boss (16.1k points)
edited by
0
beautiful  explanation.
+2
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)
0
nice explanation..........
0
I think this is out of syllabus ?
+1

One another way to solve it:

As we know each vertex v of a  cycle has degree as 2....Now given that the complement of the cycle should be isomorphic, hence the degree of each vertices in resulting (complement) must also have degree as 2...i.e. each vertices v in original cycle is connected to 2 vertices and not connected to other 2 vertices...

hence we have a total of 5 vertices in the original graph...(counting vertex v also)

0
nice [email protected] mittal 1
0
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}$
+27 votes

its $n=5$ only.

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

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

answered by (319 points)
–3
From where you got the above formula
+1
@Abhishek

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

n=5
+5 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.
answered by Junior (709 points)
edited by


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

39,530 questions
46,674 answers
139,829 comments
57,598 users