Content deleted Content added
→Definition: Clarifying what K\E means and wikilinking to relative complement. Unsure if this is a minor edit or not |
|||
Line 11:
==Definition==
Let {{math|1=''G'' = (''V'', ''E'')}} be a [[simple graph]] and let {{mvar|K}} consist of all 2-element subsets of {{mvar|V}}. Then {{math|1=''H'' = (''V'', ''K'' \ ''E'')}} is the complement of {{mvar|G}}
| last=Diestel | first=Reinhard
| title=Graph Theory
Line 18:
| edition=3rd
| isbn=3-540-26182-6
}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref> where {{math|''K'' \ ''E''}} is the [[relative complement]] of {{mvar|E}} in {{mvar|K}}. 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 of all 2-element [[ordered pair]]s of {{mvar|V}} in place of the set {{mvar|K}} in the formula above.▼
▲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 of all 2-element [[ordered pair]]s of {{mvar|V}} in place of the set {{mvar|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.
| |||