Isomorphism with complement
Task number: 4545
Find a graph that is isomorphic to its complement. Can you find another one? Is it possible to construct infinitely many of them?
Solution idea
By a case analysis can be found \(P_4\) or \(C_5\).
Infinitely more of these can be obtained by recursive construction. In a graph \(G\) that is isomorphic to its complement, replace each vertex \(v\) by a copy of some graph \(H_v\) that is also isomorphic to its complement. (It is possible to use different graphs to replace different vertices, or do not replace some vertices at all - just replace one.)
The edges of the original graph are then replaced with complete bipartite graphs.
The isomorphism between \(G\) and \(\overline G\) combined with the isomorphisms between \(H_v\) and \(\overline{H_v}\) is the desired isomorphism for the resulting graph and its complement.
