Question

several states in the northeastern United States. Is it possible to find a route that passes over each common state border exactly one time?

Answer 1

If you represent the states as vertices in a graph and
1) You can go from any vertex to any other by following the edges and
2) Every vertex has an even number of edges connected to it except possibly the the start and end points)

Then , yes, you can find a path, else no.