# How can I convert this graph into CNF to solve the hamiltonian path with SAT?

So I have this graph,

I am following the rules outlined in these slides: https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20111018.pdf

The rules for converting the graph to CNF and the proof are in the first few slides.

So far I have the following for the CNF:

(x11 V x12 V x13 V ¬x21 V¬x31 V ¬x22 V¬x32 V ¬x23 V¬x33 ) ^
(x21 V x22 V x23 V ¬x11 V¬x31 V ¬x12 V¬x32 V ¬x13 V¬x33) ^
(x31 V x32 V x33 V ¬x11 V¬x21 V ¬x12 V¬x22 V ¬x13 V¬x23) ^
(¬x11 V ¬x23) ^
(¬x21 V ¬x33) ^
(¬x12 V ¬x23) ^
(¬x22 V ¬x33)


My first question is if I converted it correctly.

My next question is how to show that T entails R(G) where R(G) is the CNF.

I understand that this graph there is no hamiltonian path and I would like to somehow prove that.

• Can you explain what does it mean to convert the graph to a CNF, and what $T$ is? Don't rely on the link, which might rot in the future. – Yuval Filmus Nov 7 '19 at 9:34