Complement graph: Difference between revisions

Revision as of 21:34, 10 February 2016

Revision as of 21:36, 10 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).]]

{{multiple image

[[File:Kneser graph KG(5,2).svg|thumb|The Petersen graph as Kneser graph KG(5,2) ...]]

[[File:Johnson|image1=Kneser graph JKG(5,2).svg|thumb|...caption1=The andPetersen itsgraph complementas the JohnsonKneser graph JKG(5,2)]] ...

|image2=Johnson graph J(5,2).svg|caption2=... 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.<ref name="bm">{{citation

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