Show that a problem is NP-Complete
You need to choose an NP-hard problem, and show a deterministic polynomial-time algorithm that transforms any instance of this NP-hard problem to an instance of your city problem that is true if and only if the original instance was true. As you suggested in the question, Hamiltonian path is a good choice for the starting problem.

Try to create an algorithm that takes any Hamiltonian path instance and constructs a "city problem" instance which has the same truth value. You must also write a proof that, for any input instance of Hamiltonian path, the corresponding output instance of the "city problem" has the same truth value.

Hint 1:


   Think about subdividing edges.


Hint 2:


   If you take an arbitrary (undirected simple) graph and subdivide each edge once, you get a graph in which none of the original vertices are adjacent to each other.