Conjectura
Beta.Proofs cannot be submitted yet. The corpus is open to read, and we are looking for researchers to maintain a subject area.Maintaining a field →
← problemsAX0002openMathematics/ Combinatorics

Ringel's Conjecture and Kotzig's Conjecture for large $n$

Maintainer — open

For all sufficiently large nn, the complete graph K2n+1K_{2n+1} decomposes into 2n+12n+1 edge-disjoint copies of any tree TT with nn edges. A "copy" of TT is the image T.map(fi)T.\text{map}(f_i) of TT under a vertex embedding fi:VFin(2n+1)f_i : V \hookrightarrow \text{Fin}(2n+1); the copies are pairwise edge-disjoint and together cover every edge of K2n+1K_{2n+1}. This follows from kotzig_conjecture_large; see `Pape

Motivation

For all sufficiently large nn, the complete graph K2n+1K_{2n+1} decomposes into 2n+12n+1 edge-disjoint copies of any tree TT with nn edges. A "copy" of TT is the image T.map(fi)T.\text{map}(f_i) of TT under a vertex embedding fi:VFin(2n+1)f_i : V \hookrightarrow \text{Fin}(2n+1); the copies are pairwise edge-disjoint and together cover every edge of K2n+1K_{2n+1}. This follows from kotzig_conjecture_large; see Paper/RingelConjecture.lean for the open form.

Recorded upstream as solved in the literature, but no Lean proof exists here yet. It is listed as open because nothing on this site is marked solved without a proof the kernel accepts — a known result needing formalization is a tractable task, and a good place to start.

Adapted from formal-conjectures, Arxiv/2001.02665/RingelConjecture.lean. Catalogued at https://arxiv.org/abs/2001.02665.

Lean API
import Mathlib.Combinatorics.SimpleGraph.Acyclic
import Mathlib.Order.CompletePartialOrder
import Mathlib.Order.Filter.AtTopBot.Defs

namespace Conjectura.AX0002

/-- For all sufficiently large $n$, the complete graph $K_{2n+1}$ decomposes into $2n+1$ edge-disjoint copies of any tree $T$ with $n$ edges. A "copy" of $T$ is the image $T.\text{map}(f_i)$ of $T$ under a vertex embedding $f_i : V \hookrightarrow \text{Fin}(2n+1)$; the copies are pairwise edge-disjoint and together cover every edge of $K_{2n+1}$. This follows from `kotzig_conjecture_large`; see `Paper/RingelConjecture.lean` for the open form. -/
def goal : Prop :=
  ∀ᶠ (n : ℕ) in Filter.atTop, ∀ {V : Type} [Finite V] (T : SimpleGraph V),
      T.IsTree → T.edgeSet.ncard = n →
      ∃ f : Fin (2 * n + 1) → (V ↪ Fin (2 * n + 1)),
        Pairwise (fun i j => Disjoint (T.map (f i)).edgeSet (T.map (f j)).edgeSet) ∧
        ⨆ i, T.map (f i) = (⊤ : SimpleGraph (Fin (2 * n + 1)))

end Conjectura.AX0002
Definition8
atTopFilter.atTop

def

FiniteFinite

class

IsTreeT.IsTree

structure

PairwisePairwise

inductive

DisjointDisjoint

def

mapT.map

def

edgeSetedgeSet

abbrev

Related work2
For your AI
Download as .md
I am proving a theorem in Lean 4 and submitting it to Conjectura.

## Problem AX0002 — Ringel's Conjecture and Kotzig's Conjecture for large $n$

For all sufficiently large $n$, the complete graph $K_{2n+1}$ decomposes into $2n+1$ edge-disjoint copies of any tree $T$ with $n$ edges. A "copy" of $T$ is the image $T.\text{map}(f_i)$ of $T$ under a vertex embedding $f_i : V \hookrightarrow \text{Fin}(2n+1)$; the copies are pairwise edge-disjoint and together cover every edge of $K_{2n+1}$. This follows from `kotzig_conjecture_large`; see `Pape

## Environment (fixed — do not assume anything newer)

- Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
- Mathlib: `v4.33.0-rc1`

If a lemma you want does not exist in that Mathlib, prove it inline instead of
importing something newer.

## The exact statement I must prove

```lean
theorem solution : Conjectura.AX0002.goal := by
  sorry
```

## The file I submit

```lean
import Conjectura.Problems.AX0002.Statement

namespace Submission

theorem solution : Conjectura.AX0002.goal := by
  sorry

end Submission

```

## The Lean definitions of every term in this problem

These are the actual definitions your proof will be checked against. Do not
substitute your own version of any of them.

### atTop

def

```lean
Filter.atTop
```
Defined in Mathlib.

### Finite

class

```lean
Finite
```
Defined in Mathlib.

### IsTree

structure

```lean
T.IsTree
```
Defined in Mathlib.

### ncard

def

```lean
T.edgeSet.ncard
```
Defined in Mathlib.

### Pairwise

inductive

```lean
Pairwise
```
Defined in Mathlib.

### Disjoint

def

```lean
Disjoint
```
Defined in Mathlib.

### map

def

```lean
T.map
```
Defined in Mathlib.

### edgeSet

abbrev

```lean
edgeSet
```
Defined in Mathlib.

## Rules — submissions violating these are rejected automatically

1. **Do not change the name or type of `solution`.** It must satisfy the
   statement above exactly.
2. **Do not redefine or shadow anything from the problem's Statement module.**
   Declaring your own `goal`, or redefining a name it depends on, produces a
   proof of a *different* statement and is rejected. This is the single most
   common rejection.
3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
   axiom `sorryAx` and is detected transitively through imports.
4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
   accepted, because it trusts compiled code rather than the kernel.
5. Only these axioms are permitted: `propext`, `Classical.choice`,
   `Quot.sound`.
6. Follow Mathlib style: hypotheses left of the colon, explicit types,
   `snake_case` theorem names, `UpperCamelCase` types.

## What I want from you

Here is my argument in informal mathematics:

> [PASTE YOUR PROOF SKETCH HERE]

Turn it into Lean 4 that compiles under the environment above and satisfies the
statement exactly. Where you are unsure a lemma exists in this Mathlib version,
say so explicitly rather than guessing a name.

Submissions are not open yet

Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.

The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.

The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.

Discussion

  • Nothing yet.

Sign in to take part.