$$x_1$$

. . .

$$x_2$$

. . .

$$x_3$$

. . .

$$s$$

$$t$$

$$C_1$$

$$C_2$$

$$x_1$$

$$x_2$$

$$x_3$$

1. Any Hamiltonian Cycle in the constructed graph ($G$) traverses $P_i$ either from right-to-left or left-to-right.
This is because any path entering a node $v_{i,j}$ has to exit from $v_{i,j+1}$ either immediately or via one
clause-node in between, in order to maintain Hamiltonian property
Similarly all paths entering at $v_{i,j-1}$ has to exit from $v_{i,j}$.

2. Since each path $P_i$ can be traversed in $2$ possible ways and we have $n$ paths mapping to $n$ variables,
there can be $2^n$ Hamiltonian cycles in the graph $G$ - {$C_1$, $C_2$ $\cdots$ $C_k$}.
Each one of this $2^n$ Hamiltonian cycles corresponds to a particular assignment for variables $x_1$, $x_2$ $\cdots$ $x_n$.


3. This graph can be constructed in polynomial time.

1. If there exists a Hamiltonian cycle $H$ in the graph $G$,
If $H$ traverses $P_i$ from left to right, assign $x_i = True$
If $H$ traverses $P_i$ from right to left, assign $x_i = False$

Since H visits each clause node $C_j$, at least one of $P_i$ was traversed in the right direction relative
to the node $C_j$
The assignment obtained here satisfies the given 3 CNF.

2. If there exists a satisfying assignment for the 3 CNF,
Select the path that traverses $P_i$ from left-to-right if $x_i = True$ or right-to-left if $x_i = False$
Include the clauses in the path wherever possible.
Connect the source to $P_1$, $P_n$ to target and $P_i$ to $P_{i+1}$ appropriately so as to maintain the continuity
of the path
Connect the target to source to complete the cycle

Since the assignment is such that every clause is satisfied, all the clause-nodes are included in the path.
The $P_i$ nodes and source and target are all included and since the path traverses unidirectional,
no node is repeated twice
The path obtained is a Hamiltonian Cycle