Задача из Нетологии.
К сожалению, проверки ДЗ у меня нет, но я решил так:
select c.city as "Город 1", c2.city as "Город 2"
from (select distinct city from city) c
cross join (select distinct city from city) c2
where c.city <> c2.city
order by "Город 1", "Город 2"