# Not All Equal 2-Sat Problem

I'm going over past papers for my exam and I came across this question. The only time I have heard of "Not-All-Equal" was as a 3-Sat problem, so I'm wondering if this question does actually mean 2-Sat and if so, could you possibly explain?

I dont really want an answer, I'd much rather an explaination so that I can work it out for myself.

Question: We consider a special case of the Not-All-Equal 2-SAT problem where no literal contains a negation. The task is to decide if it i s possible to assign truth values to the variables such that each clause has one literal that is true and one that is false. Recall that 2-COL (or 2-Colourability) is the decision problem where the input is a graph and the task is to determine if the vertices can be coloured by 2 colours such that neighbouring vertices (vertices joint with an edge) have different colours.

a) Consider the Not-All-Equal 2-SAT problem given by the clauses

{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}

Are these clauses Not-All-Equal satisfiable? Explain why this problem is equivalent to a 2- COL problem.

Draw the graph for this 2-COL problem and explain why the graph not is 2-Colourable.

• This one is easy because its graph is a cycle of odd length. – coffeemath Apr 4 '16 at 16:53

I assume your notation $\{x_i,x_j\}$ which you call a clause is just a set of two propositions $x_i$ and $x_j$ and that clause is called "not-all-equal" satisfiable provided one may assign truth values such that one of $x_i,x_j$ is T (true) and the other F (false).
Since it doesn't matter which is a true, it makes sense to draw this particular clause as a line segment connecting nodes $x_i$ and $x_j.$ In any given situation we make nodes for each proposition and connect any two that appear in the same clause. This is the connection to 2-colorability since if A,B colors denote T,F then the clause is not-all-equal satisfiable iff there is a two coloring such that no two nodes connected by a segment should be the same color.