for processing trees that rely on an Euler tour of the tree (where each edge is treated as a pair of arcs). The de Bruijn sequences can be constructed as Eulerian trails of de Bruijn graphs. In infinite graphs In an infinite graph, the corresponding concept to an Eulerian trail or Eulerian cycle is an Eulerian line, a doubly-infinite trail that covers all of the edges of the graph. It is not sufficient for the existence of such a trail that the graph be connected and that all vertex degrees be even; for instance, the infinite Cayley graph shown, with all vertex degrees equal to four, has no Eulerian line. The infinite graphs that contain Eulerian lines were characterized by . For an infinite graph or multigraph to have an Eulerian line, it is necessary and sufficient that all of the following conditions be met: is connected. has countable sets of vertices and edges. has no vertices of (finite) odd degree. Removing any finite subgraph from leaves at most two infinite connected components in the remaining graph, and if has even degree at each of its vertices then removing leaves exactly one infinite connected component. Undirected Eulerian graphs Euler stated a necessary condition for a finite graph to be Eulerian as all vertices must have even degree. Hierholzer proved this is a sufficient condition in a paper published in 1873. This leads to the following necessary and sufficient statement for what a finite graph must have to be Eulerian: An undirected connected finite graph is Eulerian if and only if every vertex of G has even degree. The following result was proved by Veblen in 1912: An undirected connected graph is Eulerian if and only if it is the disjoint union of some cycles.Hierholzer developed a linear time algorithm for constructing an Eulerian tour in an undirected graph. Directed Eulerian graphs It is possible to have a directed graph that has all even degrees but is not Eulerian. This means that even degrees is not a sufficient condition for a digraph to be Eulerian. König proved that a digraph must also have the same number of arcs entering and leaving each vertex to be Eulerian. In other words, the directed graph must be symmetric. A directed and strongly connected graph is Eulerian if and only if every vertex of G is symmetric. Hierholzer's linear time algorithm for constructing an Eulerian