The Setting
Let be a graph, and let be a quotient graph whose vertices stand for pairwise vertex-disjoint paths of : a vertex of stands for a path of that starts at a vertex and ends at a vertex . Along a cycle of , each vertex is followed by a vertex , and may contain the edge from the end of the one path to the start of the next. When contains all of these joining edges, the question is whether they form, together with the edges of the paths, the edge set of a cycle of .
The Claim
Theorem 1. Let and be graphs. To each vertex of attach two vertices and of and a walk in from to . Let be a cycle of , and put . Suppose that is an edge of for , and that are pairwise vertex-disjoint, each a path or a single vertex. Then has a cycle with (1)✦
What Is Checked
The claim (1) is stated over a graph , an arbitrary graph , two maps and from the vertices of to those of with a walk in from to for every vertex of , and a cycle of along which each is adjacent in to and the walks are pairwise vertex-disjoint paths.