simple_graph_wild_number_attained
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
- simple_graph_wild_number_le_card_edge_finsetThe wild number of a finite connected edge-coloured graph is at most its number of edges.
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- simple_graph_is_color_connecting_edge_setIn a connected edge-coloured graph, the whole edge set is colour-connecting.
- simple_graph_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
- Used by 2
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- quadripartite_exists_wild_number_eq_of_upper_exclusionIf every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1, and some colouring has no colour-connecting set of at…
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.
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.
uses
SimpleGraph.coe_edgeFinset,simple_graph_is_color_connecting_edge_setclassical 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
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.
uses
Nat.sInf_memexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩)