Revision as of 10:58, 5 July 2009 edit Miym (talk \| contribs) 4,240 edits m add comma ← Previous edit		Revision as of 11:13, 5 July 2009 edit undo Miym (talk \| contribs) 4,240 edits some concrete examples (removed some old content, as it was a bit vague and the links didn't point to articles that actually showed some applications) Next edit →
Line 8: Let ''G'' = (''V'', ''E'') be a [[simple graph]] and let ''K'' consists 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. For example, 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]]. ~~The complement graph is used in several graph theories and demonstrations, such as the [[Ramsey theory]], and different reductions for proofs of [[NP complete\|NP-Completeness]].~~ ==References==

Complement graph: Difference between revisions