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.

Difficulty level: Hard task
Reasoning task
Cs translation
Send comment on task by email