|
[[File:Petersen graph complement.svg|thumb|300px|The [[Petersen graph]] (onis the left) and its complement graph (onwith thezero right).]]degree
[[File:Kneser graph KG(5,2).svg|thumb|The Petersen graph as Kneser graph KG(5,2) ...]]
[[File:Johnson graph J(5,2).svg|thumb|... and its complement the Johnson graph J(5,2)]]
In [[graph theory]], the '''complement''' or '''inverse''' of a graph ''G'' is a graph ''H'' on the same vertices such that two distinct vertices of ''H'' are adjacent [[if and only if]] they are not adjacent in ''G''. That is, to generate the complement of a graph, one fills in all the missing edges required to form a [[complete graph]], and removes all the edges that were previously there. It is not, however, the [[complement (set theory)|set complement]] of the graph; only the edges are complemented.
==Formal construction==
Let ''G'' = (''V'', ''E'') be a [[simple graph]] and let ''K'' consist of all 2-element subsets of ''V''. Then ''H'' = (''V'', ''K'' \ ''E'') is the complement of ''G''.
==Applications and examples==
Several graph-theoretic concepts are related to each other via complement graphs:
*The vertices of the [[w:Kneser graph|Kneser graph]] KG(''n'',''k'') are the ''k''-subsets of an ''n''-set, and the edges are between [[Disjoint sets|disjoint]] sets. The complement is the [[:en:Johnson graph|Johnson graph]] J(''n'',''k''), where the edges are between intersecting sets.
*The complement of an [[edgeless graph]] is a [[complete graph]] and vice versa.
*An [[independent set (graph theory)|independent set]] in a graph is a [[clique (graph theory)|clique]] in the complement graph and vice versa.
*The complement of any [[triangle-free graph]] is a [[claw-free graph]].
*A [[self-complementary graph]] is a graph that is [[graph isomorphism|isomorphic]] to its own complement.
*[[Cograph]]s are defined as the graphs that can be built up from [[disjoint union]] and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.
==References==
* {{citation
| last1=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy
| last2=Murty | first2=U. S. R. | authorlink2=U. S. R. Murty
| title=Graph Theory with Applications
| year=1976
| publisher=North-Holland
| isbn=0-444-19451-7
| url=http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf
}}, page 6.
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.
[[Category:Graph operations]]
| 