1. The characterization of infinite Eulerian graphs, a short and computable proof
- Author
-
Carrasco-Vargas, Nicanor
- Subjects
FOS: Computer and information sciences ,05C63, 05C45, 68R10, 03D99, 68Q01 ,Information Theory (cs.IT) ,Computer Science - Information Theory ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Group Theory (math.GR) ,Mathematics - Logic ,Logic (math.LO) ,Mathematics - Group Theory - Abstract
In this paper we present a short proof of a theorem by Erd\H{o}s, Gr\"unwald and Weiszfeld on the characterization of infinite graphs which admit infinite Eulerian trails. In addition, we extend this result with a characterization of which finite trails can be extended to infinite Eulerian trails. Our proof is computable and yields an effective version of this theorem. This exhibits stark contrast with other classical results in the theory of infinite graphs which are not effective., Comment: 13 pages
- Published
- 2023