MetaMath '22

U nekoj državi između svaka dva grada postoji ili izravna autobusna ili izravna željeznička veza (sve veze su dvosmjerne i ne prolaze ni kroz jedan drugi grad).

Dokaži da je gradove u toj državi moguće rasporediti u dva disjunktna skupa tako da je sve gradove u jednom skupu moguće obići putujući samo željeznicom tako da se nijedan grad ne posjeti dvaput, a sve gradove u drugom skupu putujući samo autobusom tako da se nijedan grad ne posjeti dvaput.