Mi a különbség a hamilton-kör és az euler-kör, illetve a hamilton-vonal és az euler-vonal között?

Az Euler-kör az éleken megy keresztül és a kezdőcsúcsba jut vissza (mint amikor az volt a kérdés, hogy egy adott ábra megrajzolható-e úgy, hogy nem emeljük fel a ceruzát, a problémát a königsbergi hidak ihlették), a Hamilton-kör a csúcsokat járja végig (például ha adott 10 város, amik között utak vannak kiépítve, akkor a városokon végig lehet-e menni úgy, hogy egy városon nem megyünk át egynél többször, és az utolsó városból vissza lehet-e jutni a kiinduló városba). Ugyanez igaz a Hamilton-kör és Euler-vonal esetén is, annyi különbséggel, hogy nem kell tudni visszajutni a kezdő csúcsba (illetve inkább nyílt és zárt Euler-vonalnak szokták őket hívni, nem Euler-körnek; a zárt esetben vissza lehet jutni a kezdőpontba).

Másik lényeges különbség, hogy nyílt és zárt Euler-vonal nem lehet egyszerre egy gráfban; vagy az egyik, vagy a másik, vagy egyik sem. A Hamilton-út/kör esetén előfordulhat, hogy mindkettő van. Nyilván ha van Hamilton-kör, akkor létezik Hamilton-út is, az előbb arra gondoltam, hogy a Hamilton-körtől különböző megoldás található a Hamilton-útra.

A fő különbség az az, hogy az Euler-vonalakra van szükséges és elégséges feltétel; zárt van akkor (és csak akkor), hogyha minden csúcs fokszáma páros, nyílt Euler-vonal akkor, hogyha pontosan 2 darab páratlan fokszámú csúcsa van, a többi páros, ekkor a kiindulópont az egyik páratlan fokszámú csúcs, és a másik páratlanban fog végződni (természetesen akkor, hogyha élösszefüggő a gráf). Hamilton-útra/körre csak szükséges vagy elégséges feltételeket tudunk mondani (mint például a csúcstörlési kritérium vagy a Dirac-tétel vagy a Chávtal-tétel), szükséges és elégséges feltételt nem tudunk mondani. A probléma annyira nehéz, hogy P=NP típusú, vagyis még azt sem lehet eldönteni, hogy adható-e rá szükséges és elégséges feltétel.