Self-complementary graph

---

title: "Self-complementary graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families"] description: "Graph which is isomorphic to its complement" topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Self-complementary_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Graph which is isomorphic to its complement ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/e8/Self-complementary_NZ_graph.svg" caption=""] ::

Graph A is isomorphic to its complement.]]

In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.

Examples

Every Paley graph is self-complementary. For example, the 3 × 3 rook's graph (the Paley graph of order nine) is self-complementary, by a symmetry that keeps the center vertex in place but exchanges the roles of the four side midpoints and four corners of the grid.{{citation | last = Shpectorov | first = S. | doi = 10.1016/S0012-365X(98)0007X-1 | issue = 1–3 | journal = Discrete Mathematics | mr = 1656740 | pages = 323–331 | title = Complementary l1-graphs | volume = 192 | year = 1998| url = https://research.birmingham.ac.uk/en/publications/13d88507-fdb4-4d71-9456-a44faaee8258 | doi-access = | last = Rosenberg | first = I. G. | contribution = Regular and strongly regular selfcomplementary graphs | mr = 806985 | location = Amsterdam | pages = 223–238 | publisher = North-Holland | series = North-Holland Math. Stud. | title = Theory and practice of combinatorics | volume = 60 | year = 1982}}.

The Rado graph is an infinite self-complementary graph.{{citation | last = Cameron | first = Peter J. | authorlink = Peter Cameron (mathematician) | contribution = The random graph | mr = 1425227 | location = Berlin | pages = 333–351 | publisher = Springer | series = Algorithms Combin. | title = The mathematics of Paul Erdős, II | volume = 14 | arxiv = 1301.7544 | year = 1997| bibcode = 2013arXiv1301.7544C

Properties

An n-vertex self-complementary graph has exactly half as many edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3.{{citation | last = Sachs | first = Horst | authorlink = Horst Sachs | mr = 0151953 | journal = Publicationes Mathematicae Debrecen | pages = 270–288 | title = Über selbstkomplementäre Graphen | volume = 9 | year = 1962 | issue = 3–4 | doi = 10.5486/PMD.1962.9.3-4.11 }}. Since n(n − 1) must be divisible by 4, n must be congruent to 0 or 1 modulo 4; for instance, a 6-vertex graph cannot be self-complementary.

Computational complexity

The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem.

References

References

1. (1978). "Graph isomorphism and self-complementary graphs". [[SIGACT News]].

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::