OctoInformBeta

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

Theorem 2.1: Lov'asz’s theorem: for a graph on nn vertices, n′n' of them non-isolated, the number kk of parts can be taken with 2k≤n′2k \le n'

The edges of any graph split into few paths and cycles.

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 on nn vertices, with edge set E(G)E(G). Its edges can be split into paths and cycles, each edge in exactly one part, and the question is how few parts such a split needs as a function of nn. Lovász’s theorem answers it.

Pieces and Partitions

A piece of GG is a path of positive length in GG or a cycle in GG; for a piece PP, E(P)E(P) is its set of edges.✦ A path-or-cycle set of GG is a set of edges of GG that is the edge set E(P)E(P) of a piece PP of GG.✦

A path-cycle partition of GG with kk parts is a family of kk pairwise disjoint path-or-cycle sets E1,…,EkE_1, \dots, E_k of GG whose union is the edge set of GG: E(G)=E1⊔E2⊔…⊔Ek.E(G) = E_1 \sqcup E_2 \sqcup \dots \sqcup E_k .(1)

A decomposition of GG into kk pieces is a family of kk pieces P1,…,PkP_1, \dots, P_k of GG, no two of which share an edge, whose edge sets together make up E(G)E(G): E(G)=E(P1)⊔E(P2)⊔…⊔E(Pk).E(G) = E(P_1) \sqcup E(P_2) \sqcup \dots \sqcup E(P_k) .(2)

The non-isolated vertices of GG are those that lie on an edge of GG, and n′(G)n'(G) denotes their number.✦

The Claim

Theorem 1 (Lovász).

  1. Every graph GG on nn vertices has a path-cycle partition whose number kk of parts satisfies 2k≤n.2k \le n .(3)✦

  2. Let n≥0n \ge 0 be an integer and GG a graph with vertex set [n]={1,…,n}[n] = \{1, \dots, n\}. Then GG has a path-cycle partition whose number kk of parts satisfies 2k≤n.2k \le n .(4)✦

  3. Every graph GG has a decomposition into kk pieces whose number kk satisfies 2k≤n′(G).2k \le n'(G) .(5)✦

In the paper, the result reads: the edges of a finite simple graph on nn vertices can be partitioned into at most ⌊n/2⌋\lfloor n/2 \rfloor paths and cycles.

For an integer kk, the bound 2k≤n2k \le n of (3) and (4) is the bound k≤⌊n/2⌋k \le \lfloor n/2 \rfloor.

What Is Checked

The claims (3) and (4) are stated over graphs and their path-cycle partitions, the second for graphs with vertex set [n][n] for every n≥0n \ge 0, and (5) over decompositions into pieces and the number n′(G)n'(G) of non-isolated vertices.