we-solve (beta)

Math-2208 · mathematics · Graph theory

Decomposing an eulerian graph into cycles.

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles.

Formulation references: [S1], [S2], [S3].

Short English statement

Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2208-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2208

Linear cycle-and-edge decomposition: The Eulerian corollary supplies at most C n cycles. The specified sharp (n-1)/2 coefficient is not established for all Eulerian graphs.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Decomposing an eulerian graph into cycles.

OpenAI's claim

Linear cycle-and-edge decomposition: Every finite simple graph on $n$ vertices is claimed to have its edges partitioned using no more than $Cn$ pieces, each either a simple cycle or a single edge. The constant is the same for all graph orders.

Mathematical statement of the claimed result

Mathematical claim 1.
There is an absolute $C>0$ such that every finite simple undirected $n$-vertex graph admits an edge partition into at most $Cn$ pieces, each a single edge or the edge set of a cycle. For an Eulerian graph the corollary gives at most $Cn$ cycles alone. It further claims that, for every fixed $\delta,p>0$, some $\epsilon,n_0$ make the sharper \[\text{number of cycles}\le\Delta(G)/2+\delta n\] possible for Eulerian $G$ whenever $n\ge n_0$ and every bipartition $A\mathbin{\dot\cup}B=V(G)$ with $|A|,|B|\ge\epsilon n$ has $e_G(A,B)\ge p|A||B|$. The unconditional claim remains a linear bound with an unspecified constant. Eulerian means that every vertex has even degree; connectivity is unnecessary.

Outline of the argument

Linear cycle-and-edge decomposition: Long cycles are removed across a sequence of decreasing scales and the residue is assigned to overlapping boxes with controlled total order. Expanding pieces are extracted within the boxes. A carefully chosen layer pays for a whole prefix of scales, while reserved routing edges and small residual graphs keep the total decomposition cost linear.

Formal verification

Family 181 describes Lean coverage for a uniformly linear number of cycles and singleton edges in an edge partition.

Linear cycle-and-edge decomposition: The manuscript links CycleDecomposition.lean (declaration OAI.ErdosGallai.erdos_gallai).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →