Az Euler-út és -kör nélküli gráf

Bizonyítás

Ha belépek egy csúcsba és onnan kijövök, az két fokszámot vesz el. Így minden lépésnél -vel csökken a csúcs fokszáma, tehát a paritás (a -vel való osztáskor keletkező maradék) nem változik. Így mivel van páratlan fokszámú csúcs, a gráfnak nem lehet Euler-köre. "A gráf Euler-útjának megkeresése" című bizonyításnál beláttuk, hogy két páratlan fokszámú csúcsnál van csak Euler-út. Ha ennél több van, akkor a bizonyítás során létrehozott "Euler-kör" több, mint egy helyen megszakad, így itt Euler-út sem lehetséges. A gráfnak nem lehet páratlan fokszámú csúcsa, mivel "Az élszámra vonatkozó Euler-tétel" bizonyításánál beláttuk, hogy a fokszámok összege mindig páros.