two_extra_fork_subgraph_counterexample
There is a triangle-free graph on four pairs whose edges lie in the union of one fork per pair and two additional forks, but whose independence number is less than four.
Statement
theorem two_extra_fork_subgraph_counterexample :
∃ (G : SimpleGraph (Fin 4 × Fin 2)) (w : Fin 4 → Fin 4 × Fin 2),
(∀ i, (w i).1 ≠ i) ∧
(∀ x y, G.Adj x y →
(∃ i : Fin 4, (x.1 = i ∧ y = w i) ∨ (y.1 = i ∧ x = w i)) ∨
(x.1 = 0 ∧ y = (1,1)) ∨ (y.1 = 0 ∧ x = (1,1)) ∨
(x.1 = 3 ∧ y = (0,1)) ∨ (y.1 = 3 ∧ x = (0,1))) ∧
G.CliqueFree 3 ∧
¬∃ I : Finset (Fin 4 × Fin 2), 4 ≤ I.card ∧ G.IsIndepSet (I : Set (Fin 4 × Fin 2))- Source
- Refutes the partial-fork subgraph lemma using the explicit eight-vertex graph in experiment 16921.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The counterexample is constructed explicitly as an 8-vertex simple graph `graph580` on four pairs Fin 4 × Fin 2 with 10 edges. An explicit target function w : Fin 4 → Fin 4 × Fin 2 maps each pair index to an outside vertex, and exhaustive finite evaluation (`decide`) verifies that all edges lie within the four base forks defined by w plus two additional forks. Triangle-freeness is established by checking that no two adjacent edges share a third edge, which eliminates all 3-cliques. Finally, an exhaustive case analysis over all 2⁸ = 256 vertex subsets proves that no independent set contains both endpoints of any edge and has size at least 4, demonstrating that the independence number is strictly less than four.
The relation `graph580.Adj` defines a valid simple graph on Fin 4 × Fin 2 (it is symmetric and loopless).
Adjacency requires x ≠ y and that the named vertex pair (or its reverse) belongs to the 10-element edge list `edges580`. Symmetry follows by swapping the components of the disjunction and symmetry of inequality; looplessness holds because x ≠ x is impossible.
symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨by intro x h; exact h.1 rfl⟩
Each pair's fork target vertex lies outside that pair: (w(i))₁ ≠ i for all i ∈ Fin 4.
The `decide` tactic evaluates the inequality on the four values of w: w(0) = (2, 1), w(1) = (2, 0), w(2) = (3, 1), and w(3) = (1, 0), each having a first coordinate distinct from its input.
theorem hw580 : ∀ i, (w580 i).1 ≠ i := by decide
Every edge of `graph580` belongs to one of the four base forks or one of the two additional forks.
Finite exhaustion via `decide` verifies that every adjacent pair x, y is covered either by a base fork (one endpoint in pair i and the other equal to w(i)), an extra fork from pair 0 to (1, 1), or an extra fork from pair 3 to (0, 1).
(x.1 = 3 ∧ y = (0,1)) ∨ (y.1 = 3 ∧ x = (0,1)) := by decide
No two adjacent edges in `graph580` have their other endpoints connected by an edge.
The `decide` tactic checks by exhaustion over all triples of vertices a, b, c that if a is adjacent to b and b is adjacent to c, then a is not adjacent to c.
decideThe graph `graph580` is clique-free of order 3 (triangle-free).
Given any putative 3-clique s, `SimpleGraph.isNClique_iff` and `Finset.card_eq_three.mp` express s as {a, b, c} with three distinct, pairwise adjacent vertices. Applying `notriangle580` to the edges (a, b) and (b, c) contradicts the adjacency of a and c.
uses
SimpleGraph.isNClique_iff,Finset.card_eq_three.mp,notriangle580intro s hs rw [SimpleGraph.isNClique_iff] at hs obtain ⟨hc, hs⟩ := hs obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp hs exact notriangle580 a b c (hc (by simp) (by simp) hab) (hc (by simp) (by simp) hbc) (hc (by simp) (by simp) hac)
The cardinality of any independent set I is given by the sum of its indicator values across all eight vertices.
Assuming an independent set I with |I| ≥ 4, the size |I| is expressed as the sum of indicators 1_{v ∈ I} over Fin 4 × Fin 2. Applying `Fintype.sum_prod_type`, `Fin.sum_univ_succ`, `Fin.sum_univ_zero`, and `add_zero` expands the sum into eight explicit binary terms.
uses
Fintype.sum_prod_type,Fin.sum_univ_succ,Fin.sum_univ_zero,add_zeroclassical intro ⟨I, hcard, hi⟩ have hc : I.card = ∑ v : V580, if v ∈ I then 1 else 0 := by simp rw [Fintype.sum_prod_type] at hc simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero] at hc
An independent set I cannot contain both endpoints of any of the ten edges of `graph580`.
For each of the ten edges ((0,0), (2,1)), ((0,0), (1,1)), ((1,0), (2,0)), ((1,0), (3,0)), ((2,0), (3,1)), ((2,0), (1,1)), ((2,1), (3,1)), ((1,1), (0,1)), ((3,0), (0,1)), and ((3,1), (0,1)), assuming both endpoints belong to I contradicts the independence of I.
have e03 : ¬ (((0,0) : V580) ∈ I ∧ ((2,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e04 : ¬ (((0,0) : V580) ∈ I ∧ ((1,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e12 : ¬ (((1,0) : V580) ∈ I ∧ ((2,0) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e15 : ¬ (((1,0) : V580) ∈ I ∧ ((3,0) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e26 : ¬ (((2,0) : V580) ∈ I ∧ ((3,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e24 : ¬ (((2,0) : V580) ∈ I ∧ ((1,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e36 : ¬ (((2,1) : V580) ∈ I ∧ ((3,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e47 : ¬ (((1,1) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e57 : ¬ (((3,0) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e67 : ¬ (((3,1) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide)
No independent set in `graph580` has cardinality 4 or greater. automation
A tree of eight nested `by_cases` splits generates all 2⁸ = 256 combinations of vertex membership in I. In every branch, either two adjacent vertices are included (violating an edge exclusion) or at most three vertices are selected (violating |I| ≥ 4); `simp_all` and linear arithmetic (`omega`) close every branch.
by_cases h0 : ((0,0) : V580) ∈ I <;> by_cases h1 : ((1,0) : V580) ∈ I <;> by_cases h2 : ((2,0) : V580) ∈ I <;> by_cases h3 : ((2,1) : V580) ∈ I <;> by_cases h4 : ((1,1) : V580) ∈ I <;> by_cases h5 : ((3,0) : V580) ∈ I <;> by_cases h6 : ((3,1) : V580) ∈ I <;> by_cases h7 : ((0,1) : V580) ∈ I <;> simp_all <;> omega
There exists a triangle-free graph on four pairs covered by four base forks and two extra forks whose independence number is less than four.
The graph `graph580` and the mapping `w580` serve as witnesses. Assembling the verified properties—non-reflexivity (`hw580`), fork covering (`cover580`), triangle-freeness (`trianglefree580`), and non-existence of 4-independent sets (`nofour580`)—establishes the existential statement.
uses
hw580,cover580,trianglefree580,nofour580exact ⟨graph580, w580, hw580, cover580, trianglefree580, nofour580⟩
SimpleGraph.isNClique_iff- A finite subset s of vertices is an n-clique of a simple graph G if and only if s is a clique and has cardinality n.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three pairwise distinct elements x, y, and z.
notriangle580- In `graph580`, if a is adjacent to b and b is adjacent to c, then a is not adjacent to c (the graph contains no triangles).
Fintype.sum_prod_type- A sum over a Cartesian product of two finite types decomposes into an iterated sum over each component.
Fin.sum_univ_succ- A sum of a function over Fin (n + 1) equals its value at 0 plus the sum of the remaining n terms.
Fin.sum_univ_zero- A sum over the empty index set Fin 0 is zero.
add_zero- Adding zero to any element leaves it unchanged (a + 0 = a).
hw580- For each pair index i in Fin 4, the target vertex w(i) does not belong to pair i.
cover580- Every edge of `graph580` belongs either to one of the four base forks defined by w or to one of the two extra forks.
trianglefree580- The graph `graph580` contains no 3-cliques (it is triangle-free).
nofour580- There is no independent set in `graph580` of cardinality 4 or greater.
- Several finite verifications (such as `hw580`, `cover580`, and `notriangle580`) are discharged by Lean's `decide` tactic via exhaustive computation over the finite types Fin 4 and Fin 4 × Fin 2.
- The proof that the independence number is less than 4 (`nofour580`) analyzes all 2⁸ = 256 subsets of vertices via nested `by_cases` splits, closing each branch using `simp_all` and linear arithmetic (`omega`).
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.
Lean’s trace was cut to the first 400 of 586 tactics.
set_option maxRecDepth 100000set_option maxHeartbeats 1000000abbrev V580 := Fin 4 × Fin 2def name580 (v : V580) : Fin 8 := ![![0,7], ![1,4], ![2,3], ![5,6]] v.1 v.2def edges580 : List (Fin 8 × Fin 8) := [(0,3),(0,4),(1,2),(1,5),(2,6),(2,4),(3,6),(4,7),(5,7),(6,7)]def graph580 : SimpleGraph V580 where Adj x y := x ≠ y ∧ ((name580 x, name580 y) ∈ edges580 ∨ (name580 y, name580 x) ∈ edges580) symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨by intro x h; exact h.1 rfl⟩instance : DecidableRel graph580.Adj := fun x y => inferInstanceAs (Decidable (x ≠ y ∧ _))def w580 : Fin 4 → V580 := ![(2,1),(2,0),(3,1),(1,0)]theorem hw580 : ∀ i, (w580 i).1 ≠ i := by decidetheorem cover580 : ∀ x y, graph580.Adj x y → (∃ i : Fin 4, (x.1 = i ∧ y = w580 i) ∨ (y.1 = i ∧ x = w580 i)) ∨ (x.1 = 0 ∧ y = (1,1)) ∨ (y.1 = 0 ∧ x = (1,1)) ∨ (x.1 = 3 ∧ y = (0,1)) ∨ (y.1 = 3 ∧ x = (0,1)) := by decidetheorem notriangle580 : ∀ a b c : V580, graph580.Adj a b → graph580.Adj b c → ¬ graph580.Adj a c := by decidetheorem trianglefree580 : graph580.CliqueFree 3 := by intro s hs rw [SimpleGraph.isNClique_iff] at hs obtain ⟨hc, hs⟩ := hs obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp hs exact notriangle580 a b c (hc (by simp) (by simp) hab) (hc (by simp) (by simp) hbc) (hc (by simp) (by simp) hac)theorem nofour580 : ¬∃ I : Finset V580, 4 ≤ I.card ∧ graph580.IsIndepSet (I : Set V580) := by classical intro ⟨I, hcard, hi⟩ have hc : I.card = ∑ v : V580, if v ∈ I then 1 else 0 := by simp rw [Fintype.sum_prod_type] at hc simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero] at hc have e03 : ¬ (((0,0) : V580) ∈ I ∧ ((2,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e04 : ¬ (((0,0) : V580) ∈ I ∧ ((1,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e12 : ¬ (((1,0) : V580) ∈ I ∧ ((2,0) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e15 : ¬ (((1,0) : V580) ∈ I ∧ ((3,0) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e26 : ¬ (((2,0) : V580) ∈ I ∧ ((3,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e24 : ¬ (((2,0) : V580) ∈ I ∧ ((1,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e36 : ¬ (((2,1) : V580) ∈ I ∧ ((3,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e47 : ¬ (((1,1) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e57 : ¬ (((3,0) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) have e67 : ¬ (((3,1) : V580) ∈ I ∧ ((0,1) : V580) ∈ I) := by rintro ⟨ha, hb⟩ exact (hi ha hb (by decide)) (by decide) by_cases h0 : ((0,0) : V580) ∈ I <;> by_cases h1 : ((1,0) : V580) ∈ I <;> by_cases h2 : ((2,0) : V580) ∈ I <;> by_cases h3 : ((2,1) : V580) ∈ I <;> by_cases h4 : ((1,1) : V580) ∈ I <;> by_cases h5 : ((3,0) : V580) ∈ I <;> by_cases h6 : ((3,1) : V580) ∈ I <;> by_cases h7 : ((0,1) : V580) ∈ I <;> simp_all <;> omegatheorem two_extra_fork_subgraph_counterexample : ∃ (G : SimpleGraph (Fin 4 × Fin 2)) (w : Fin 4 → Fin 4 × Fin 2), (∀ i, (w i).1 ≠ i) ∧ (∀ x y, G.Adj x y → (∃ i : Fin 4, (x.1 = i ∧ y = w i) ∨ (y.1 = i ∧ x = w i)) ∨ (x.1 = 0 ∧ y = (1,1)) ∨ (y.1 = 0 ∧ x = (1,1)) ∨ (x.1 = 3 ∧ y = (0,1)) ∨ (y.1 = 3 ∧ x = (0,1))) ∧ G.CliqueFree 3 ∧ ¬∃ I : Finset (Fin 4 × Fin 2), 4 ≤ I.card ∧ G.IsIndepSet (I : Set (Fin 4 × Fin 2)) := by exact ⟨graph580, w580, hw580, cover580, trianglefree580, nofour580⟩