Я подумал, что может возникнуть ситуация, когда город

соединен со всеми остальными городами так, что все дороги исходят из

. Вот картинка примерная.

1) При этом, если из

города выехать в первый, то можно объехать все города (побывав в каждом только один раз), односторонность соблюдется!
2) Если будет ситуация, когда все дороги из городов

ведут в город

, то можно объехать все города (побывав в каждом только один раз, выехав из 1 города во второй), односторонность соблюдется!
Но, например, вот в такой ситуации -- движение не будет односторонним.

Мне кажется, что третьего варианта -- нет, потому как движение не будет иначе односторонним. То есть либо все города соединены дорогой из

, либо все города соеденены дорогой в

. В обоих случаях можно объехать все города, побывав в каждом ровно один раз. Значит по индукции доказали. Верно?