Let G V E and GVE be two simple graphs Prove that G and G a

Let G = (V, E) and G\'=(V\',E\') be two simple graphs. Prove that G and G\' are isomorphic only if G^c and G\'^c are isomorphic. The complement of a graph

G = (V, E), denoted by G^c, is the graph with set of vertices V and set of edges E^c = {{u, v} | {u, v} / E}.

Solution

Let two graphs Gc and G\'c be isomorphic graphs, this implies there exist a bijection( say) f from Vc to V\'c such that every two adjacent vertices of Gc are mapped to adjacent vertices of G\'c. It is easy to follow that number of vertices in G are equal to complement of G(i.e.G\'c) and similarly for G\'. then the same function f takes vertices from G to adjacent vertices G\' and non-adjacent vertices of Gc to non-adjacent vetices of G\'c.thus graphs G and G\' are isomorphic.