# Given a graph and specific VC instance, find number of variables when reducing from VC to SAT

I have question already answered from past exam, and I'm trying to figure where my logic fails.

Given a graph find vertex cover of size 2.

The question is how many variables are there going to be for the CNF when doing polynomial reduction for the input $$\langle G,2 \rangle$$ to SAT? specify those variables.

The answer given is : $$X11$$ $$X12$$ $$X13$$ $$X14$$ $$X15$$ $$X16$$ $$X21$$ $$X22$$ $$X23$$ $$X24$$ $$X25$$ $$X26$$

I didn't understand the answer. I tried to follow the logic from this thread: Reduce Vertex cover to SAT

But the answers do not seem to correlate.

Following the thread: Each node receives a certain $$x_i$$ marking whether or not the node is part of the $$VC$$. My nodes are $$v_1$$ and $$v_6$$ for vertex cover so its corresponding $$x_i$$ has the value $$1$$. other variables have $$x_i$$ with value $$0$$. For each edge in the graph presenting the clause $$\left \{ x_i\vee x_j \right \}$$. This is the part where I get a different answer : I get $$X_{12}$$ $$X_{13}$$ $$X_{14}$$ $$X_{15}$$ $$X_{16}$$ $$X_{56}$$ which is completely different answer from what was given... I tried to search the web but the thread is the best reference I could find(it seemed the most identical..). What is the problem with my way of solving?

• There is no single reduction from vertex cover to SAT. Perhaps the answer refers to a different reduction? Oct 2 at 10:52