When is graph G with n vertices is isomorphic to complement G ¯ ?Question :...
When is graph G with n vertices is isomorphic to complement ?
Question : When is graph G with n vertices is isomorphic to complement ?
So, total no of edges that a n vertex graph can have is . And if G is isomorphic to then no of edges in G is equal to no of edges in . So no of edges in . But for this to be an integer, n = 4k or n = 4k+1 for some integer k.
My question is : Is this the only requirement? That is, is n=4k or 4k+1 the sufficient condition to construct such a graph G? Does it have anything to do with the fact that G and can both be bipartite if both of them don't have any triangle in it? The question asks to think about what is the condition of G and simultaneously bipartite.