k4_forest_aug
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
- 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 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`.
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`.
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
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.
uses
k4_forest,and_associntro 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)
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.
uses
Finset.mem_filtersimp only [Finset.mem_filter] at he refine ⟨e, he.1, he.2.1, ?_⟩
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.
uses
Bool.and_eq_true,decide_eq_true_eq,bne_iff_ne,ne_eq,k4_foresthave := 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)
- The core combinatorial verification (checking all pairs of sub-forests of K₄) is carried out by Lean's kernel through computational reflection (`decide +kernel`), which evaluates the finite decision procedure directly by reduction rather than through symbolic deductive steps.
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_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