Reduce Hamiltonian Path to CNF SAT

Question

I'm trying to figure out how to reduce a 5 vertex graph to a Boolean equation that will answer if the graph contains a Hamiltonian path.

For a Hamiltonian Path to be present in a graph: Each vertex must be in the path exactly one time Each vertex must have an edge between them (except for the start and end vertex)

I'm not sure how to make this into a Boolean equation. I start by labeling all the vertexes $$V_{1}, V_{2}, V_{3}, V_{4}, V_{5}$$

An now through some combination of and, or, and not, I need to express the above properties. Any ideas?

Answer 1

This paper explains the technique for doing such a reduction: http://www.cse.msu.edu/~torng/Classes/Archives/cse830.03fall/Lectures/example-reductions.pdf