k4_forest_subset
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
- k4_cycle_matroid_indepA set of edges is independent in M(K₄) exactly when it is a forest.
- k4_cycle_matroidThe cycle matroid M(K₄) on the six edges of K₄.
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.
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.
decide +kernel
- The proof is carried out entirely by exhaustive finite verification (`decide +kernel`) rather than by symbolic reasoning: Lean checks all pairs of subsets of the 6 edges by direct computation in its 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
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.
set_option maxRecDepth 100000 intheorem k4_forest_subset : ∀ ⦃I J : Finset (Fin 6)⦄, k4_forest J → I ⊆ J → k4_forest I := by decide +kernel