Graf hamiltonowski, ale nie eulerowski agata_12: Czy istnieje graf hamiltonowski, które nie jest eulerowski? I nie mam tu na myśli półhamiltonowskich. Bo półhamiltonowski, które nie jest eulerowski łatwo znaleźć. Ale hamiltonowski, który nie jest eulerowski już nie.

Pytający:

agata_12: No ale zaraz. Czy w hamiltonowskim grafie nie jest tak, że przy jednym wierzchołku można być tylko raz przemierzając drogę hamiltonowską?

Pytający: Przy wierzchołku w zasadzie można być 2 razy (którędyś wchodzimy i którędyś wychodzimy). Natomiast w samym wierzchołku tylko raz. Ewentualnie można powiedzieć, że ustalony pierwszy wierzchołek cyklu odwiedzamy dwukrotnie (bo jest jednocześnie wierzchołkiem ostatnim). Na rysunku przykładowy cykl Hamiltona.