Grafuri Euleriene

Dacă la grafurile hamiltoniene căutăm cicli care să conțină toate nodurile, aici ne interesează cicli care să conțină toate muchiile.

Din fericire în acest caz există algoritm cu timp de calcul de ordin polinomial. Totul se bazează pe rezultatul: un graf conține ciclu eulerian dacă și numai dacă toate nodurile au grad par (și toate muchiile sunt în aceeași componentă conexă).