This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

FindEulerianCycle

FindEulerianCycle[g]
finds an Eulerian cycle in the graph g if one exists.
FindEulerianCycle
finds at most k Eulerian cycles.
  • An Eulerian cycle is a cycle that traverses every edge exactly once.
Find an Eulerian cycle in an undirected graph:
In a directed graph:
Find an Eulerian cycle in an undirected graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
 
In a directed graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
FindEulerianCycle works with undirected graphs:
Directed graphs:
Find at most 3 Eulerian cycles:
FindEulerianCycle returns an empty result for non-Eulerian graphs:
Works with large graphs:
Trace out the figure of an envelope without lifting the pen and without going over the same line twice:
The graph is not Eulerian:
Since there are two odd-degree vertices, an augmented Eulerian graph is constructed by joining the odd-degree vertices via a new vertex (to avoid multiple edges):
Find an Eulerian cycle in the augmented graph:
Rotate the edges of the cycle until the edges involving the vertex become the last ones:
Show the Eulerian path:
Find the order of vertices visited along a directed cycle:
Pick the source vertex of each edge:
Find the order of vertices visited along an undirected cycle:
The path starts at a vertex of the first edge, which is not a vertex of the second edge unless the first edge is a self-loop:
Find the vertices by following the edges in order:
Test whether a graph has an Eulerian cycle using EulerianGraphQ:
A connected undirected graph has an Eulerian cycle iff every graph vertex has an even degree:
An undirected graph has an Eulerian cycle if it can be decomposed into edge-disjoint cycles:
The graphs are cycles if they are connected and the number of vertices and edges coincide:
For a connected directed graph:
The line graph of an undirected Eulerian graph has an Eulerian cycle:
A directed graph has an Eulerian cycle iff every vertex has equal in-degree and out-degree:
New in 8