У нас связный (наверное, ведь это же один город) граф. Пусть число вершин нечетной степени =к. Тогда этот граф можно покрыть к/2 цепями, реберно непересекающимися. Каждую такую цепь ориентируем в одну сторону (в какую именно - смотрим по условиям).
Это, конечно, не доказательство - только направление, куда думать.