AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_min_uncolorable_ge_three

theoremverified

For every k at least 5, the least uncolorable threshold is at least 3.

Statement

theorem bipartite_subset_min_uncolorable_ge_three (k : ℕ) (hk : 5 ≤ k) : 3 ≤ bipartite_subset_min_uncolorable_r k
Source
A direct consequence of the list-coloring construction for OP-861, arXiv:2610.42094.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Lean source view module on GitHub

theorem bipartite_subset_min_uncolorable_ge_three (k : ℕ) (hk : 5 ≤ k) : 3 ≤ bipartite_subset_min_uncolorable_r k := by
  have h := (bipartite_subset_colorable_iff_below_threshold k 2 (by omega)).1 (bipartite_subset_colorable_two_from_five k hk)
  omega
See it in the graphDiscuss this resultChallenge it