k4_two_forests
If the six edges of K₄ are 2-colored so that both color classes are forests and the opposite pair {01, 23} is split, then the other two opposite pairs are each monochromatic and get different colors.
Statement
theorem k4_two_forests (g : Fin 6 → Bool) (h1 : k4_forest (Finset.univ.filter fun e => g e = true)) (h2 : k4_forest (Finset.univ.filter fun e => g e = false)) (h01 : g 0 ≠ g 1) : g 2 = g 3 ∧ g 4 = g 5 ∧ g 2 ≠ g 4
- Source
- arXiv:2610.07318 (A note on the list chromatic number of two matroids), Claim 2.1 (two complementary 3-edge sets of K₄ are both spanning trees iff exactly one opposite pair is split), in the form used in the proof of 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 1
- matroid_common_list_colorable_two_not_of_colorable_twoThere are two loopless matroids M₁, M₂ on a common finite ground set (M₁ graphic: three disjoint copies of K₄; M₂ a unit-capacity…
The proof, explained
The theorem is proved by finite case exhaustion. Since an edge 2-coloring of $K_4$ is a function $g : \mathrm{Fin}\; 6 \to \mathrm{Bool}$, there are only $2^6 = 64$ possible colorings, making the property entirely decidable. A universal helper lemma (`key`) encoding the forest and split-pair conditions as a boolean predicate is verified by kernel evaluation (`decide +kernel`), and the main theorem then specializes this lemma to $g$ by reflecting the propositional hypotheses into boolean terms.
For any 2-coloring of the six edges of $K_4$, if both color classes satisfy the boolean conditions for being a forest and the opposite edge pair $\{0, 1\}$ is split, then the pair $\{2, 3\}$ is monochromatic, the pair $\{4, 5\}$ is monochromatic, and $\{2, 3\}$ has a different color from $\{4, 5\}$. automation
Because the domain $\mathrm{Fin}\; 6 \to \mathrm{Bool}$ is finite, containing only $2^6 = 64$ functions, the truth of this implication is completely decidable. The kernel evaluates this boolean expression exhaustively across all 64 colorings.
have key : ∀ g : Fin 6 → Bool, (decide ((Finset.univ.filter fun e => g e = true).card ≤ 3) && (Finset.univ.filter fun e => g e = true) != {0, 2, 5} && (Finset.univ.filter fun e => g e = true) != {0, 3, 4} && (Finset.univ.filter fun e => g e = true) != {1, 2, 4} && (Finset.univ.filter fun e => g e = true) != {1, 3, 5}) = true → (decide ((Finset.univ.filter fun e => g e = false).card ≤ 3) && (Finset.univ.filter fun e => g e = false) != {0, 2, 5} && (Finset.univ.filter fun e => g e = false) != {0, 3, 4} && (Finset.univ.filter fun e => g e = false) != {1, 2, 4} && (Finset.univ.filter fun e => g e = false) != {1, 3, 5}) = true → g 0 != g 1 → (g 2 == g 3 && g 4 == g 5 && g 2 != g 4) = true := by decide +kernel
The boolean conclusion $(g(2) == g(3) \;\&\&\; g(4) == g(5) \;\&\&\; g(2) \ne g(4)) = \mathrm{true}$ holds for the specific coloring $g$.
We specialize the universal lemma `key` to the coloring $g$. The three required premises are supplied by our hypotheses $h_1$, $h_2$, and $h_{01}$, rewriting the definition of `k4_forest`, reassociating conjunctions via `and_assoc`, and converting the propositional hypotheses into their equivalent boolean form.
uses
k4_forest,and_assochave := key g (by simpa [k4_forest, and_assoc] using h1) (by simpa [k4_forest, and_assoc] using h2) (by simpa using h01)
$g(2) = g(3) \land g(4) = g(5) \land g(2) \ne g(4)$
We simplify the boolean evaluation $(g(2) == g(3) \;\&\&\; g(4) == g(5) \;\&\&\; g(2) \ne g(4)) = \mathrm{true}$ into the standard propositional conjunction of equalities and disequality.
uses
and_assocsimpa [and_assoc] using this
k4_forest- A set of edges in $K_4$ is a forest if and only if it has at most 3 edges and does not equal any of the four 3-cycles (triangles) $\{0, 2, 5\}$, $\{0, 3, 4\}$, $\{1, 2, 4\}$, or $\{1, 3, 5\}$.
and_assoc- Conjunction of propositions is associative: $(a \land b) \land c \leftrightarrow a \land (b \land c)$.
- The core universal lemma `key` is proved by kernel-level computation (`decide +kernel`), which exhaustively verifies the statement across all $2^6 = 64$ possible edge colorings $g : \mathrm{Fin}\; 6 \to \mathrm{Bool}$ without producing explicit deduction steps for each case.
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.
theorem k4_two_forests (g : Fin 6 → Bool) (h1 : k4_forest (Finset.univ.filter fun e => g e = true)) (h2 : k4_forest (Finset.univ.filter fun e => g e = false)) (h01 : g 0 ≠ g 1) : g 2 = g 3 ∧ g 4 = g 5 ∧ g 2 ≠ g 4 := by have key : ∀ g : Fin 6 → Bool, (decide ((Finset.univ.filter fun e => g e = true).card ≤ 3) && (Finset.univ.filter fun e => g e = true) != {0, 2, 5} && (Finset.univ.filter fun e => g e = true) != {0, 3, 4} && (Finset.univ.filter fun e => g e = true) != {1, 2, 4} && (Finset.univ.filter fun e => g e = true) != {1, 3, 5}) = true → (decide ((Finset.univ.filter fun e => g e = false).card ≤ 3) && (Finset.univ.filter fun e => g e = false) != {0, 2, 5} && (Finset.univ.filter fun e => g e = false) != {0, 3, 4} && (Finset.univ.filter fun e => g e = false) != {1, 2, 4} && (Finset.univ.filter fun e => g e = false) != {1, 3, 5}) = true → g 0 != g 1 → (g 2 == g 3 && g 4 == g 5 && g 2 != g 4) = true := by decide +kernel have := key g (by simpa [k4_forest, and_assoc] using h1) (by simpa [k4_forest, and_assoc] using h2) (by simpa using h01) simpa [and_assoc] using this