Perfect path double covers in every simple graph

Abstract

Abstract We prove in this paper that every simple graph G admits a perfect path double cover (PPDC), i.e., a set of paths of G such that each edge of G belongs to exactly two of the paths and each vertex of G is an end of exactly two of the paths, where a path of length zero is considered to have (identical) ends. This was conjectured by A. Bondy in 1988.