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-03-26 12:40:03.1774528803
On
Graph Theory Isomorphism
155 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)