OctoInformBeta

OpenAI preprint, September 2026 · Steps of the proof with no numbered result

Lifting a cycle of the quotient: If its vertices stand for vertex-disjoint paths of GG joined end to start by edges, the paths and these edges form a cycle

When a cycle of a quotient graph lifts to GG..

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let GG be a graph, and let QQ be a quotient graph whose vertices stand for pairwise vertex-disjoint paths of GG: a vertex zz of QQ stands for a path PzP_z of GG that starts at a vertex s(z)s(z) and ends at a vertex t(z)t(z). Along a cycle of QQ, each vertex zz is followed by a vertex ww, and GG may contain the edge t(z)s(w)t(z)s(w) from the end of the one path to the start of the next. When GG 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 GG.

The Claim

Theorem 1. Let GG and QQ be graphs. To each vertex zz of QQ attach two vertices s(z)s(z) and t(z)t(z) of GG and a walk PzP_z in GG from s(z)s(z) to t(z)t(z). Let z1z2⋯zkz1z_1 z_2 \cdots z_k z_1 be a cycle of QQ, and put zk+1=z1z_{k+1} = z_1. Suppose that t(zi)s(zi+1)t(z_i)s(z_{i+1}) is an edge of GG for 1≤i≤k1 \le i \le k, and that Pz1,…,PzkP_{z_1}, \dots, P_{z_k} are pairwise vertex-disjoint, each a path or a single vertex. Then GG has a cycle CC with E(C)={t(zi)s(zi+1):1≤i≤k}∪⋃i=1kE(Pzi).E(C) = \{\, t(z_i)s(z_{i+1}) : 1 \le i \le k \,\} \cup \bigcup_{i=1}^{k} E(P_{z_i}).(1)✦

What Is Checked

The claim (1) is stated over a graph GG, an arbitrary graph QQ, two maps ss and tt from the vertices of QQ to those of GG with a walk PzP_z in GG from s(z)s(z) to t(z)t(z) for every vertex zz of QQ, and a cycle z1z2⋯zkz1z_1 z_2 \cdots z_k z_1 of QQ along which each t(zi)t(z_i) is adjacent in GG to s(zi+1)s(z_{i+1}) and the walks PziP_{z_i} are pairwise vertex-disjoint paths.