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.

This graph is formed from the 2-satisfiability instance

$\genfrac{}{}{0ex}{}{{\displaystyle (x_0\vee x_2)\wedge (x_0\vee \mathrm{\neg }{x}_3)\wedge (x_1\vee \mathrm{\neg }{x}_3)\wedge (x_1\vee \mathrm{\neg }{x}_4)\wedge (x_2\vee \mathrm{\neg }{x}_4)\wedge }}{(x_0\vee \mathrm{\neg }{x}_5)\wedge (x_1\vee \mathrm{\neg }{x}_5)\wedge (x_2\vee \mathrm{\neg }{x}_5)\wedge (x_3\vee x_6)\wedge (x_4\vee x_6)\wedge (x_5\vee x_6)}$

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

${\displaystyle (x_0\vee \mathrm{\neg }{x}_3)\equiv (\mathrm{\neg }{x}_0\Rightarrow \mathrm{\neg }{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.