An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with 
, 2, ... nodes 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 1973, 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 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 degree
(i.e., all vertices are of even degree). 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.
A graph can be tested in the Wolfram Language to see if it 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; Heinrich and Streicher 2019; Gross
and Yellen 2006, p. 195). Determining whether an Eulerian graph can be decomposed
into at most 
cycles is NP-complete (Péron 1984,
Heinrich and Streicher 2017). Finding the largest subgraph
of 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.
A directed graph is Eulerian iff every graph vertex has equal indegree
and outdegree. A planar bipartite
graph is dual to a planar
Eulerian graph and vice versa. The numbers of Eulerian digraphs on 
, 2, ... nodes are 1, 1, 3, 12, 90, 2162, ... (OEIS A058337).
