Given a network, or graph, an Euler Cycle is a tour from vertex to vertex, finishing where it started, and traversing every edge exactly once.
More formally ...
Given a graph $G=(V,E)$ where $|E|=m,$ an Euler Cycle is a list $L=[v_0,v_1,...,v_m]$ of vertices such that:
This definition does not require the graph to be connected, but in the case
of a graph with more than one component, all but at most one component must
contain exactly one vertex and no edges.
The "degree" of a vertex is the number of edges incident to it, and it is a well-known theorem that a connected graph is Eulerian if and only if every vertex has even degree. A graph has an Eulerian Path that is not a cycle if and only if every vertex has even degree except for two.
|The well-known Bridges of Koenigsberg problem asks if the road network of a particular town is Eulerian. Some versions require an Euler Cycle, but many ask only for an Euler Path. Neither is possible, as proven by Leonhard Euler in 1736. The Doodle Theorem says that a planar Eulerian graph can be two-coloured, and hence is bi-partite.
Links on this page