AFTD Auto-Formalizing Theoretical Domains

two_extra_fork_subgraph_counterexample

theoremverified

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.

  1. 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.

    lines 14–15

      symm := ⟨by intro x y h; exact ⟨h.1.symm, h.2.symm⟩⟩
      loopless := ⟨by intro x h; exact h.1 rfl⟩
  2. 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.

    line 21

    theorem hw580 : ∀ i, (w580 i).1 ≠ i := by decide
  3. 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).

    line 26

        (x.1 = 3 ∧ y = (0,1)) ∨ (y.1 = 3 ∧ x = (0,1)) := by decide
  4. 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.

    line 30

      decide
  5. The 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.

    lines 33–38

    uses SimpleGraph.isNClique_iff, Finset.card_eq_three.mp, notriangle580

      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)
  6. 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.

    lines 41–45

    uses Fintype.sum_prod_type, Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero

      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
  7. 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.

    lines 46–75

      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)
  8. 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.

    lines 76–84

      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
  9. 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.

    line 95

    uses hw580, cover580, trianglefree580, nofour580

      exact ⟨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.

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

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⟩
See it in the graphDiscuss this resultChallenge it