##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 019.23602

**Autor: ** Erdös, Pál; Grünwald, T.; Vazsonyi, E.

**Title: ** Über Euler-Linien unendlicher Graphen. (On Eulerian lines in infinite Graphs.) (In German)

**Source: ** J. Math. Phys., Mass. Inst. Techn. 17, 59-75 (1938).

**Review: ** *König* (Theorie der Graphen p. 31) posed the problem: When does a denumerably infinite graph G contain an Euler line (a chain Z extending infinitely in both directions and containing each edge of G exactly once)? The authors obtain these necessary and sufficient conditions: (T_{1}) G is connected; (T_{2}), G contains no vertex of odd order; (E_{1}) If g is any finite subgraph of G, G-g has at most two infinite components; (E_{2}) If all vertices of a finite g have in g the same, even, order, then G-g has only one infinite component. Necessary and sufficient that G contain an Euler line infinite in one direction are the conditions: (T_{1}); (T^*), G contains a vertex of either infinite or odd order, and at most one vertex of odd order; (E) each G-g with g finite has at most one infinite component. The proof that these sets of conditions are sufficient depends in each case on removing a finite chain z containing a specified edge, adding to z all finite components C_{i} of G-z, applying the known finite methods to g' = z+**sum** C_{i}, and finally showing that the remainting portions of G can be suitably attached to the Euler line of g' in virtue of the essential conditions (E). For this argument it suffices to assume weakened forms of (E_{i}) in which the finite g is only a chain or circuit containing a fixed vertex.

Applications: the existence of an Euler line for the lattice of n-space, conditions for the existence of a finite number of lines covering G; and the theorem that G has a Z containing each edge exactly twice if and only if (T_{1}) and (E) hold.

**Reviewer: ** MacLane (Cambridge, Mass.)

**Classif.: ** * 05C99 Graph theory

**Index Words: ** Topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag