Vsi Hamiltonovi grafi so dvopovezani, ni pa nujno, da je bipovezan graf Hamiltonov (glej na primer Petersenov graf). Eulerjev graf G (povezan graf, v katerem ima vsako oglišče sodo stopnjo) nujno ima Eulerjev ogled, zaprt sprehod, ki gre skozi vsak rob G natančno enkrat.
Ali je graf lahko hamiltonov, ne pa Eulerijev?
Povezan graf G je Hamiltonov, če obstaja cikel, ki vključuje vsako točko G; tak cikel imenujemo Hamiltonov cikel. … Ta graf je OBA Eulerijev in Hamiltonov. Ta graf je Eulerjev, vendar NE Hamiltonov. Ta graf je hamiltionski, vendar NE Eulerijev.
Ali je vsak Hamiltonov graf Eulerjev?
Št. Hamiltonova pot obišče vsako točko natanko enkrat, vendar lahko ponovi robove. Eulerijevo vezje prečka vsak rob v grafu natanko enkrat, vendar lahko ponovi vozlišča.
Kaj ni Eulerian, ni Hamiltonov?
Celoten dvodelni graf K2, 4 ima Eulerjev krog, vendar ni hamiltonov (v resnici ne vsebuje niti Hamiltonove poti). Vsaka Hamiltonova pot bi zamenjala barve (in ni dovolj modrih vozlišč).
Ali so vsi popolni grafi Eulerjevi?
Graf je Eulerian, če in samo če je stopnja vsakega oglišča soda. Zato je Kn Eulerian, če je n liho. (ii) Edini pol-Eulerjev popoln graf je K2. … Graf je povezan, in točno sodve točki lihe stopnje.
