Definiţie: Se numeşte ciclu hamiltonian un ciclu elementar care trece prin toate vârfurile grafului. Un graf care admite un ciclu hamiltonian se numeşte graf hamiltonian.
Fie G = (X,U) un graf neorientat şi un lanţ elementar care trece prin toate nodurile grafului [x0,x1, …, xn]. Dacă d(x1) + d(xn)≥n atunci graful este hamiltonian.
Fie G = (X,U) un graf neorientat cu n noduri. Dacă pentru orice pereche de noduri neadiacente xi≠xj, avem relaţia d(xi) + d(xj)≥n atunci graful este hamiltonian.
Dacă G = (X,U) este un graf neorientat cu n noduri şi gradul oricărui vârf este mai mare sau egal n/2, atunci G este hamiltonian.
Un graf G este hamiltonian dacă are n≥3 vârfuri şi gradul oricărui vârf verifică inegalitatea: d(x)≥n/2.
Exemplu: 1, 2, 3, 9, 8, 7, 5, 6, 4, 1 este ciclu hamiltonian.
Definiţie: Un lanţ al unui graf care conţine fiecare muchie o dată şi numai o dată se numeşte lanţ eulerian. Dacă x0 = xn şi lanţul este eulerian atunci, ciclul respectiv se numeşte ciclu eulerian.
Un graf care conţine un ciclu eulerian se numeşte graf eulerian.
Dacă este eulerian nu înseamnă că nu are vârfuri izolate.
Exemplu: 1, 2, 4, 6, 5, 7, 8, 3, 9, 8, 5, 2, 3, 4, 1 este ciclu eulerian.
Th. lui Dirac: Un graf fără vârfuri izolate, este eulerian dacă şi numai dacă
- este conex
- gradele tuturor vârfurilor sale sunt pare
OBS: Un graf complet cu numar impar de varfuri este hamiltonian si eulerian
Un graf complet cu numar par de varfuri este hamiltonian si NU este eulerian (ar avea
gradele toate impare) => elimin MINIM n/2 muchii si poate deveni eulerian
Graf hamiltonian si eulerian: un poligon
Graf hamiltonian si NU eulerian: un poligon cu o diagonala
Graf NU hamiltonian si eulerian: o fundita cu 5 noduri (unul e in mijloc)
Graf NU hamiltonian si NU eulerian: ciclu neelementar si grade impare