/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilAlspach's conjecture on cycle decompositions of complete graphs (1981; proved 2014)
References:
[Al81] Alspach, B. (1981). "Research problems, Problem 3." Discrete Math. 36, p. 333.
[BHP14] Bryant, D., Horsley, D. and Pettersson, W. (2014). "Cycle decompositions V: Complete graphs into cycles of arbitrary lengths." Proc. London Math. Soc. 108, pp. 1153--1192. arXiv:1204.3709
[GJKKO21] Glock, S., Joos, F., Kim, J., Kühn, D. and Osthus, D. (2021). "Resolution of the Oberwolfach problem." J. Eur. Math. Soc. 23, pp. 2511--2547. arXiv:1806.04644
@[expose] public sectionopen SimpleGraph Finsetnamespace AlspachConjecturevariable {V : Type*} [Fintype V] [DecidableEq V]open Classical in
A multiset of cycles C is a cycle decomposition of G if every edge of G lies on
exactly one of the cycles.
def IsCycleDecomposition (G : SimpleGraph V) [DecidableRel G.Adj] (C : Multiset (Cycle G)) :
Prop :=
∀ e ∈ G.edgeFinset, (C.filter fun c => e ∈ c.edges).card = 1The multiset of cycle lengths of a family of cycles.
def lengths {G : SimpleGraph V} (C : Multiset (Cycle G)) : Multiset ℕ :=
C.map SimpleGraph.Cycle.lengthAlspach's conjecture (1981), proved by Bryant, Horsley and Pettersson (2014).
Let $n$ be odd and let $m_1, \dots, m_t$ be integers with $3 \le m_i \le n$ and $m_1 + \dots + m_t = \binom{n}{2}$. Then the complete graph $K_n$ decomposes into cycles of lengths $m_1, \dots, m_t$. (These conditions are clearly necessary: $K_n$ has all degrees even only for odd $n$, and its edges must be split exactly among the cycles.)
@[category research solved, AMS 5]
theorem alspach_conjecture :
∀ (n : ℕ), Odd n → ∀ m : Multiset ℕ, (∀ x ∈ m, 3 ≤ x ∧ x ≤ n) → m.sum = n.choose 2 →
∃ C : Multiset (Cycle (completeGraph (Fin n))),
IsCycleDecomposition (completeGraph (Fin n)) C ∧ lengths C = m := ⊢ ∀ (n : ℕ),
Odd n →
∀ (m : Multiset ℕ),
(∀ x ∈ m, 3 ≤ x ∧ x ≤ n) →
m.sum = n.choose 2 → ∃ C, IsCycleDecomposition (completeGraph (Fin n)) C ∧ lengths C = m
All goals completed! 🐙open Classical inThe even case (Bryant–Horsley–Pettersson 2014).
For even $n$, the complete graph minus a perfect matching, $K_n - I$, decomposes into cycles of
lengths $m_1, \dots, m_t$ whenever $3 \le m_i \le n$ and $\sum m_i = \binom{n}{2} - n/2$.
Since Mathlib has no canonical perfect matching of $K_n$, we state this for any perfect
matching I.
Reference: [BHP14].
@[category research solved, AMS 5]
theorem alspach_conjecture.variants.even (n : ℕ) (hn : Even n)
(I : (completeGraph (Fin n)).Subgraph) (hI : I.IsPerfectMatching)
(m : Multiset ℕ) (hm : ∀ x ∈ m, 3 ≤ x ∧ x ≤ n) (hsum : m.sum = n.choose 2 - n / 2) :
∃ C : Multiset (Cycle (completeGraph (Fin n) \ I.spanningCoe)),
IsCycleDecomposition (completeGraph (Fin n) \ I.spanningCoe) C ∧ lengths C = m := n:ℕhn:Even nI:(completeGraph (Fin n)).SubgraphhI:I.IsPerfectMatchingm:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ nhsum:m.sum = n.choose 2 - n / 2⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin n) \ I.spanningCoe) C ∧ lengths C = m
All goals completed! 🐙A long-cycle corollary of the Alspach theorem (Bryant–Horsley–Pettersson 2014).
For odd $n$, the conjecture holds whenever all the prescribed lengths $m_i$ are at least $\lceil(n+4)/2\rceil$. This follows from [BHP14, Theorem 1].
@[category research solved, AMS 5]
theorem alspach_conjecture.variants.long_cycles (n : ℕ) (hn : Odd n) (m : Multiset ℕ)
(hm : ∀ x ∈ m, (n + 5) / 2 ≤ x ∧ x ≤ n) (hsum : m.sum = n.choose 2) :
∃ C : Multiset (Cycle (completeGraph (Fin n))),
IsCycleDecomposition (completeGraph (Fin n)) C ∧ lengths C = m := n:ℕhn:Odd nm:Multiset ℕhm:∀ x ∈ m, (n + 5) / 2 ≤ x ∧ x ≤ nhsum:m.sum = n.choose 2⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin n)) C ∧ lengths C = m
All goals completed! 🐙The empty family decomposes an edgeless graph.
@[category API, AMS 5]
lemma isCycleDecomposition_zero {G : SimpleGraph V} [DecidableRel G.Adj]
(h : G.edgeFinset = ∅) : IsCycleDecomposition G 0 :=
fun e he => V:Type u_1inst✝²:Fintype Vinst✝¹:DecidableEq VG:SimpleGraph Vinst✝:DecidableRel G.Adjh:G.edgeFinset = ∅e:Sym2 Vhe:e ∈ G.edgeFinset⊢ (Multiset.filter (fun c ↦ e ∈ c.edges) 0).card = 1 All goals completed! 🐙The case $n = 1$.
$K_1$ has no edges, so the only admissible multiset of lengths is empty and the empty decomposition works.
m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 1hsum:m.sum = Nat.choose 1 2hm0:m = 0⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 1)) C ∧ lengths C = m
subst hm0 hm:∀ x ∈ 0, 3 ≤ x ∧ x ≤ 1hsum:Multiset.sum 0 = Nat.choose 1 2⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 1)) C ∧ lengths C = 0
refine ⟨0, isCycleDecomposition_zero ?_, Multiset.map_zero _⟩ hm:∀ x ∈ 0, 3 ≤ x ∧ x ≤ 1hsum:Multiset.sum 0 = Nat.choose 1 2⊢ (completeGraph (Fin 1)).edgeFinset = ∅
decide All goals completed! 🐙
The triangle 0 → 1 → 2 → 0 as a cycle of K₃.
def triangle : Cycle (completeGraph (Fin 3)) where
base := 0
walk := Walk.cons (by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (completeGraph (Fin 3)).Adj 0 1 decide All goals completed! 🐙 : (completeGraph (Fin 3)).Adj 0 1)
(Walk.cons (by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (completeGraph (Fin 3)).Adj 1 2 decide All goals completed! 🐙 : (completeGraph (Fin 3)).Adj 1 2)
(Walk.cons (by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (completeGraph (Fin 3)).Adj 2 0 decide All goals completed! 🐙 : (completeGraph (Fin 3)).Adj 2 0) Walk.nil))
isCycle := by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).IsCycle
rw [Walk.isCycle_def, V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).IsTrail ∧
Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil ∧
(Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).edges.Nodup ∧
Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil ∧
(Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup Walk.isTrail_def V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).edges.Nodup ∧
Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil ∧
(Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).edges.Nodup ∧
Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil ∧
(Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup] V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).edges.Nodup ∧
Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil ∧
(Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup
exact ⟨by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).edges.Nodup decide All goals completed! 🐙, by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil)) ≠ Walk.nil simp All goals completed! 🐙, by V:Type u_1inst✝¹:Fintype Vinst✝:DecidableEq V⊢ (Walk.cons ⋯ (Walk.cons ⋯ (Walk.cons ⋯ Walk.nil))).support.tail.Nodup decide All goals completed! 🐙⟩The case $n = 3$.
$K_3$ has three edges, so the only admissible multiset of lengths is ${3}$, realised by the triangle itself.
@[category test, AMS 5]
theorem alspach_conjecture.variants.three (m : Multiset ℕ) (hm : ∀ x ∈ m, 3 ≤ x ∧ x ≤ 3)
(hsum : m.sum = Nat.choose 3 2) :
∃ C : Multiset (Cycle (completeGraph (Fin 3))),
IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m := by m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m
-- Every element of `m` is `3`, and the sum is `3`, so `m = {3}`.
have hm3 : m = Multiset.replicate m.card 3 := by
rw [Multiset.eq_replicate m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2⊢ m.card = m.card ∧ ∀ b ∈ m, b = 3 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2⊢ m.card = m.card ∧ ∀ b ∈ m, b = 3 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m] m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2⊢ m.card = m.card ∧ ∀ b ∈ m, b = 3 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m; exact ⟨rfl, fun x hx => le_antisymm (hm x hx).2 (hm x hx).1⟩ m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m
have hcard : m.card = 1 := by
have := hsum m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.sum = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m; rw [hm3, m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:(Multiset.replicate m.card 3).sum = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card * 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m Multiset.sum_replicate, m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card • 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card * 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m smul_eq_mul m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card * 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card * 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m] at this m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card * 3 = Nat.choose 3 2⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m; simp at this m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3this:m.card = 1⊢ m.card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m; omega m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = m
rw [hm3, m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = Multiset.replicate m.card 3 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = {3} hcard, m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = Multiset.replicate 1 3 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = {3} Multiset.replicate_one m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = {3} m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = {3}] m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ ∃ C, IsCycleDecomposition (completeGraph (Fin 3)) C ∧ lengths C = {3}
refine ⟨{triangle}, fun e he => ?_, by m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ lengths {triangle} = {3} simp [lengths, triangle] m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1⊢ { base := 0, walk := Walk.cons triangle._proof_2 (Walk.cons triangle._proof_3 (Walk.cons triangle._proof_4 Walk.nil)),
isCycle := triangle._proof_5 }.length =
3; decide All goals completed! 🐙⟩
rw [Multiset.filter_singleton m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinset⊢ (if e ∈ triangle.edges then {triangle} else ∅).card = 1 m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinset⊢ (if e ∈ triangle.edges then {triangle} else ∅).card = 1] m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinset⊢ (if e ∈ triangle.edges then {triangle} else ∅).card = 1
split_ifs with h pos m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∈ triangle.edges⊢ {triangle}.card = 1neg m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∉ triangle.edges⊢ ∅.card = 1
· pos m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∈ triangle.edges⊢ {triangle}.card = 1 rfl All goals completed! 🐙
· neg m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∉ triangle.edges⊢ ∅.card = 1 exfalso neg m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∉ triangle.edges⊢ False
apply h neg m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∉ triangle.edges⊢ e ∈ triangle.edges
have he' : e ∈ (completeGraph (Fin 3)).edgeSet := mem_edgeFinset.mp he neg m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1e:Sym2 (Fin 3)he:e ∈ (completeGraph (Fin 3)).edgeFinseth:e ∉ triangle.edgeshe':e ∈ (completeGraph (Fin 3)).edgeSet⊢ e ∈ triangle.edges
induction e using Sym2.ind with
| h a b => neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':s(a, b) ∈ (completeGraph (Fin 3)).edgeSet⊢ s(a, b) ∈ triangle.edges
rw [mem_edgeSet, neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':(completeGraph (Fin 3)).Adj a b⊢ s(a, b) ∈ triangle.edges neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':a ≠ b⊢ s(a, b) ∈ triangle.edges completeGraph_eq_top, neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':⊤.Adj a b⊢ s(a, b) ∈ triangle.edgesneg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':a ≠ b⊢ s(a, b) ∈ triangle.edges top_adj neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':a ≠ b⊢ s(a, b) ∈ triangle.edgesneg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':a ≠ b⊢ s(a, b) ∈ triangle.edges] at he'neg.h m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1a:Fin 3b:Fin 3he:s(a, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s(a, b) ∉ triangle.edgeshe':a ≠ b⊢ s(a, b) ∈ triangle.edges
fin_cases a neg.h.«_@».1219813011._hygCtx._hyg.341.«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨0, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨0, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨0, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨0, ⋯⟩, b) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨1, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨1, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨1, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨1, ⋯⟩, b) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨2, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨2, ⋯⟩, b) ∈ triangle.edges <;> neg.h.«_@».1219813011._hygCtx._hyg.341.«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨0, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨0, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨0, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨0, ⋯⟩, b) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨1, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨1, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨1, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨1, ⋯⟩, b) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1b:Fin 3he:s((fun i ↦ i) ⟨2, ⋯⟩, b) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, b) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ b⊢ s((fun i ↦ i) ⟨2, ⋯⟩, b) ∈ triangle.edges fin_cases b neg.h.«_@».1219813011._hygCtx._hyg.341.«2».«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨0, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2».«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨1, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2».«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨2, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ triangle.edges <;> neg.h.«_@».1219813011._hygCtx._hyg.341.«0».«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨0, ⋯⟩ ≠ (fun i ↦ i) ⟨0, ⋯⟩⊢ s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«0».«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨0, ⋯⟩ ≠ (fun i ↦ i) ⟨1, ⋯⟩⊢ s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«0».«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨0, ⋯⟩ ≠ (fun i ↦ i) ⟨2, ⋯⟩⊢ s((fun i ↦ i) ⟨0, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«1».«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨1, ⋯⟩ ≠ (fun i ↦ i) ⟨0, ⋯⟩⊢ s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«1».«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨1, ⋯⟩ ≠ (fun i ↦ i) ⟨1, ⋯⟩⊢ s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«1».«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨1, ⋯⟩ ≠ (fun i ↦ i) ⟨2, ⋯⟩⊢ s((fun i ↦ i) ⟨1, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2».«0» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨0, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨0, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2».«1» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨1, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨1, ⋯⟩) ∈ triangle.edgesneg.h.«_@».1219813011._hygCtx._hyg.341.«2».«2» m:Multiset ℕhm:∀ x ∈ m, 3 ≤ x ∧ x ≤ 3hsum:m.sum = Nat.choose 3 2hm3:m = Multiset.replicate m.card 3hcard:m.card = 1he:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ (completeGraph (Fin 3)).edgeFinseth:s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∉ triangle.edgeshe':(fun i ↦ i) ⟨2, ⋯⟩ ≠ (fun i ↦ i) ⟨2, ⋯⟩⊢ s((fun i ↦ i) ⟨2, ⋯⟩, (fun i ↦ i) ⟨2, ⋯⟩) ∈ triangle.edges first | exact absurd rfl he' All goals completed! 🐙 | decide All goals completed! 🐙
The exceptional Oberwolfach $2$-factor C₄ + C₅ on nine vertices.
def oberwolfachException9 : SimpleGraph (Fin 4 ⊕ Fin 5) :=
cycleGraph 4 ⊕g cycleGraph 5
The exceptional Oberwolfach $2$-factor C₃ + C₃ + C₅ on eleven vertices.
def oberwolfachException11 : SimpleGraph ((Fin 3 ⊕ Fin 3) ⊕ Fin 5) :=
(cycleGraph 3 ⊕g cycleGraph 3) ⊕g cycleGraph 5The Oberwolfach problem (Ringel 1967).
For odd $n$ and a $2$-regular graph $F$ on $n$ vertices, can $K_n$ be decomposed into $(n-1)/2$ spanning subgraphs isomorphic to $F$? The decomposition is known to be impossible for exactly two pairs with odd $n$ — $(9, C_4 + C_5)$ and $(11, C_3 + C_3 + C_5)$ — and is conjectured to exist in every other case. Known for all sufficiently large $n$ [GJKKO21].
@[category research open, AMS 5]
theorem alspach_conjecture.variants.oberwolfach :
∀ (n : ℕ), Odd n → 3 ≤ n →
∀ (F : SimpleGraph (Fin n)) [DecidableRel F.Adj], (∀ v, F.degree v = 2) →
IsEmpty (F ≃g oberwolfachException9) → IsEmpty (F ≃g oberwolfachException11) →
∃ D : Fin ((n - 1) / 2) → SimpleGraph (Fin n),
(∀ i, Nonempty (D i ≃g F)) ∧
∀ u v, (completeGraph (Fin n)).Adj u v ↔ ∃! i, (D i).Adj u v := by ⊢ ∀ (n : ℕ),
Odd n →
3 ≤ n →
∀ (F : SimpleGraph (Fin n)) [inst : DecidableRel F.Adj],
(∀ (v : Fin n), F.degree v = 2) →
IsEmpty (F ≃g oberwolfachException9) →
IsEmpty (F ≃g oberwolfachException11) →
∃ D,
(∀ (i : Fin ((n - 1) / 2)), Nonempty (D i ≃g F)) ∧
∀ (u v : Fin n), (completeGraph (Fin n)).Adj u v ↔ ∃! i, (D i).Adj u v
sorry All goals completed! 🐙end AlspachConjecture