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 graphMathworldPlanetmath has an Euler path, one can be constructed by applying Fleury’s algorithmMathworldPlanetmath. 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