next up previous contents index Search
Next: Hamilton Circuits Up: 0.4.2 Graph Traversal Previous: Breadth-first traversal Euler Cycles

A cycle in a graph is a traversal which visits no node more than once. An Euler cycle is a special cycle that traverses all the edges in a graph and visits every node at least once. It can be proven that an Euler cycle can exist in a graph if and only if all vertices are of even degree. That is to say, the must be an even number of edges emanating from every vertex in the graph.

Scott Gasch