OctoInformBeta

OpenAI preprint, September 2026 · §7. The induction · §7

Proposition 7.2: The edges of every graph on nn vertices split into at most Cφ(n)nC\varphi(n)n cycles and single edges, for one constant CC

A linear bound on the decomposition cost of graphs.

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

How few cycles and single edges does it take to partition the edges of a graph GG on nn vertices? Splitting into single edges takes |E(G)||E(G)| of them, of order n2n^2 when GG is dense, and Erdős and Gallai conjectured that O(n)O(n) always suffice. Proposition 7.2, the inductive bound of §7, bounds this number linearly in nn.

Cycle-and-edge Partitions

A cycle-or-edge set of a graph GG is a set of edges of GG that is either the edge set of a cycle of GG or consists of a single edge 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 such that E(G)=P1∪…∪Pk,Pi∩Pj=∅(i≠j).E(G) = P_1 \cup \dots \cup P_k, \qquad P_i \cap P_j = \emptyset \quad (i \ne j).(1)✦

The decomposition cost c(G)c(G) of a graph GG on a finite vertex set is the least kk for which GG has a cycle-and-edge partition into kk parts.✦

The induction factor is the real function φ\varphi given by φ(x)={1/2,x=1,max⁡{1/2,1−1/log⁡x},x≠1,\varphi(x) = \begin{cases} 1/2, & x = 1,\\ \max\bigl\{1/2,\ 1 - 1/\sqrt{\log x}\bigr\}, & x \ne 1, \end{cases}(2)✦ where log\log is the logarithm to base 22.

The Claim

Theorem 1. There is a constant C>0C > 0 such that every graph GG on nn vertices satisfies c(G)≤Cφ(n)n.c(G) \le C\,\varphi(n)\,n.(3)✦

In the paper, the result reads: there is an absolute constant CC such that every graph on n≥1n \ge 1 vertices has an edge partition into at most Cφ(n)nC\varphi(n)n cycles and single edges.

What Is Checked

The claim (3) is stated over all graphs on a finite vertex set, the empty vertex set included, with c(G)c(G) the least number of parts in a cycle-and-edge partition (1) of GG and φ\varphi the induction factor (2).