Are there any graphs that are isomorphic to its complement? I'm not sure if I can consider just a vertex A with no edges to be the graph and its complement A' to also have no edges which would make them isomorphic to each other.
2026-05-11 08:42:44.1778488964
On
Graph Theory Isomorphism
156 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
There are in fact many graphs which are isomorphic to their complement. For example, there are more than 9 billion such graphs of order 20. See http://oeis.org/A000171 for more enumerative results.
In fact, there are infinitely many self-complementary graphs, as is explained well in an answer to this previous M.SE question.
Try the path graph $P_4$ (edges of complement shown below in red)