Algorithms - Finding Clique of size n in a Graph

Question

I have the following statements (NOTE: $\bar x$ means the complement of $x$):

$(x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4)$

I need to do the following: Convert this to the graph G=(V,E) so that this G will have a clique of size 4 if and if CNF is satisfiable. Will G have a cliqueemphasized text of size 4?

I am confused how to approach this problem. My work so far consists of setting up the following nodes in the graph (where ~x means complement of x):

x1    ~x2    x3        (nodes formed from first set (x1 V ~x2 V x3)

~x1    x2    x3        (nodes formed from second set (~x1 V x2 V x3)

x1     ~x3             (nodes formed from third set (x1 V ~x3)

x2     ~x3   x4        (nodes formed from fourth set (x2 V ~x3 V x4)

I then put edges to all nodes except their complements (for example, $x_1$ will not connect to $ \bar x_1$).

I am stuck trying to finish this problem. I don't understand how to convert the graph G=(V,E) so that this G will have a clique of size 4 if and if CNF is satisfiable. And how to answer the question: Will G have a clique of size 4?

I looked up Boolean Satisfialbility on Wikipedia: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem but I still do not understand how to finish this problem.

Any help would be much appreciated, thank you.

Answer 1

Let's call your formula CNF. Let's call the clauses $C_1, C_2, C_3, C_4$
Let $v_i$ be a literal in $C_i$
By your conversion, every $(v_i, v_j)$ for $i \neq j$ and $v_i \neq \bar v_j$ is an edge in G.

Now we have to prove: CNF is satisfiable $\iff$ G(V, E) has a clique of size 4

Suppose CNF is satisfiable
$\quad$This means every clause has at least one literal that is true.
$\quad$From each clause $C_i$, pick any one $v_i$ that is true.
$\quad$Now we have a set of 4 vertices $\{v_1, v_2, v_3, v_4 \}$ in $G(V, E)$
$\quad$Since all the $v_i$ are true, neither is a complement of the other.
$\quad$So, there must be an edge between every pair of vertices in the set.
$\quad$So, the set of vertices form a clique of size 4 in G(V, E).

Suppose $G(V, E)$ has a clique of size 4
$\quad$There are 4 vertices in the clique $v_1, v_2, v_3, v_4$
$\quad$Since each pair of vertices is connected by an edge and our conversion does not connect 2 literals $\quad$from the same clause, each vertex must be in a different clause.
$\quad$So, each clause has a literal/vertex in the Clique.
$\quad$So, assigning true to each of the vertices would satisfy CNF.