| Version current |
Version 13 |
| An \emph{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 \emph{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. |
An Euler path along a connected graph with $n$ vertices is a path connecting all $n$ vertices, and traversing every edge of the graph only once. Note that a vertex with an odd \PMlinkid{degree}{788} allows one to traverse through it and return by another path at least once, while a vertex with an even degree only allows a number of traversals through, but one cannot end an Euler path at a vertex with even degree. Thus, a connected graph has an Euler path which is a circuit (an Euler circuit) if all of its vertices have even degree. A connected graph has an Euler path which is non-circuituous if it has exactly two vertices with odd degree. |
|
|
| 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. |
|
|
|
| \begin{center} |
\begin{center} |
| \includegraphics[width=1in,height=1in]{ecircuit} |
\includegraphics[width=1in,height=1in]{ecircuit} |
| \end{center} |
\end{center} |
|
|
|
This graph has an Euler cycle. All of its vertices are of even degree.
|
This graph has an Euler path which is a circuit. All of its vertices are of even degree.
|
|
|
| \begin{center} |
\begin{center} |
| \includegraphics[width=1in,height=1in]{epath} |
\includegraphics[width=1in,height=1in]{epath} |
| \end{center} |
\end{center} |
|
|
| This graph has an Euler path which is not a cycle. It has exactly two vertices of odd degree. |
This graph has an Euler path which is not a circuit. It has exactly two vertices of odd degree. |
|
|
|
Note that a graph must be connected to have an Euler path or circuit. A graph is \textbf{connected} if every pair of vertices $u$ and $z$ has a path $uv,\dots,yz$ between them. |
