FindEulerianCycle

finds an Eulerian cycle in the graph g.

FindEulerianCycle[g,k]

finds at most k Eulerian cycles.

FindEulerianCycle[{vw,},]

uses rules vw to specify the graph g.

Details

• An Eulerian cycle is a cycle that traverses every edge exactly once.
• FindEulerianCycle returns a list of paths consisting of Eulerian cycles.
• FindEulerianCycle returns the list {} if no Eulerian cycles exist.
• is equivalent to FindEulerianCycle[g,1].
• finds all Eulerian cycles in the graph g.
• FindEulerianCycle works with undirected graphs, directed graphs, and multigraphs.

Background & Context

• FindEulerianCycle attempts to find one or more distinct Eulerian cycles, also called Eulerian circuits, Eulerian tours, or Euler tours in a graph. The cycles are returned as a list of edge lists or as {} if none exist. An Eulerian cycle (more properly called a circuit when the cycle is identified using a explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edge coincide at their endpoints and in which each edge appears exactly once. Eulerian cycles may be used to reconstruct genome sequences, construct de Bruijn sequences, and to find optimal conference scheduling.
• FindEulerianCycle[g,k] attempts to find k Eulerian cycles, where the count specification k may be omitted (in which case it is taken as 1), may be a positive integer, or may be All. Eulerian cycles need not be simple cycles, i.e. there can be a repeated vertex in a cycle (unlike Hamiltonian cycles, which are always simple).
• A graph possessing an Eulerian cycle is known as an Eulerian graph. However, some care is needed in interpreting the term, since some authors define an Euler (as opposed to "Eulerian") graph as a different object, namely a graph for which all vertices are of even degree. The latter definition is motivated by Euler's correct (but unproved by him) observation that a connected simple graph possesses an Eulerian circuit if and only if it has no vertices of odd degree. Eulerian cycles are therefore mathematically easier to study than Hamiltonian cycles. While the number of connected Euler graphs on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for disconnected graphs since there exist disconnected graphs having multiple disjoint cycles with each node even but for which no single cycle passes through all edges.
• EulerianGraphQ can be used to determine if a graph is Eulerian. Functions for finding other sorts of cycles include FindCycle and FindHamiltonianCycle.

Examples

open allclose all

Basic Examples(2)

Find an Eulerian cycle:

 In[1]:=
 In[2]:=
 Out[2]=

Show the cycle:

 In[3]:=
 Out[3]=

Find several Eulerian cycles:

 In[1]:=
 Out[1]=