OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Cycle-and-edge partitions: Each part is the edge set of a cycle or a single edge, and the decomposition cost is the least number of parts

Cycle-and-edge partitions and the decomposition cost of a graph.

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

Take a simple graph GG on a finite vertex set, with edge set E(G)E(G). Its edges can be shared out among cycles and single edges of GG so that every edge is used exactly once, if only by taking each edge on its own; the question is how few cycles and edges suffice. Erdős and Gallai conjectured that for a graph on nn vertices, O(n)O(n) of them always suffice.

A cycle CC of GG is a closed walk in GG of length at least 33 that passes through no vertex twice except that it ends where it starts; its edge set E(C)E(C) is the set of edges it traverses.

The Claim

Definition 1. Let GG be a graph. A part SS of GG is a set of edges of GG that is the edge set of a cycle of GG or consists of a single edge of GG: S=E(C) for a cycle C of GorS={e} for an edge e∈E(G).S = E(C) \text{ for a cycle } C \text{ of } G \qquad\text{or}\qquad S = \{e\} \text{ for an edge } e \in E(G).(1)✦ For an integer k≥0k \ge 0, a cycle-and-edge partition of GG into kk parts is a sequence S0,…,Sk−1S_0, \dots, S_{k-1} of pairwise disjoint parts of GG whose union is E(G)E(G).✦ The decomposition cost c(G)c(G) of GG is the least kk for which GG has a cycle-and-edge partition into kk parts✦. E(G)=S0∪S1∪…∪Sc(G)−1.E(G) = S_0 \cup S_1 \cup \dots \cup S_{c(G)-1}.(2)✦

In the paper, the definition reads: a partition of E(G)E(G) into parts, each the edge set of a simple cycle or a single edge, where parts may share vertices but not edges.

What Is Checked

The parts in (1) and the cycle-and-edge partitions are defined for a simple graph GG on any vertex set, and the decomposition cost and (2) for a simple graph on a finite vertex set.