({{, (RefLink[GraphComplement, paclet:ref/GraphComplement])[g] 
gives the graph complement of the graph g.}, {, (RefLink[GraphComplement, paclet:ref/GraphComplement])[{v->w,…}]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

The graph complement has the same vertices and edges defined by two vertices being adjacent only if they are not adjacent in g.

(RefLink[GraphComplement, paclet:ref/GraphComplement]) works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (15)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Graph complement of cycle graphs:

Table[CycleGraph[n],{n,4,6}]

GraphComplement/@%

Graph complement of directed graphs:

Table[CycleGraph[n,DirectedEdges->True,EdgeStyle-> Arrowheads[0.1]],{n,4,6}]

GraphComplement/@%

OpenersExampleSection1(Spacer1)Scope  (6)

(RefLink[GraphComplement, paclet:ref/GraphComplement]) works with undirected graphs:

GraphComplement[]

Directed graphs:

GraphComplement[]

Multiple graphs:

GraphComplement[]

Mixed graphs:

GraphComplement[]

Use rules to specify the graph:

GraphComplement[{1->2,1->6,2->3,3->4,4->5,5->6}]

(RefLink[GraphComplement, paclet:ref/GraphComplement]) works with large graphs:

g=GridGraph[{10,10,10,10}];

GraphComplement[g]//EdgeCount // Timing

OpenersExampleSection3(Spacer1)Properties & Relations  (7)

The complement of a (RefLink[CompleteGraph, paclet:ref/CompleteGraph]) is an edgeless graph:

{CompleteGraph[5], GraphComplement[CompleteGraph[5]]}

The complement of the complement is the original graph (for simple graphs):

NestList[GraphComplement,CycleGraph[6],2]

The complement of the graph can be obtained from its adjacency matrix:

g =CycleGraph[5];

m = AdjacencyMatrix[g];

{GraphComplement[g],AdjacencyGraph[1-IdentityMatrix[Length[m]]-m]}

Equal@@(AdjacencyMatrix/@%)

An independent vertex set of the graph is a clique of its complement graph:

g=PetersenGraph[5,2]

FindIndependentVertexSet[%]

FindClique[GraphComplement[g]]

The complement of the line graph of (Subscript[K, 5]) is a Petersen graph:

{GraphComplement[LineGraph@CompleteGraph[5]],PetersenGraph[5,2]}

IsomorphicGraphQ@@%

The graph union of any simple graph and its complement is a complete graph:

g=;

CompleteGraphQ[GraphUnion[g,GraphComplement[g]]]

The graph intersection of any graph and its complement is an empty graph:

g=;

EmptyGraphQ[GraphIntersection[g,GraphComplement[g]]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[GraphDifference, paclet:ref/GraphDifference])  ▪  (RefLink[GraphUnion, paclet:ref/GraphUnion])  ▪  (RefLink[GraphIntersection, paclet:ref/GraphIntersection])  ▪  (RefLink[GraphDisjointUnion, paclet:ref/GraphDisjointUnion])  ▪  (RefLink[BooleanGraph, paclet:ref/BooleanGraph])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Operations and Modifications, paclet:guide/GraphModifications])}})}})