Bebizonyítjuk, hogy Gábor biztosan visszajut az állomásra, ha minden elágazásnál olyan utat választ a továbbhaladásra, amelyen addig páratlan sokszor járt. Ehhez elegendő azt megmutatni, hogy ha egy kereszteződésnél már nem tud így továbbhaladni, akkor szükségképpen az állomás előtt áll. Az általa páratlan sokszor érintett utcák száma ugyanis egyre csökken, azaz előbb-utóbb lesz olyan elágazás, amelyből kiinduló minden utat már páros sokszor tett meg.
Tegyük fel tehát, hogy Gábor egy olyan útkereszteződésben áll, ahonnan csupa olyan utca indul, amelyen addig páros sokszor járt. Ebből következik, hogy az elágazáshoz ugyanannyiszor érkezett meg, ahányszor elhagyta azt. Minden ,,érkezéshez'' (az utolsót leszámítva) tartozik egy ,,távozás'', amikor továbbment. Ezeken a párokon kívül marad még a mostani ,,érkezés'', és egy ,,távozás''. Ezek azonban nem egymás után történtek, hiszen Gábor éppen itt áll, és még nem ment tovább; vagyis a ,,távozás'' csak a nap legelején történhetett: az egész út innen indult, Gábor tehát az állomás előtt áll.