FindEulerianCycle

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: