|
An Euler tour, path is a path through a graph which
starts and ends at the same vertex and includes every edge exactly
once. The well-known Königsberg bridges problem is an example of an Euler tour.
Euler showed that a connected graph has an Euler path if and only if it has at
most two graph vertices of odd degree. Vertices of odd degree are vertices
which are connected to odd number of neighboring vertices. Thus, in order
for an Euler tour to be possible, a maximum of two vertices are allowed to be
connected to odd number of neighboring vertices.
|
