Megmutatjuk, hogy pontosan a következő gráfok találomra bejárhatóak: a(z egy és) kétpontú összefüggő gráf, valamint a (legalább három csúcsú) körök. A felsorolt gráfok nyilván ilyenek; tegyük fel a továbbiakban, hogy adott egy legalább három csúcsú, találomra bejárható gráf. Mivel a gráf bármely csúcsából kiindulva bejárható, és a csúcsok száma legalább 3, azért mindegyik csúcsa páros fokú, azaz létezik benne Euler-féle zárt séta (azaz a gráf bejárható úgy, hogy a végén a kiindulási csúcsba érkezünk vissza). Így persze a gráf szükségképpen tartalmaz kört; jelölje az egyik körét $k$.
Megmutatjuk, hogy az egész gráf csupán ebből a $k$-ból áll. Ezt belátandó tételezzük fel először, hogy a gráfnak van $k$-hoz nem tartozó éle is. Hagyjuk el a gráfból a $k$ körhöz tartozó éleket; a megmaradó ‐ nemüres ‐ gráfban is létezik Euler-féle zárt séta, hiszen az eredeti gráfot bejárhatjuk úgy, hogy először a $k$ körön megyünk végig. Ha létezne a gráfban olyan csúcs, amely nem $k$-n fekszik, akkor járjuk be a megmaradó gráfot egy ilyen csúcsból kiindulva, vagyis az iménti zárt sétát ezen a helyen kezdve és végezve; ha ezután innen továbbhaladva folytatni kívánnánk immár az egész eredeti gráf bejárását, akkor ezen a módon nem leszünk rá képesek, hiszen már csak a $k$-beli élek bejáratlanok, ám azok egyikét sem érhetjük el egy külső pontból, mivel az odavezető élek mindegyikén előzőleg végimentünk már. Ez ellentmond a gráf találomra bejárhatóságának. Tehát $k$ minden csúcson (pontosan egyszer) áthalad. Azt kell már csak belátnunk, hogy a gráfban nincs is $k$ élein kívül további él. Ha lenne, akkor egy ilyen él a kör két nem szomszédos csúcsát kötné össze, ezért a körünket két rövidebb körre vágná szét. Ilyen rövidebb (azaz nem mindegyik csúcson áthaladó) kör azonban a fentiek szerint nincsen.