DescriptionImplication graph.svg	An implication graph
Date	2 May 2008
Source	Own work
Author	David Eppstein
Permission (Reusing this file)	Public domainPublic domainfalsefalse I, the copyright holder of this work, release this work into the public domain. This applies worldwide. In some countries this may not be legally possible; if so: I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Detailed description edit

This graph is formed from the 2-satisfiability instance

${\displaystyle \scriptstyle (x_{0}\lor x_{2})\land (x_{0}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{4})\land (x_{2}\lor \lnot x_{4})\land {} \atop \scriptstyle \quad (x_{0}\lor \lnot x_{5})\land (x_{1}\lor \lnot x_{5})\land (x_{2}\lor \lnot x_{5})\land (x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6})}$

by replacing each disjunction by the two implications to which it is equivalent, e.g.,

${\displaystyle \scriptstyle (x_{0}\lor \lnot x_{3})\equiv (\lnot x_{0}\Rightarrow \lnot x_{3})\equiv (x_{3}\Rightarrow x_{0}),}$

and then representing the implications graphically as directed edges in a graph.

The solution set for the same example instance is depicted in Image:2SAT median graph.svg.