AFTD Auto-Formalizing Theoretical Domains

triangle_free_subcubic_independent_bipartite_partition_negation

theoremverifiedformalization

Refutation of Open Problem OP-1086: there exists a finite simple graph with maximum degree at most 3 that is triangle-free (contains no 3-clique) admitting no partition of its vertex set into an independent set L and complement R = Lᶜ such that G[R] is bipartite and for every connected component C of G[R] and every vertex v in L, the induced subgraph on V(C) ∪ {v} is bipartite.

Statement

theorem triangle_free_subcubic_independent_bipartite_partition_negation :
    ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : SimpleGraph V) (_ : DecidableRel G.Adj),
      G.maxDegree ≤ 3 ∧
      G.CliqueFree 3 ∧
      ¬ ∃ L : Finset V,
        G.induce (L : Set V) = ⊥ ∧
        (G.induce (Lᶜ : Set V)).IsBipartite ∧
        ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,
          ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite
Formalizes
scout/2611-05178-weighted-max-cut-in-subcubic-graphs.md:1025
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

There exists a finite type $V$ with decidable equality and a simple graph $G$ on $V$ with decidable adjacency such that: 1. $G$ has maximum degree at most 3 ($G.\text{maxDegree} \le 3$), 2. $G$ is triangle-free ($G.\text{CliqueFree}\ 3$), and 3. There does not exist a subset $L \subseteq V$ (given as a Finset V) such that: a. $L$ is an independent set in $G$ (the induced subgraph on $L$ has no edges: $G.\text{induce}\ L = \bot$), b. the induced subgraph on the complement $V \setminus L$ is bipartite, and c. for every connected component $C$ of the induced subgraph $G[V \setminus L]$ and every vertex $v \in L$, the subgraph of $G$ induced by $C \cup \{v\}$ is bipartite.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof refutes Open Problem OP-1086 by exhibiting the 8-vertex Möbius ladder graph (the cycle C₈ with 4 diameter chords i ↔ i + 4), which is 3-regular and triangle-free. A preliminary lemma shows that no bipartite induced subgraph can contain an odd cycle of length 5. Exhaustive computation (`decide`) establishes that for every independent set L, some 5-cycle is either entirely contained in Lᶜ or has 4 vertices in Lᶜ and 1 vertex v in L. In the first case, G[Lᶜ] contains a 5-cycle and cannot be bipartite; in the second case, the 4 vertices form a connected path in G[Lᶜ] and thus lie in a single connected component C, so G[V(C) ∪ {v}] contains the full 5-cycle and cannot be bipartite.

  1. The graph on 8 vertices with adjacency j = i ± 1 or j = i + 4 (mod 8) is well-defined, symmetric, and loopless. automation

    Defines the graph on vertex set ℤ₈ = Fin 8 where edges connect vertices differing modulo 8 by ±1 or 4. Symmetry is verified by propositional logic (`tauto`), and looplessness is verified by exhausting all 8 vertices and checking that no vertex is adjacent to itself (`fin_cases` and `decide`).

    lines 1–6

    abbrev triangle_free_subcubic_independent_bipartite_partition_negation_graph :
        SimpleGraph (Fin 8) where
      Adj i j := j = i + 1 ∨ i = j + 1 ∨ j = i + 4 ∨ i = j + 4
      symm := ⟨fun i j h => by tauto⟩
      loopless := ⟨fun i h => by fin_cases i <;> exact absurd h (by decide)⟩
    
  2. The canonical 5-cycle map and its rotations in the 8-vertex graph are well-defined.

    Defines `cyc` mapping k ∈ {0, …, 4} to i + k (mod 8), using arithmetic (`omega`) and `Fin.castLE` to embed Fin 5 into Fin 8, and defines `rot` as the cyclic rotation of this cycle by an offset k₀.

    lines 7–13

    uses Fin.castLE

    abbrev triangle_free_subcubic_independent_bipartite_partition_negation_cyc
        (i : Fin 8) (k : Fin 5) : Fin 8 := i + Fin.castLE (by omega) k
    
    abbrev triangle_free_subcubic_independent_bipartite_partition_negation_rot
        (i : Fin 8) (k₀ k : Fin 5) : Fin 8 :=
      triangle_free_subcubic_independent_bipartite_partition_negation_cyc i (k₀ + k)
    
  3. Any 2-coloring of an induced subgraph containing a 5-cycle must assign different colors to adjacent cycle vertices.

    To show that an induced subgraph S containing a 5-cycle cannot be bipartite, suppose for contradiction it admits a 2-coloring c : S → Fin 2. Composing c with the cycle map f : Fin 5 → S yields a color sequence a : Fin 5 → Fin 2. Because consecutive cycle vertices are adjacent in the induced subgraph by `SimpleGraph.induce_adj`, the coloring property forces a(k) ≠ a(k + 1) for every k ∈ Fin 5.

    lines 14–25

    uses SimpleGraph.induce_adj

    private lemma triangle_free_subcubic_independent_bipartite_partition_negation_cycle5
        {V : Type*} {G : SimpleGraph V} {S : Set V} (f : Fin 5 → V)
        (hmem : ∀ k : Fin 5, f k ∈ S) (hedge : ∀ k : Fin 5, G.Adj (f k) (f (k + 1))) :
        ¬ (G.induce S).IsBipartite := by
      rintro ⟨c⟩
      let a : Fin 5 → Fin 2 := fun k => c ⟨f k, hmem k⟩
      have hne : ∀ k : Fin 5, a k ≠ a (k + 1) := by
        intro k
        have h : (G.induce S).Adj ⟨f k, hmem k⟩ ⟨f (k + 1), hmem (k + 1)⟩ := by
          rw [SimpleGraph.induce_adj]; exact hedge k
        have h2 := c.map_rel h
        simpa [a] using h2
  4. An induced subgraph containing a 5-cycle cannot be bipartite.

    Since colors lie in {0, 1}, the inequality a(k) ≠ a(k + 1) implies the sum of their integer values is 1, established via `Fin.ext` and linear arithmetic. Specializing this identity to the five cycle steps k = 0, 1, 2, 3, 4 gives a system of equations a₀ + a₁ = 1, a₁ + a₂ = 1, a₂ + a₃ = 1, a₃ + a₄ = 1, and a₄ + a₀ = 1. This system is inconsistent over the natural numbers (summing with alternating signs forces 2 a₀ = 1), yielding False via `omega`.

    lines 26–42

    uses Fin.ext

      have hval : ∀ k : Fin 5, (a k).val + (a (k + 1)).val = 1 := by
        intro k
        have h1 : (a k).val < 2 := (a k).isLt
        have h2 : (a (k + 1)).val < 2 := (a (k + 1)).isLt
        have h3 : (a k).val ≠ (a (k + 1)).val := by
          intro hh; exact hne k (Fin.ext hh)
        omega
      have h0 := hval 0
      have h1 := hval 1
      have h2 := hval 2
      have h3 := hval 3
      have h4 := hval 4
      simp only [show (0 : Fin 5) + 1 = 1 from rfl, show (1 : Fin 5) + 1 = 2 from rfl,
        show (2 : Fin 5) + 1 = 3 from rfl, show (3 : Fin 5) + 1 = 4 from rfl,
        show (4 : Fin 5) + 1 = 0 from rfl] at h0 h1 h2 h3 h4
      omega
    
  5. Consecutive vertices in the canonical 5-cycle and its rotations are adjacent in the graph. automation

    Verifies by finite computation (`decide`) that each step in the 5-cycle k ↦ i + k is an edge of the graph, since consecutive steps differ by 1 modulo 8 and the wraparound step from 4 to 0 differs by 4. Using associativity of addition (`add_assoc`), the same adjacency holds for any cyclic rotation of the 5-cycle.

    lines 43–66

    uses add_assoc

    /-- Refutation of Question 5.3 of arXiv:2611.05178 (OP-1086): there exists a finite triangle-free subcubic simple graph admitting no independent-bipartite component partition. -/
    theorem triangle_free_subcubic_independent_bipartite_partition_negation :
        ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : SimpleGraph V) (_ : DecidableRel G.Adj),
          G.maxDegree ≤ 3 ∧
          G.CliqueFree 3 ∧
          ¬ ∃ L : Finset V,
            G.induce (L : Set V) = ⊥ ∧
            (G.induce (Lᶜ : Set V)).IsBipartite ∧
            ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,
              ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite := by
      have hcyc_adj : ∀ (i : Fin 8) (k : Fin 5),
          triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj
            (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k)
            (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i (k + 1)) := by
        decide
      have hrot_adj : ∀ (i : Fin 8) (k₀ : Fin 5) (k : Fin 5),
          triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj
            (triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k)
            (triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ (k + 1)) := by
        intro i k₀ k
        have h : k₀ + (k + 1) = (k₀ + k) + 1 := by rw [add_assoc]
        rw [triangle_free_subcubic_independent_bipartite_partition_negation_rot,
          triangle_free_subcubic_independent_bipartite_partition_negation_rot, h]
        exact hcyc_adj i (k₀ + k)
  6. The graph contains no triangles (3-cliques). automation

    Verifies by exhaustive finite checking (`decide`) that no triple of vertices x, y, z in Fin 8 has all three mutual edges present.

    lines 67–71

      have hno_triangle : ∀ x y z : Fin 8,
          ¬ (triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y ∧
            triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x z ∧
            triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj y z) := by
        decide
  7. For every independent set L, some 5-cycle is either disjoint from L or contains exactly one vertex of L. automation

    Establishes by exhaustive checking over all subsets of Fin 8 (`decide`) the key combinatorial property: whenever L is an independent set, there exists a 5-cycle entirely contained in Lᶜ, or there exists a 5-cycle having its base vertex in L and its remaining 4 vertices in Lᶜ.

    lines 72–81

      have hkey : ∀ (L : Finset (Fin 8)),
          (∀ x ∈ L, ∀ y ∈ L,
            ¬ triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y) →
          (∃ i : Fin 8, ∀ k : Fin 5,
            triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k ∉ L) ∨
          (∃ (i : Fin 8) (k₀ : Fin 5),
            triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀ ∈ L ∧
            ∀ k' : Fin 5, k' ≠ 0 →
              triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k' ∉ L) := by
        decide
  8. The maximum degree of the graph is at most 3. automation

    Supplies the 8-vertex graph as the existential witness and checks by computation (`decide`) that its maximum degree is at most 3 (it is 3-regular).

    lines 82–84

      refine ⟨Fin 8, inferInstance, inferInstance,
        triangle_free_subcubic_independent_bipartite_partition_negation_graph, inferInstance, ?_, ?_, ?_⟩
      · decide
  9. The graph is triangle-free (CliqueFree 3).

    For any 3-clique t, `Finset.card_eq_three.mp` extracts its three distinct vertices x, y, z. The clique assumption implies mutual adjacency between all three pairs, which directly contradicts the absence of triangles established in `hno_triangle`.

    lines 85–89

    uses Finset.card_eq_three.mp

      · intro t ht
        obtain ⟨hcl, hcard⟩ := ht
        obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hcard
        exact hno_triangle x y z
          ⟨hcl (by simp) (by simp) hxy, hcl (by simp) (by simp) hxz, hcl (by simp) (by simp) hyz⟩
  10. Assuming a valid independent-bipartite partition exists, split into the two cases of the combinatorial lemma.

    Suppose for contradiction there is an independent set L such that G[Lᶜ] is bipartite and for every connected component C of G[Lᶜ] and vertex v ∈ L, G[V(C) ∪ {v}] is bipartite. Since G[L] = ⊥, no two vertices in L are adjacent (via `SimpleGraph.induce_adj`). Applying `hkey` to L splits the proof into two cases: a 5-cycle disjoint from L, or a 5-cycle meeting L in exactly one vertex.

    lines 90–99

    uses SimpleGraph.induce_adj

      · rintro ⟨L, hind, hbip, hcomp⟩
        have hL : ∀ x ∈ L, ∀ y ∈ L,
            ¬ triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y := by
          intro x hx y hy hxy
          have h1 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
              (L : Set (Fin 8))).Adj ⟨x, by simpa using hx⟩ ⟨y, by simpa using hy⟩ := by
            rw [SimpleGraph.induce_adj]; exact hxy
          rw [hind] at h1
          simp at h1
        rcases hkey L hL with ⟨i, hi⟩ | ⟨i, k₀, hmem0, hrest⟩
  11. Case 1: If an entire 5-cycle lies in Lᶜ, G[Lᶜ] cannot be bipartite, yielding a contradiction.

    All five vertices of the cycle lie in Lᶜ, and their adjacencies are given by `hcyc_adj`. Applying the helper lemma `triangle_free_subcubic_independent_bipartite_partition_negation_cycle5` proves that G[Lᶜ] is not bipartite, directly contradicting the assumption that G[Lᶜ] is bipartite.

    lines 100–107

    uses triangle_free_subcubic_independent_bipartite_partition_negation_cycle5

        · refine (triangle_free_subcubic_independent_bipartite_partition_negation_cycle5
            (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph)
            (S := (↑L : Set (Fin 8))ᶜ)
            (f := fun k => triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k) ?_ ?_) hbip
          · intro k
            simpa using hi k
          · intro k
            exact hcyc_adj i k
  12. Case 2: The four vertices of the 5-cycle in Lᶜ belong to the same connected component of G[Lᶜ].

    In the second case, one vertex v of the 5-cycle is in L, and the other four vertices p₁, p₂, p₃, p₄ are in Lᶜ. Consecutive pairs are adjacent in G[Lᶜ] by `SimpleGraph.induce_adj`. Letting C be the component of p₁ via `SimpleGraph.connectedComponentMk`, the membership characterization `SimpleGraph.ConnectedComponent.mem_supp_iff` gives p₁ ∈ C, and connectivity propagation along edges via `SimpleGraph.ConnectedComponent.mem_supp_congr_adj` shows that p₂, p₃, and p₄ all belong to C.

    lines 108–148

    uses SimpleGraph.ConnectedComponent.mem_supp_congr_adj, SimpleGraph.ConnectedComponent.mem_supp_iff, SimpleGraph.induce_adj

        · have hRm : ∀ k' : Fin 5, k' ≠ 0 →
              triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k' ∈
                (↑L : Set (Fin 8))ᶜ := by
            intro k' hk'
            simpa using hrest k' hk'
          let p1 : ↥((↑L : Set (Fin 8))ᶜ) :=
            ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 1, hRm 1 (by decide)⟩
          let p2 : ↥((↑L : Set (Fin 8))ᶜ) :=
            ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 2, hRm 2 (by decide)⟩
          let p3 : ↥((↑L : Set (Fin 8))ᶜ) :=
            ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 3, hRm 3 (by decide)⟩
          let p4 : ↥((↑L : Set (Fin 8))ᶜ) :=
            ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 4, hRm 4 (by decide)⟩
          let C := (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
            (↑L : Set (Fin 8))ᶜ).connectedComponentMk p1
          have h12 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
              (↑L : Set (Fin 8))ᶜ).Adj p1 p2 := by
            rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 1
          have h23 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
              (↑L : Set (Fin 8))ᶜ).Adj p2 p3 := by
            rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 2
          have h34 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
              (↑L : Set (Fin 8))ᶜ).Adj p3 p4 := by
            rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 3
          have h1C : p1 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) := by
            change p1 ∈ C.supp
            rw [SimpleGraph.ConnectedComponent.mem_supp_iff]
          have h2C : p2 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=
            (SimpleGraph.ConnectedComponent.mem_supp_congr_adj
              (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
                (↑L : Set (Fin 8))ᶜ) C h12).mp h1C
          have h3C : p3 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=
            (SimpleGraph.ConnectedComponent.mem_supp_congr_adj
              (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
                (↑L : Set (Fin 8))ᶜ) C h23).mp h2C
          have h4C : p4 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=
            (SimpleGraph.ConnectedComponent.mem_supp_congr_adj
              (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce
                (↑L : Set (Fin 8))ᶜ) C h34).mp h3C
          have hbipC := hcomp C
            (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀) hmem0
  13. Case 2 completion: The induced subgraph G[V(C) ∪ {v}] contains the full 5-cycle and cannot be bipartite, reaching the final contradiction.

    The rotated 5-cycle has one vertex at v ∈ L and its other four vertices in V(C), so all five cycle vertices lie in V(C) ∪ {v}. By `triangle_free_subcubic_independent_bipartite_partition_negation_cycle5`, G[V(C) ∪ {v}] cannot be bipartite, contradicting the hypothesis that every component augmented by v is bipartite.

    lines 149–167

    uses triangle_free_subcubic_independent_bipartite_partition_negation_cycle5

          refine (triangle_free_subcubic_independent_bipartite_partition_negation_cycle5
            (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph)
            (S := Subtype.val '' (C : Set ↥((↑L : Set (Fin 8))ᶜ)) ∪
              {triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀})
            (f := fun k => triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k) ?_ ?_) hbipC
          · intro k
            by_cases hk : k = 0
            · subst hk
              right
              simp [triangle_free_subcubic_independent_bipartite_partition_negation_rot]
            · left
              fin_cases k
              · exact absurd rfl hk
              · exact ⟨p1, h1C, rfl⟩
              · exact ⟨p2, h2C, rfl⟩
              · exact ⟨p3, h3C, rfl⟩
              · exact ⟨p4, h4C, rfl⟩
          · intro k
            exact hrot_adj i k₀ k
Fin.castLE
embeds an element of Fin n into Fin m given a proof that n ≤ m
SimpleGraph.induce_adj
two vertices in an induced subgraph are adjacent if and only if their underlying vertices are adjacent in the original graph
Fin.ext
two elements of Fin n are equal if and only if their underlying natural numbers are equal
add_assoc
addition in an additive semigroup is associative: (a + b) + c = a + (b + c)
Finset.card_eq_three.mp
a finite set has cardinality 3 if and only if it consists of three distinct elements
triangle_free_subcubic_independent_bipartite_partition_negation_cycle5
an induced subgraph containing a 5-cycle cannot be bipartite (admits no proper 2-coloring)
SimpleGraph.ConnectedComponent.mem_supp_iff
a vertex belongs to the support of a connected component if and only if the component is the one containing that vertex
SimpleGraph.ConnectedComponent.mem_supp_congr_adj
if two vertices are adjacent in a graph, one belongs to a connected component if and only if the other does

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

abbrev triangle_free_subcubic_independent_bipartite_partition_negation_graph :    SimpleGraph (Fin 8) where  Adj i j := j = i + 1 ∨ i = j + 1 ∨ j = i + 4 ∨ i = j + 4  symm := ⟨fun i j h => by tauto⟩  loopless := ⟨fun i h => by fin_cases i <;> exact absurd h (by decide)⟩abbrev triangle_free_subcubic_independent_bipartite_partition_negation_cyc    (i : Fin 8) (k : Fin 5) : Fin 8 := i + Fin.castLE (by omega) kabbrev triangle_free_subcubic_independent_bipartite_partition_negation_rot    (i : Fin 8) (k₀ k : Fin 5) : Fin 8 :=  triangle_free_subcubic_independent_bipartite_partition_negation_cyc i (k₀ + k)private lemma triangle_free_subcubic_independent_bipartite_partition_negation_cycle5    {V : Type*} {G : SimpleGraph V} {S : Set V} (f : Fin 5 → V)    (hmem : ∀ k : Fin 5, f k ∈ S) (hedge : ∀ k : Fin 5, G.Adj (f k) (f (k + 1))) :    ¬ (G.induce S).IsBipartite := by  rintro ⟨c⟩  let a : Fin 5 → Fin 2 := fun k => c ⟨f k, hmem k⟩  have hne : ∀ k : Fin 5, a k ≠ a (k + 1) := by    intro k    have h : (G.induce S).Adj ⟨f k, hmem k⟩ ⟨f (k + 1), hmem (k + 1)⟩ := by      rw [SimpleGraph.induce_adj]; exact hedge k    have h2 := c.map_rel h    simpa [a] using h2  have hval : ∀ k : Fin 5, (a k).val + (a (k + 1)).val = 1 := by    intro k    have h1 : (a k).val < 2 := (a k).isLt    have h2 : (a (k + 1)).val < 2 := (a (k + 1)).isLt    have h3 : (a k).val ≠ (a (k + 1)).val := by      intro hh; exact hne k (Fin.ext hh)    omega  have h0 := hval 0  have h1 := hval 1  have h2 := hval 2  have h3 := hval 3  have h4 := hval 4  simp only [show (0 : Fin 5) + 1 = 1 from rfl, show (1 : Fin 5) + 1 = 2 from rfl,    show (2 : Fin 5) + 1 = 3 from rfl, show (3 : Fin 5) + 1 = 4 from rfl,    show (4 : Fin 5) + 1 = 0 from rfl] at h0 h1 h2 h3 h4  omega/-- Refutation of Question 5.3 of arXiv:2611.05178 (OP-1086): there exists a finite triangle-free subcubic simple graph admitting no independent-bipartite component partition. -/theorem triangle_free_subcubic_independent_bipartite_partition_negation :    ∃ (V : Type) (_ : Fintype V) (_ : DecidableEq V) (G : SimpleGraph V) (_ : DecidableRel G.Adj),      G.maxDegree ≤ 3 ∧      G.CliqueFree 3 ∧      ¬ ∃ L : Finset V,        G.induce (L : Set V) = ⊥ ∧        (G.induce (Lᶜ : Set V)).IsBipartite ∧        ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent,          ∀ v ∈ L, (G.induce (Subtype.val '' (C : Set ↑(Lᶜ : Set V)) ∪ {v})).IsBipartite := by  have hcyc_adj : ∀ (i : Fin 8) (k : Fin 5),      triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj        (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k)        (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i (k + 1)) := by    decide  have hrot_adj : ∀ (i : Fin 8) (k₀ : Fin 5) (k : Fin 5),      triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj        (triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k)        (triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ (k + 1)) := by    intro i k₀ k    have h : k₀ + (k + 1) = (k₀ + k) + 1 := by rw [add_assoc]    rw [triangle_free_subcubic_independent_bipartite_partition_negation_rot,      triangle_free_subcubic_independent_bipartite_partition_negation_rot, h]    exact hcyc_adj i (k₀ + k)  have hno_triangle : ∀ x y z : Fin 8,      ¬ (triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y ∧        triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x z ∧        triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj y z) := by    decide  have hkey : ∀ (L : Finset (Fin 8)),      (∀ x ∈ L, ∀ y ∈ L,        ¬ triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y) →      (∃ i : Fin 8, ∀ k : Fin 5,        triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k ∉ L) ∨      (∃ (i : Fin 8) (k₀ : Fin 5),        triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀ ∈ L ∧        ∀ k' : Fin 5, k' ≠ 0 →          triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k' ∉ L) := by    decide  refine ⟨Fin 8, inferInstance, inferInstance,    triangle_free_subcubic_independent_bipartite_partition_negation_graph, inferInstance, ?_, ?_, ?_⟩  · decide  · intro t ht    obtain ⟨hcl, hcard⟩ := ht    obtain ⟨x, y, z, hxy, hxz, hyz, rfl⟩ := Finset.card_eq_three.mp hcard    exact hno_triangle x y z      ⟨hcl (by simp) (by simp) hxy, hcl (by simp) (by simp) hxz, hcl (by simp) (by simp) hyz⟩  · rintro ⟨L, hind, hbip, hcomp⟩    have hL : ∀ x ∈ L, ∀ y ∈ L,        ¬ triangle_free_subcubic_independent_bipartite_partition_negation_graph.Adj x y := by      intro x hx y hy hxy      have h1 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce          (L : Set (Fin 8))).Adj ⟨x, by simpa using hx⟩ ⟨y, by simpa using hy⟩ := by        rw [SimpleGraph.induce_adj]; exact hxy      rw [hind] at h1      simp at h1    rcases hkey L hL with ⟨i, hi⟩ | ⟨i, k₀, hmem0, hrest⟩    · refine (triangle_free_subcubic_independent_bipartite_partition_negation_cycle5        (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph)        (S := (↑L : Set (Fin 8))ᶜ)        (f := fun k => triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k) ?_ ?_) hbip      · intro k        simpa using hi k      · intro k        exact hcyc_adj i k    · have hRm : ∀ k' : Fin 5, k' ≠ 0 →          triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k' ∈            (↑L : Set (Fin 8))ᶜ := by        intro k' hk'        simpa using hrest k' hk'      let p1 : ↥((↑L : Set (Fin 8))ᶜ) :=        ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 1, hRm 1 (by decide)⟩      let p2 : ↥((↑L : Set (Fin 8))ᶜ) :=        ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 2, hRm 2 (by decide)⟩      let p3 : ↥((↑L : Set (Fin 8))ᶜ) :=        ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 3, hRm 3 (by decide)⟩      let p4 : ↥((↑L : Set (Fin 8))ᶜ) :=        ⟨triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ 4, hRm 4 (by decide)⟩      let C := (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce        (↑L : Set (Fin 8))ᶜ).connectedComponentMk p1      have h12 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce          (↑L : Set (Fin 8))ᶜ).Adj p1 p2 := by        rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 1      have h23 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce          (↑L : Set (Fin 8))ᶜ).Adj p2 p3 := by        rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 2      have h34 : (triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce          (↑L : Set (Fin 8))ᶜ).Adj p3 p4 := by        rw [SimpleGraph.induce_adj]; exact hrot_adj i k₀ 3      have h1C : p1 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) := by        change p1 ∈ C.supp        rw [SimpleGraph.ConnectedComponent.mem_supp_iff]      have h2C : p2 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=        (SimpleGraph.ConnectedComponent.mem_supp_congr_adj          (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce            (↑L : Set (Fin 8))ᶜ) C h12).mp h1C      have h3C : p3 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=        (SimpleGraph.ConnectedComponent.mem_supp_congr_adj          (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce            (↑L : Set (Fin 8))ᶜ) C h23).mp h2C      have h4C : p4 ∈ (C : Set ↥((↑L : Set (Fin 8))ᶜ)) :=        (SimpleGraph.ConnectedComponent.mem_supp_congr_adj          (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph.induce            (↑L : Set (Fin 8))ᶜ) C h34).mp h3C      have hbipC := hcomp C        (triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀) hmem0      refine (triangle_free_subcubic_independent_bipartite_partition_negation_cycle5        (G := triangle_free_subcubic_independent_bipartite_partition_negation_graph)        (S := Subtype.val '' (C : Set ↥((↑L : Set (Fin 8))ᶜ)) ∪          {triangle_free_subcubic_independent_bipartite_partition_negation_cyc i k₀})        (f := fun k => triangle_free_subcubic_independent_bipartite_partition_negation_rot i k₀ k) ?_ ?_) hbipC      · intro k        by_cases hk : k = 0        · subst hk          right          simp [triangle_free_subcubic_independent_bipartite_partition_negation_rot]        · left          fin_cases k          · exact absurd rfl hk          · exact ⟨p1, h1C, rfl⟩          · exact ⟨p2, h2C, rfl⟩          · exact ⟨p3, h3C, rfl⟩          · exact ⟨p4, h4C, rfl⟩      · intro k        exact hrot_adj i k₀ k
See it in the graphDiscuss this resultChallenge it