Euler path
An Euler path in a graph is a path which traverses each edge of the graph exactly once. An Euler path which is a cycle is called an Euler cycle. For loopless graphs without isolated vertices, the existence of an Euler path implies the connectedness of the graph, since traversing every edge of such a graph requires visiting each vertex at least once.
If a connected graph
has an Euler path, one can be constructed by applying Fleury’s algorithm
. A connected graph has an Euler path if it has exactly zero or two vertices of odd degree. If every vertex has even degree, the graph has an Euler cycle.
This graph has an Euler cycle. All of its vertices are of even degree.
This graph has an Euler path which is not a cycle. It has exactly two vertices of odd degree.
| Title | Euler path |
|---|---|
| Canonical name | EulerPath |
| Date of creation | 2013-03-22 12:02:04 |
| Last modified on | 2013-03-22 12:02:04 |
| Owner | CWoo (3771) |
| Last modified by | CWoo (3771) |
| Numerical id | 18 |
| Author | CWoo (3771) |
| Entry type | Definition |
| Classification | msc 05C38 |
| Related topic | EulerCircuit |
| Related topic | Graph |
| Defines | Euler cycle |