Complement graph: Difference between revisions

Revision as of 23:45, 10 February 2016

Revision as of 23:56, 10 February 2016

Line 14:

==Formal construction==

Let {{math|1=''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'')}} be a [[simple graph]] and let ''{{mvar|K''}} consist of all 2-element subsets of ''{{mvar|V''}}. Then {{math|1=''H''&nbsp;=&nbsp;(''V'',&nbsp;''K''&nbsp;\&nbsp;''E'')}} is the complement of ''{{mvar|G''}}.<ref>{{Citation

| last=Diestel | first=Reinhard

| title=Graph Theory

Line 22:

| isbn=3-540-26182-6

}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref>

For [[directed graph]]s, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set pf all 2-element [[ordered pair]]s of ''V'' in place of the set ''K'' in the formula above.

The complement is not defined for [[multigraph]]s. In graphs that allow [[loop (graph theory)|self-loops]] (but not multiple adjacencies) the complement of {{mvar|G}} may be defined by adding a self-loop to every vertex that does not have one in {{mvar|G}}, and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result in a graph with self-loops on all vertices.

==Applications and examples==