OctoInformBeta

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

Corollary 2.2: The edges of a graph on nn vertices partition into at most nn paths, each vertex an end of at most two of them

Every graph splits into paths with endpoint load two.

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 finite simple graph with vertex set VV, and let n=|V|n = |V|. The edge set E(G)E(G) always splits into paths, for instance into its single edges, and then a vertex of degree dd is an end of dd of the paths. The question is whether E(G)E(G) can be partitioned into paths so that no vertex is an end of more than two of them, with at most nn paths in all.

Paths and Endpoint Load

A path PP of positive length in GG is a sequence v0v1…vmv_0 v_1 \dots v_m of distinct vertices of GG with m≥1m \ge 1 and vj−1vj∈E(G)v_{j-1} v_j \in E(G) for 1≤j≤m1 \le j \le m; its ends are v0v_0 and vmv_m, and its edge set is E(P)={vj−1vj:1≤j≤m}E(P) = \{v_{j-1} v_j : 1 \le j \le m\}.✦

For paths P1,…,PkP_1, \dots, P_k in GG, the endpoint load of a vertex vv of GG is the number of indices ii for which vv is an end of PiP_i: λ(v)=|{i∈{1,…,k}:v is an end of Pi}|.\lambda(v) = \bigl|\{\, i \in \{1, \dots, k\} : v \text{ is an end of } P_i \,\}\bigr|.(1)

An endpoint path partition of GG is a family P1,…,PkP_1, \dots, P_k of paths of positive length in GG with E(G)=E(P1)⊔…⊔E(Pk),λ(v)≤2 for every v∈V,k≤|V|.E(G) = E(P_1) \sqcup \dots \sqcup E(P_k), \qquad \lambda(v) \le 2 \ \text{ for every } v \in V, \qquad k \le |V|.(2)✦ Write 𝒫2(G)\mathcal{P}_2(G) for the set of endpoint path partitions of GG.

The Claim

Theorem 1 (Corollary 2.2). Let GG be a finite simple graph. Then 𝒫2(G)≠∅.\mathcal{P}_2(G) \neq \emptyset.(3)✦ In particular, for every n≥0n \ge 0 and every graph GG on the vertex set {0,1,…,n−1}\{0, 1, \dots, n-1\}, 𝒫2(G)≠∅.\mathcal{P}_2(G) \neq \emptyset.(4)✦

What Is Checked

The claim (3) is stated over a finite simple graph, the paths of positive length in it, the endpoint load (1) of a family of such paths and the endpoint path partitions (2) built from them; (4) is stated over the graphs on the vertex sets {0,1,…,n−1}\{0, 1, \dots, n-1\}, n≥0n \ge 0.