OctoInformBeta

OpenAI preprint, September 2026 · §2. Conventions and preliminary results · §2

Pieces carrying assigned edges, and graph partitions: Graphs supported on a vertex set, pieces built from them, and lists of graphs carrying each edge of GG once and nothing else

Pieces on vertex sets and edge partitions 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

Let GG be a graph on a finite vertex set VV. A cycle-and-edge partition of GG is a partition of E(G)E(G) into parts, each the edge set of a cycle of GG or a single edge of GG, and the decomposition cost of GG is the least number of parts of such a partition. Such a partition can be assembled from partitions of smaller graphs H1,…,HkH_1, \dots, H_k among which the edges of GG are shared out, each HiH_i sitting on a vertex set of its own: the parts of the partitions of the HiH_i, taken together, form a cycle-and-edge partition of GG.

The library defines when a graph is supported on a vertex set, what a piece is, and when a sequence of graphs partitions GG.

Edge Multiplicity in a Sequence of Graphs

The edge multiplicity mℒ(x,y)m_{\mathcal{L}}(x, y) of a pair of vertices x,yx, y in a finite sequence ℒ=(H1,…,Hk)\mathcal{L} = (H_1, \dots, H_k) of graphs on VV is the number of indices ii for which xyxy is an edge of HiH_i: mℒ(x,y)=|{i∈{1,…,k}:xy∈E(Hi)}|.m_{\mathcal{L}}(x, y) = \bigl|\{\, i \in \{1, \dots, k\} : xy \in E(H_i) \,\}\bigr|.(1)✦

The Definition

Definition 1. Let VV be a vertex set.

A graph HH on VV is supported on a finite set A⊆VA \subseteq V when both ends of every edge of HH lie in AA: x∈Aandy∈Afor every edge xy∈E(H).x \in A \ \text{and}\ y \in A \qquad \text{for every edge } xy \in E(H).(2)✦

A piece on VV is a pair P=(A,H)P = (A, H) of a finite set A⊆VA \subseteq V, the vertex set of PP, and a graph HH on VV supported on AA: $$P = (A, H), \qquad A \subseteq V \text{ finite}, \qquad H \text{ satisfies \eqref{eq:claim1}}.$$(3)✦

A finite sequence ℒ=(H1,…,Hk)\mathcal{L} = (H_1, \dots, H_k) of graphs on VV partitions a graph GG on VV when every pair of vertices x,yx, y has edge multiplicity one in ℒ\mathcal{L} if xyxy is an edge of GG, and zero otherwise: mℒ(x,y)={1if xy∈E(G),0otherwise,for all x,y∈V.m_{\mathcal{L}}(x, y) = \begin{cases} 1 & \text{if } xy \in E(G), \\ 0 & \text{otherwise}, \end{cases} \qquad \text{for all } x, y \in V.(4)✦

In the paper, the definition reads: a family of subgraphs H1,…,HkH_1, \dots, H_k of GG partitions GG when the edge sets assigned to them are pairwise disjoint with union E(G)E(G), each HiH_i carries only its assigned edges, and their vertex sets may overlap.

What Is Checked

The definitions (2), (3) and (4) are stated over graphs on a vertex set VV, finite subsets of VV and finite sequences of graphs on VV, the last through the edge multiplicity (1).