> 1. [send a link for each possible combination]

> 2. instruct clients on how to construct appropriate URIs

> 3. link a URI for the starting city and then from there link them to possible choices of the second city

All three of these are possible RESTful solutions, and I can imagine situations where each of them might make sense.

But what you're probably looking for is something like this:

  <form><select name="city1">...</select><select name="city2">...</select></form>

(Using URL templates is a potentially simpler way to achieve the same thing). This is, of course, your solution 2.

There are tradeoffs involved in using this style. Are they worth it? That really depends on the larger system and all kinds of details which you've left out.