Let G be a graph. Carry out the following steps:
(1) If G is not connected3 or if G contains a vertex of odd degree, STOP: the problem has no solution.
(2) (We now know that G is connected and that all vertices of G have even degree.) Choose an edge e1, consider each permutation (
, . . . , 
) of the remaining edges and check whether (
, . . . , ) is an Euler tour, until such a tour is found.