AFTD Auto-Formalizing Theoretical Domains

k4_forest_subset

theoremverified

Subsets of forests of K₄ are forests.

Statement

set_option maxRecDepth 100000 in
theorem k4_forest_subset : ∀ ⦃I J : Finset (Fin 6)⦄, k4_forest J → I ⊆ J → k4_forest 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 states that the hereditary property holds for forests of the complete graph K₄: any subset of edges of a forest is again a forest. Because the edge set of K₄ consists of only 6 edges, the domain of subsets is finite (64 subsets in total). The statement is proved by exhaustive case evaluation performed directly by Lean's kernel.

  1. For all subsets I, J ⊆ Fin 6, if J is a forest in K₄ and I ⊆ J, then I is also a forest in K₄. automation

    Because the edge set of K₄ has size 6, there are only 2⁶ = 64 possible edge subsets. The property `k4_forest` and the subset relation are decidable, so the universal statement over all pairs of subsets is decided by finite exhaustive evaluation directly inside the Lean kernel.

    line 3

      decide +kernel

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_subset : ∀ ⦃I J : Finset (Fin 6)⦄, k4_forest J → I ⊆ J → k4_forest I := by  decide +kernel
See it in the graphDiscuss this resultChallenge it