AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_min_uncolorable_monotone

theoremverified

For positive k, the least uncolorable threshold is nondecreasing as k increases.

Statement

theorem bipartite_subset_min_uncolorable_monotone (k : ℕ) (hk : 1 ≤ k) : bipartite_subset_min_uncolorable_r k ≤ bipartite_subset_min_uncolorable_r (k+1)
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_monotone (k : ℕ) (hk : 1 ≤ k) : bipartite_subset_min_uncolorable_r k ≤ bipartite_subset_min_uncolorable_r (k+1) := by
  by_contra! h
  let r := bipartite_subset_min_uncolorable_r (k+1)
  have hc : bipartite_subset_standard_list_colorable k r := (bipartite_subset_colorable_iff_below_threshold k r hk).2 h
  have hcnew := bipartite_subset_colorable_succ k r hk hc
  have hh := (bipartite_subset_colorable_iff_below_threshold (k+1) r (by omega)).1 hcnew
  omega
See it in the graphDiscuss this resultChallenge it