Euler Graphs

Euler's Theorem 1 If a graph has any vertex of odd degree then it cannot have an euler circuit. If a graph is connected and every vertex is of even degree, then it at least has one euler circuit. An applet on Finding Euler Circuits

Euler's Theorem 2 If a graph has more than two vertices of odd degree then it cannot have an euler path. If a graph is connected and has just two vertices of odd degree, then it at least has one euler path. Any such path must start at one of the odd-vertices and end at the other odd vertex.

Fleury's Algorithm for finding an Euler Circuit Check to make sure that the graph is connected and all vertices are of even degree Start at any vertex Travel through an edge: If it is not a bridge for the untraveled part, or there is no other alternative Label the edges in the order in which you travel them. When you cannot travel any more, stop. (You are done!) An illustration of Fleury's Algorithm

Eulerization of non-eulerian Graphs