Euler cycle:
A path through a given graph which traverses each edge only once and ends up on the starting point. Often confused with Hamiltonian cycle or Hamiltonian circuit.
Euler's Problem
(Pronounced "Oiler's Problem"), also see Euler tour
Simple question: Is there a way through a graph which traverses each edge only once?
The following illustration is commonly associated with this concept*.
+---------------------------------+
| |
| A |
|*****\**********/*****|**********|
| \ / | |
| \ / | |
| \ * */ **|* |
| * * * * |
| * * * * |
| * B *--* D * |
| * * * * |
| * * * * |
| /**\ */* |
| / \ / |
|******/******\*****/*************|
| C |
+---------------------------------+
This is a map (use your imagination) of a river. Points A and C are riverbanks. B and D are islands. The seven lines connecting the islands and river banks are bridges, and are to be thought of as edges. So the question is, is there a way to tour this area while crossing each bridge (traversing each edge) only once?
One way to solve this is to begin at each point and try all possible combinations until every possiblity has been tried (an O(n!) problem). This could take a long time though.
Euler proposed that a Eulerian Path existed through a given graph if and only if the following two criteria were met:
- It must be possible to go from any vertex (point) to any other vertex by following the edges. Which basically means that there may be no non-connected points in the graph.
- Every vertex must have an even number of edges connected to it, with no more than 2 exceptions. The 2 exceptions being the starting and end points.
Now look at our graph.
Each point is connected, so the first criteria has been met.
However, Riverbank (point) A has 3 bridges (3 edges), which is an odd number. Riverbank (point) C has 3 bridges (3 edges) which is an odd number, and island (point) D has 3 bridges (3 edges) which is an odd number. This makes 3 exceptions to the second rule, which allows a maximum of 2 exceptions, and thus this graph has no Eulerian path.
*Update-AT tells me: "...the problem comes from an actual set of bridges -- namely those in the Prussian town of Königsberg (now Kaliningrad, Russia)" | 
