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: (T1) G is connected; (T2), G contains no vertex of odd order; (E1) If g is any finite subgraph of G, G-g has at most two infinite components; (E2) 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: (T1); (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 Ci of G-z, applying the known finite methods to g' = z+sum Ci, 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 (Ei) 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 (T1) and (E) hold.
Reviewer: MacLane (Cambridge, Mass.)
Classif.: * 05C99 Graph theory
Index Words: Topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag