OctoInformBeta

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

Theorem 1.1: The edge set of a simple graph on nn vertices partitions into at most CnCn cycles and single edges, for one absolute constant CC

Every graph splits into linearly many cycles and single edges.

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 simple graph on nn vertices with edge set E(G)E(G). The question is how few parts suffice to partition E(G)E(G) into edge sets of cycles and single edges. Taking each edge as a part gives |E(G)||E(G)| parts, of order n2n^2 when GG is dense; the Erdős-Gallai conjecture asserts that a number of parts linear in nn always suffices, with a constant that does not depend on GG.✦

Cycles and Partitions

A cycle of GG is a closed walk v0v1⋯vℓv_0 v_1 \cdots v_\ell in GG with vℓ=v0v_\ell = v_0 and ℓ≥3\ell \ge 3 whose vertices v0,…,vℓ−1v_0, \dots, v_{\ell-1} are distinct; its edge set is {v0v1,v1v2,…,vℓ−1vℓ}\{v_0 v_1, v_1 v_2, \dots, v_{\ell-1} v_\ell\}. A cycle-or-edge set of GG is a set of edges of GG that is either the edge set of a cycle of GG or {e}\{e\} for a single edge ee of GG.✦

A cycle-and-edge partition of GG into kk parts is a sequence P1,…,PkP_1, \dots, P_k of cycle-or-edge sets of GG with E(G)=P1∪P2∪⋯∪Pk,Pi∩Pj=∅(i≠j).E(G) = P_1 \cup P_2 \cup \cdots \cup P_k, \qquad P_i \cap P_j = \emptyset \quad (i \ne j).(1)✦

The Claim

Theorem 1. There is a constant C>0C > 0 such that, for every integer n≥0n \ge 0, every simple graph GG on the vertex set {0,1,…,n−1}\{0, 1, \dots, n-1\} has a cycle-and-edge partition into kk parts with k≤Cn.k \le Cn.(2)✦

In the paper, the result reads: there is an absolute constant C>0C > 0 such that, for every finite simple undirected graph GG with nn vertices, E(G)E(G) has a partition into at most CnCn parts, each of which is the edge set of a cycle or consists of a single edge.

What Is Checked

The claim (2) is stated over simple graphs on {0,1,…,n−1}\{0, 1, \dots, n-1\} for every n≥0n \ge 0, and over their cycle-and-edge partitions (1), whose parts are edge sets of cycles and single edges.