So I have this graph,enter image description here

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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 7 '19 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.