AFTD Auto-Formalizing Theoretical Domains

k4_two_forests

theoremverified

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

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.

  1. 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.

    lines 5–17

      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
  2. 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.

    lines 18–19

    uses k4_forest, and_assoc

      have := key g (by simpa [k4_forest, and_assoc] using h1) (by simpa [k4_forest, and_assoc] using h2)
        (by simpa using h01)
  3. $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.

    line 20

    uses and_assoc

      simpa [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)$.

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

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
See it in the graphDiscuss this resultChallenge it