finds an Eulerian cycle in the graph g.


finds at most k Eulerian cycles.


uses rules vw to specify the graph g.


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.


open all close all

Basic Examples  (2)

Find an Eulerian cycle:

Click for copyable input
Click for copyable input

Show the cycle:

Click for copyable input

Find several Eulerian cycles:

Click for copyable input

Scope  (8)

Applications  (7)

Properties & Relations  (6)

Neat Examples  (1)

Introduced in 2010
Updated in 2015