Complement graph: Difference between revisions

Revision as of 00:24, 11 February 2016

Revision as of 00:25, 11 February 2016

Line 1:

[[File:Petersen graph complement.svg|thumb|upright=1.35|The [[Petersen graph]] (on the left) and its complement graph (on the right).]]

In [[graph theory]], the '''complement''' or '''inverse''' of a graph ''{{mvar|G''}} is a graph ''{{mvar|H''}} on the same vertices such that two distinct vertices of ''{{mvar|H''}} are adjacent [[if and only if]] they are not adjacent in ''{{mvar|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.<ref name="bm">{{citation

| last1=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy

| last2=Murty | first2=U. S. R. | authorlink2=U. S. R. Murty