Take l_l and its complement.

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

Both are isomorphic.

Dark Mode

13,561 views

40 votes

0

A cycle with n vertices has n edges.

For isomorphism, both graphs should have an equal number of edges.

If G is a simple graph with n vertices than #edges in G + #edges in G' = #edges in complete Graph.

i.e n + n = n(n-1)/2.

If we put 4 edges in this equation it will not satisfy the condition hence it is false, whereas 5 edges satisfy the condition.

For isomorphism, both graphs should have an equal number of edges.

If G is a simple graph with n vertices than #edges in G + #edges in G' = #edges in complete Graph.

i.e n + n = n(n-1)/2.

If we put 4 edges in this equation it will not satisfy the condition hence it is false, whereas 5 edges satisfy the condition.

0

115 votes

Best answer

1

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 ?!!

0

32 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 $.

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 C_{5 }5 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 .**

@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

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

2