Keywords: 2SAT median graph.svg A median graph representing the set of solutions to a 2-satisfiability instance Own 2008-05-02 David Eppstein This graph is formed from the 2-satisfiability instance <math>\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 x_5 \land x_1\lor x_5 \land x_2\lor x_5 \land x_3\lor x_6 \land x_4\lor x_6 \land x_5\lor x_6 </math> by creating a vertex for each satisfying truth assignment to the formula and an edge between any two assignments that differ in the value of a single variable The vertices in the drawing are labeled by the sequence of variable values <math>\scriptstyle x_0x_1x_2x_3x_4x_5x_6 </math> In general any 2-satisfiability instance has a set of solutions with the structure of a median graph in which the median of any three solutions is formed by taking a majority vote separately for each variable's value However for some 2-satisfiability problems the edges in this median graph may connect pairs of solutions that differ by simultanously flipping several variables that are forced by the instance to all be equal or unequal Files by User David Eppstein from en wikipedia Boolean satisfiability problem Graphs with 16 vertices Related to the cube |