GATE CSE 2014 Set 2 | Question: 51

Question

A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.

Comments

Why not 4.

Take l_l and its complement.

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

Both are isomorphic.

---

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.

---

Bro it's already mentioned in question graph is cycle but the example with u are trying to counter is not a cycle.

Answer 1

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)

Answer 2

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
n=5