AFTD Auto-Formalizing Theoretical Domains

k4_forest_aug

theoremverified

The forests of K₄ satisfy the matroid augmentation axiom.

Statement

set_option maxRecDepth 100000 in
theorem k4_forest_aug : ∀ ⦃I J : Finset (Fin 6)⦄, k4_forest I → k4_forest J → I.card < J.card →
    ∃ e ∈ J, e ∉ I ∧ k4_forest (insert e I)
Source
step towards matroid_common_list_colorable_two_not_of_colorable_two (arXiv:2610.07318 (A note on the list chromatic number of two matroids), Theorem 1.1)
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • k4_forestThe independent sets of the cycle matroid of K₄, with the six edges numbered 01, 23, 02, 13, 03, 12 (so {0,1}, {2,3}, {4,5} are the pairs…
Used by 2

The proof, explained

The theorem proves that the collection of forests in the complete graph K₄ satisfies the matroid augmentation axiom: given two forests I and J with |I| < |J|, there exists an edge e ∈ J \ I such that I ∪ {e} is also a forest. Because K₄ has only 6 edges and 2⁶ = 64 subgraphs, the proof first establishes this property via exhaustive kernel evaluation (`decide +kernel`) over all pairs of edge subsets. It then bridges this computational result back to the mathematical theorem by translating between boolean reflection and the propositional definition of `k4_forest`.

  1. For any pair of subsets of edges satisfying the boolean encoding of forests with |I| < |J|, there exists an edge in J \ I whose addition to I preserves the forest property. automation

    Because K₄ has 6 edges, there are only 2⁶ = 64 edge subsets and 64² = 4096 pairs (I, J). The assertion that every such pair with |I| < |J| has an augmenting edge in J \ I is expressed using decidable boolean operations. Lean's kernel verifies this universal statement by exhaustive finite case evaluation via `decide +kernel`.

    lines 4–10

      have key : ∀ I J : Finset (Fin 6),
          (decide (I.card ≤ 3) && I != {0, 2, 5} && I != {0, 3, 4} && I != {1, 2, 4} && I != {1, 3, 5}) = true →
          (decide (J.card ≤ 3) && J != {0, 2, 5} && J != {0, 3, 4} && J != {1, 2, 4} && J != {1, 3, 5}) = true →
          decide (I.card < J.card) = true →
          (J.filter fun e => e ∉ I ∧ (decide ((insert e I).card ≤ 3) && insert e I != {0, 2, 5} &&
            insert e I != {0, 3, 4} && insert e I != {1, 2, 4} && insert e I != {1, 3, 5}) = true).Nonempty := by
        decide +kernel
  2. Given forests I and J with |I| < |J|, there exists an edge e in the filtered set of augmenting edges.

    We introduce the forests I and J and the hypotheses that they are forests with |I| < |J|. We convert these assumptions from their propositional form to the boolean format expected by `key` using simplification with the definition of `k4_forest` and associativity of conjunction (`and_assoc`). Applying `key` yields an edge e satisfying the augmentation condition.

    lines 11–13

    uses k4_forest, and_assoc

      intro I J hI hJ hlt
      obtain ⟨e, he⟩ := key I J (by simpa [k4_forest, and_assoc] using hI) (by simpa [k4_forest, and_assoc] using hJ)
        (by simpa using hlt)
  3. The edge e satisfies e ∈ J and e ∉ I, leaving only the condition that insert e I is a forest.

    Unfolding membership in the filtered finset via `Finset.mem_filter` decomposes the hypothesis on e into e ∈ J, e ∉ I, and the boolean condition that insert e I is a forest. We supply e, e ∈ J, and e ∉ I to satisfy the existential quantifier and the first two conjuncts of the goal.

    lines 14–15

    uses Finset.mem_filter

      simp only [Finset.mem_filter] at he
      refine ⟨e, he.1, he.2.1, ?_⟩
  4. The augmented set insert e I is a forest. automation

    We isolate the boolean condition asserting that insert e I is a forest and translate its boolean connectives and equality tests into mathematical propositions using `Bool.and_eq_true`, `decide_eq_true_eq`, `bne_iff_ne`, and `ne_eq`. After unfolding the definition of `k4_forest` in the goal, the hypothesis and goal have identical propositional structure, so propositional tautology (`tauto`) finishes the proof.

    lines 16–19

    uses Bool.and_eq_true, decide_eq_true_eq, bne_iff_ne, ne_eq, k4_forest

      have := he.2.2
      simp only [Bool.and_eq_true, decide_eq_true_eq, bne_iff_ne, ne_eq] at this
      simp only [k4_forest]
      tauto
k4_forest
a subset I of edges of K₄ is a forest if |I| ≤ 3 and I does not equal any of the four 3-cycles {0, 2, 5}, {0, 3, 4}, {1, 2, 4}, or {1, 3, 5}
and_assoc
conjunction of propositions is associative: ((a ∧ b) ∧ c) ↔ (a ∧ b ∧ c)
Finset.mem_filter
an element a belongs to filter p s if and only if a ∈ s and p a holds
Bool.and_eq_true
the boolean AND (a && b) equals true if and only if both a = true and b = true
decide_eq_true_eq
the boolean test decide p equals true if and only if the proposition p holds
bne_iff_ne
the boolean inequality test (a != b) equals true if and only if a ≠ b
ne_eq
the inequality a ≠ b is definitionally the negation ¬(a = b)

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

set_option maxRecDepth 100000 intheorem k4_forest_aug : ∀ ⦃I J : Finset (Fin 6)⦄, k4_forest I → k4_forest J → I.card < J.card →    ∃ e ∈ J, e ∉ I ∧ k4_forest (insert e I) := by  have key : ∀ I J : Finset (Fin 6),      (decide (I.card ≤ 3) && I != {0, 2, 5} && I != {0, 3, 4} && I != {1, 2, 4} && I != {1, 3, 5}) = true →      (decide (J.card ≤ 3) && J != {0, 2, 5} && J != {0, 3, 4} && J != {1, 2, 4} && J != {1, 3, 5}) = true →      decide (I.card < J.card) = true →      (J.filter fun e => e ∉ I ∧ (decide ((insert e I).card ≤ 3) && insert e I != {0, 2, 5} &&        insert e I != {0, 3, 4} && insert e I != {1, 2, 4} && insert e I != {1, 3, 5}) = true).Nonempty := by    decide +kernel  intro I J hI hJ hlt  obtain ⟨e, he⟩ := key I J (by simpa [k4_forest, and_assoc] using hI) (by simpa [k4_forest, and_assoc] using hJ)    (by simpa using hlt)  simp only [Finset.mem_filter] at he  refine ⟨e, he.1, he.2.1, ?_⟩  have := he.2.2  simp only [Bool.and_eq_true, decide_eq_true_eq, bne_iff_ne, ne_eq] at this  simp only [k4_forest]  tauto
See it in the graphDiscuss this resultChallenge it