AFTD Auto-Formalizing Theoretical Domains

simple_graph_wild_number_attained

theoremverified

For any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.

Statement

theorem simple_graph_wild_number_attained {V α : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (γ : G.edgeSet → α) (hG : G.Connected) :
    ∃ W : Finset (Sym2 V), W.card = simple_graph_wild_number G γ ∧
      simple_graph_is_color_connecting G γ ↑W
Source
Structural necessity and certificate-soundness helpers for the OP-306 campaign; arXiv:2610.22142, Sections 3.3.1 and 3.3.2. These make the optimal block-partition route an equivalence at every odd order; no new exact wild-number case or bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 2

The proof, explained

By definition, the wild number of an edge-colored graph is the infimum of the cardinalities of all finite color-connecting edge sets. Because the graph is connected, its full edge set is color-connecting, showing that the set of such cardinalities is nonempty. By the well-ordering principle for natural numbers (Nat.sInf_mem), this infimum is in the set, so some finite color-connecting edge set achieves the wild number as its cardinality.

  1. The entire edge set of G, viewed as a finite set of edges, is color-connecting.

    Working in classical logic, we show that the finite edge set G.edgeFinset is color-connecting. By rewriting with SimpleGraph.coe_edgeFinset, the finite set coercion equals G.edgeSet, and the full edge set is color-connecting by simple_graph_is_color_connecting_edge_set because G is connected.

    lines 9–12

    uses SimpleGraph.coe_edgeFinset, simple_graph_is_color_connecting_edge_set

      classical
      have he : simple_graph_is_color_connecting G γ (↑G.edgeFinset : Set (Sym2 V)) := by
        rw [SimpleGraph.coe_edgeFinset]
        exact simple_graph_is_color_connecting_edge_set G γ hG
  2. There exists a finite edge set W whose cardinality is the wild number of G and which is color-connecting.

    The wild number of G is defined as the infimum of the set of sizes of all finite color-connecting edge sets. Because G.edgeFinset is color-connecting, this set of sizes is nonempty. By the well-ordering principle on ℕ (Nat.sInf_mem), a nonempty set of natural numbers contains its infimum, meaning that some finite color-connecting edge set achieves this minimum cardinality.

    lines 13–14

    uses Nat.sInf_mem

      exact Nat.sInf_mem (show {j | ∃ W : Finset (Sym2 V), W.card = j ∧ simple_graph_is_color_connecting G γ ↑W}.Nonempty from
        ⟨G.edgeFinset.card,G.edgeFinset,rfl,he⟩)
SimpleGraph.coe_edgeFinset
The set coercion of a graph's finite edge set G.edgeFinset is its edge set G.edgeSet.
simple_graph_is_color_connecting_edge_set
For any connected edge-colored graph, its entire edge set is color-connecting.
Nat.sInf_mem
Every nonempty set of natural numbers contains its infimum (minimum).

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

open scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem simple_graph_wild_number_attained {V α : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (γ : G.edgeSet → α) (hG : G.Connected) :    ∃ W : Finset (Sym2 V), W.card = simple_graph_wild_number G γ ∧      simple_graph_is_color_connecting G γ ↑W := by  classical  have he : simple_graph_is_color_connecting G γ (↑G.edgeFinset : Set (Sym2 V)) := by    rw [SimpleGraph.coe_edgeFinset]    exact simple_graph_is_color_connecting_edge_set G γ hG  exact Nat.sInf_mem (show {j | ∃ W : Finset (Sym2 V), W.card = j ∧ simple_graph_is_color_connecting G γ ↑W}.Nonempty from    ⟨G.edgeFinset.card,G.edgeFinset,rfl,he⟩)
See it in the graphDiscuss this resultChallenge it