triangle_free_subcubic_independent_bipartite_partition_negation
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.
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`).
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)⟩
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₀.
uses
Fin.castLEabbrev 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)
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.
uses
SimpleGraph.induce_adjprivate 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
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`.
uses
Fin.exthave 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
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.
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)
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.
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
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ᶜ.
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
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).
refine ⟨Fin 8, inferInstance, inferInstance, triangle_free_subcubic_independent_bipartite_partition_negation_graph, inferInstance, ?_, ?_, ?_⟩ · decide
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`.
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⟩
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.
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⟩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.
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
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.
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
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.
uses
triangle_free_subcubic_independent_bipartite_partition_negation_cycle5refine (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
- The counterexample graph is the 8-vertex Möbius ladder (an 8-cycle with four main diagonals).
- Key combinatorial and structural properties of this graph—maximum degree at most 3, absence of triangles, looplessness, and the partition case exhaustion (hkey)—are established by Lean's kernel evaluator through exhaustive computation (`decide`).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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