Worked solution: A rainbow-tree proof of Ringel's conjecture (2020)

Step 8 of 8: Closing the loop: Ringel's conjecture holds for large

n

Previous step Next step

In plain words

With Theorem 2.1 established, the very first idea from Step 2 -- Kotzig's cyclic-shift trick -- finishes the whole proof in one line: take the guaranteed rainbow copy of $T$ , spin it around the $2n+1$ positions of the circle, and the $2n+1$ rotated copies automatically use every edge of $K_{2n+1}$ exactly once. What began as an old, elegant conjecture about trees and complete graphs is settled by combining a purely combinatorial colouring trick with heavy modern machinery (randomised embeddings and absorption) built to guarantee that one essential rainbow copy always exists.

K_{2n+1} \text{ decomposes into } 2n+1 \text{ edge-disjoint copies of any tree } T \text{ with } n \text{ edges}

Detailed analysis

Combining Theorem 2.1 (Step 7) with Kotzig's cyclic-shift observation (Step 2): for sufficiently large $n$ , the ND-coloured $K_{2n+1}$ contains a rainbow copy $\hat{T}$ of any given $n$ -edge tree $T$ , and its $2n+1$ cyclic shifts $\hat{T}_0,\ldots,\hat{T}_{2n}$ are pairwise edge-disjoint (since a shift only maps edges to other edges of the same colour, and $\hat{T}$ uses each colour once) and together cover all $n(2n+1)$ edges of $K_{2n+1}$ . This proves Theorem 1.2: $K_{2n+1}$ decomposes into $2n+1$ copies of $T$ for every sufficiently large $n$ , confirming Ringel's 1963 conjecture; the same argument simultaneously proves Kotzig's related conjecture about rainbow copies in the ND-colouring, and gives the first decomposition result for complete graphs into arbitrary-degree spanning-scale subgraphs, free of the bounded-degree restriction that limited all earlier approaches.

Knowledge used in this step

Graphs, degree, and paths