Primes in a Diamond

Question

Label the vertices of this graph with numbers 1 to 16 in such a way that the edges between any two vertices whose sum and absolute difference are both primes are precisely the edges of a hamiltonian circuit of the graph, that is a tour of all of the graph's vertices that visits each vertex exactly once, and returns to the vertex from where it started.

For your convenience, five of the numbers have been placed.

Answer 1

First, I found all pairs that satisfy the criteria:

Next, we can start making some deductions:

1 must connect both southwest and south, and 15 must connect both northeast and southeast. Since 15 only connects to {2,4,8}, and 8 is already used, 4 must go northeast of it and 2 must go southeast.

That gives this new grid:

Next,

1 must connect to 16 or 12, neither of which connects to 8. So that resolves more of the path. Additionally, 2 connects to 9 only out of the leftovers, which connects to 14 only, which connects to 3 only, which does not connect to the 13 it is adjacent to.

That resolves the rest of the path, but not the numbers:

For the numbers,

the 1 must have a 2-chain leading to 8. Out of the remaining numbers, that can only be 1-6-11-8. And finally, the 5 only connects to 12, which only connects to 7, which only connects to 10, and so the chain can be completed.

The final answer to the puzzle:

And to double-check the result:

The only extra lines we're concerned about are when an odd and an even number are adjacent, but not connected. These pairs are 11-14, 11-16, 7-16, and 1-8. None of these have both sum and difference prime, so the puzzle is solved.