Eulerian Graph

An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with , 2, ... vertices are 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736), the first few of which are illustrated above.

The corresponding numbers of connected Eulerian graphs are 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS A003049; Robinson 1969; Liskovec 1972; Harary and Palmer 1973a, p. 117), the first few of which are illustrated above.

Some care is needed in interpreting the term, however, since some authors define an Euler graph as a different object, namely a graph for which all vertices are of even vertex degree (motivated by the following theorem). Euler showed (without proof) that a connected simple graph is Eulerian iff it has no graph vertices of odd vertex degree (i.e., all vertices are of even vertex degree). While the number of connected Euler graphs on vertices is equal to the number of connected Eulerian graphs on vertices, the counts are different for disconnected graphs since there exist disconnected graphs having multiple disjoint cycles with each graph vertex of even vertex degree but for which no single Eulerian cycle passes through all edges.

A graph can be tested in the Wolfram Language to see if it is Eulerian using the command EulerianGraphQ[g].

A graph is Eulerian iff its edge set can be decomposed into cycles (Veblen 1916, p. 15; Fleischner 1990; Gross and Yellen 2006, p. 195; Heinrich and Streicher 2019). Determining whether an Eulerian graph can be decomposed into at most cycles is NP-complete (Péroche 1984, Heinrich and Streicher 2019). Finding the largest subgraph of a graph having an odd number of vertices which is Eulerian is also an NP-complete problem (Skiena 1990, p. 194).

Determining the number of Eulerian cycles in an undirected graph is #P-complete.

The following table gives some named Eulerian graphs.

graph
singleton graph	1
triangle graph	3
square graph	4
pentatope graph	5
octahedral graph	6
16-cell graph	8
cuboctahedral graph	12
Chvátal graph	12
tesseract graph	16
Hoffman graph	16
Robertson graph	19
Folkman graph	20
24-cell graph	24
small rhombicuboctahedral graph	24
25-Grünbaum graph	25
Doyle graph	27
icosidodecahedral graph	30
Harborth graph	52
Gewirtz graph	56
small rhombicosidodecahedral graph	60
Meredith graph	70
600-cell graph	120
McLaughlin graph	275
120-cell graph	600

A planar bipartite graph is dual to a planar Eulerian graph and vice versa. The directed analogue of an Eulerian graph is an Eulerian digraph.