AFTD Auto-Formalizing Theoretical Domains

quadripartite_max_wild_number_eq_of_bounds

theoremverified

The maximum wild number equals 2n + 1 as soon as every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1 and some such colouring has wild number exactly 2n + 1.

Statement

theorem quadripartite_max_wild_number_eq_of_bounds (n : ℕ)
    (hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1)
    (hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1) :
    quadripartite_max_wild_number n = 2 * n + 1
Source
step towards quadripartite_minimum_coloring_max_wild_number_eq
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • quadripartite_max_wild_numberThe maximum wild number of the complete equipartite graph K_{n,n,n,n} over all proper edge colorings using exactly 3n colors.
  • simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.

The proof, explained

The maximum wild number is defined as the supremum of the set S of wild numbers achieved by proper (3n)-edge-colourings of K_{n,n,n,n}. For a bounded subset of ℕ, this supremum is the least upper bound. The proof checks that 2n + 1 is an upper bound via the universal bound hypothesis, and that 2n + 1 belongs to S via the existence hypothesis, so by antisymmetry the least upper bound is exactly 2n + 1.

  1. The goal is to show that the supremum of the set S of all wild numbers attained by proper (3n)-edge-colourings of K_{n,n,n,n} is 2n + 1.

    Unfold the definition of quadripartite_max_wild_number and introduce the abbreviation S for the set of wild numbers attained by proper (3n)-edge-colourings of the complete equipartite graph K_{n,n,n,n}.

    lines 8–11

      classical
      unfold quadripartite_max_wild_number
      set S := {k : ℕ | ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
        simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = k}
  2. The set S is bounded above by 2n + 1.

    The hypothesis hU states that every proper (3n)-edge-colouring has wild number at most 2n + 1. Thus every element a ∈ S satisfies a ≤ 2n + 1, giving an upper bound N = 2n + 1.

    lines 12–15

      have hbd : ∃ N, ∀ a ∈ S, a ≤ N := by
        use 2 * n + 1
        rintro a ⟨c, rfl⟩
        exact hU c
  3. The supremum of S is the least upper bound Nat.find hbd.

    Using Nat.sSup_def with the upper bound certificate hbd, the supremum of S in ℕ is by definition the smallest natural number that bounds S from above.

    line 16

    uses Nat.sSup_def

      rw [Nat.sSup_def hbd]
  4. It suffices to show that Nat.find hbd ≤ 2n + 1 and 2n + 1 ≤ Nat.find hbd.

    By antisymmetry of the partial order on ℕ (le_antisymm), equality reduces to the two non-strict inequalities.

    line 17

    uses le_antisymm

      apply le_antisymm
  5. Nat.find hbd ≤ 2n + 1.

    By Nat.find_min', the least upper bound is bounded above by any valid upper bound. Since 2n + 1 is an upper bound for S (by hU), Nat.find hbd ≤ 2n + 1.

    lines 18–20

    uses Nat.find_min'

      · apply Nat.find_min'
        rintro a ⟨c, rfl⟩
        exact hU c
  6. 2n + 1 ≤ Nat.find hbd.

    By hypothesis hE, there exists a colouring c with wild number exactly 2n + 1, so 2n + 1 ∈ S. Because Nat.find hbd is an upper bound for every element of S (Nat.find_spec), 2n + 1 ≤ Nat.find hbd.

    lines 21–23

    uses Nat.find_spec

      · obtain ⟨c, hc⟩ := hE
        have hmem : 2 * n + 1 ∈ S := ⟨c, hc⟩
        exact Nat.find_spec hbd (2 * n + 1) hmem
Nat.sSup_def
for a set of natural numbers with an upper bound, its supremum is defined as the least upper bound, given by the minimal natural number satisfying the upper-bound predicate
le_antisymm
if a ≤ b and b ≤ a in a partial order, then a = b
Nat.find_min'
if a predicate on ℕ holds for m, then the minimal natural number satisfying the predicate is at most m
Nat.find_spec
the minimal natural number found by Nat.find satisfies the defining predicate

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

/-- The maximum wild number is 2n + 1 once the universal upper bound and one attaining colouring are available. -/theorem quadripartite_max_wild_number_eq_of_bounds (n : ℕ)    (hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1)    (hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1) :    quadripartite_max_wild_number n = 2 * n + 1 := by  classical  unfold quadripartite_max_wild_number  set S := {k : ℕ | ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),    simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = k}  have hbd : ∃ N, ∀ a ∈ S, a ≤ N := by    use 2 * n + 1    rintro a ⟨c, rfl⟩    exact hU c  rw [Nat.sSup_def hbd]  apply le_antisymm  · apply Nat.find_min'    rintro a ⟨c, rfl⟩    exact hU c  · obtain ⟨c, hc⟩ := hE    have hmem : 2 * n + 1 ∈ S := ⟨c, hc⟩    exact Nat.find_spec hbd (2 * n + 1) hmem
See it in the graphDiscuss this resultChallenge it