wild_number_complete_graph_le_sub_one
For every n ≥ 1 and every edge colouring γ of K_n, wld_γ(K_n) ≤ n − 1 (a spanning star is colour-connecting).
Statement
theorem wild_number_complete_graph_le_sub_one {α : Type*} (n : ℕ) (hn : 1 ≤ n) (γ : (⊤ : SimpleGraph (Fin n)).edgeSet → α) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) γ ≤ n - 1
- Formalizes
- arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2, inequality (1) (0 ≤ wld_γ(G) ≤ n − 1 for an n-vertex connected graph), here for K_n.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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…
- simple_graph_wild_number_le_of_is_color_connectingThe wild number is at most the size of any colour-connecting set.
- Used by 1
- wild_number_complete_three_min_proper_coloring_eqFor every minimum proper edge colouring of K_3, the wild number is 2 = ⌊4⌈3/2⌉/3⌋: the case n = 3 of the conjecture in Sec. 6.
The proof, explained
The proof shows that the wild number of any edge-coloured complete graph K_n (with n ≥ 1) is at most n - 1 by exhibiting an explicit color-connecting set of edges. It chooses an arbitrary vertex z and defines W to be the spanning star centered at z, consisting of the edges {z, j} for all j ≠ z. Because every vertex is directly adjacent to z along an edge in W, the graph containing W (plus any monochromatic edges) is connected, making W color-connecting. The bound follows because the star W contains at most n - 1 edges.
Define a candidate edge set W as the spanning star centered at vertex z = 0.
Since n ≥ 1, the index 0 exists as a vertex z ∈ Fin n. We define W to be the set of unordered pairs {z, j} connecting z to all other vertices j ∈ Fin n with j ≠ z.
classical let z : Fin n := ⟨0, by omega⟩ let W : Finset (Sym2 (Fin n)) := (Finset.univ.erase z).image fun j => s(z, j)
Every pair in W is an edge of the complete graph K_n.
To show W ⊆ (⊤ : SimpleGraph (Fin n)).edgeSet, take any f ∈ W. Unfolding the definition of W via Finset.coe_image, Set.mem_image, Finset.mem_coe, and Finset.mem_erase, f has the form {z, j} for some j ≠ z. Since z ≠ j by Ne.symm, the pair {z, j} connects distinct vertices and is therefore an edge of the complete graph.
uses
Finset.coe_image,Set.mem_image,Finset.mem_coe,Finset.mem_erase,Ne.symmhave hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) γ ↑W := by refine ⟨?_, fun e => ?_⟩ · intro f hf simp only [W, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase] at hf obtain ⟨j, ⟨hj, -⟩, rfl⟩ := hf simpa using Ne.symm hj
For every edge e, the subgraph containing all edges of color γ(e) together with W is connected, so W is color-connecting.
By SimpleGraph.connected_iff_exists_forall_reachable, connectivity reduces to showing that z can reach every vertex y. If y = z, reachability is trivial. If y ≠ z, SimpleGraph.Adj.reachable shows reachability follows from adjacency. By SimpleGraph.fromEdgeSet_adj, adjacency holds because z ≠ y (from Ne.symm) and {z, y} belongs to the allowed edges: choosing the second disjunct via Or.inr, {z, y} ∈ W holds by definition of W (simplified via Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase, Finset.mem_univ, and and_true) because y ≠ z.
uses
SimpleGraph.connected_iff_exists_forall_reachable,SimpleGraph.Adj.reachable,SimpleGraph.fromEdgeSet_adj,Or.inr,Ne.symm,Finset.coe_image,Set.mem_image,Finset.mem_coe,Finset.mem_erase,Finset.mem_univ,and_true· rw [SimpleGraph.connected_iff_exists_forall_reachable] refine ⟨z, fun y => ?_⟩ by_cases hy : y = z · rw [hy] apply SimpleGraph.Adj.reachable rw [SimpleGraph.fromEdgeSet_adj] refine ⟨Or.inr ?_, Ne.symm hy⟩ simp only [W, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase, Finset.mem_univ, and_true] exact ⟨y, hy, rfl⟩
The wild number of K_n under γ is bounded by n - 1.
By simple_graph_wild_number_le_of_is_color_connecting, the wild number is bounded above by |W|. Applying Finset.card_image_le bounds |W| by the size of (Finset.univ.erase z). Finally, removing z from Finset.univ leaves n - 1 elements by Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, and Fintype.card_fin.
uses
simple_graph_wild_number_le_of_is_color_connecting,Finset.card_image_le,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_univ,Fintype.card_finrefine (simple_graph_wild_number_le_of_is_color_connecting _ γ W hW).trans ?_ refine Finset.card_image_le.trans ?_ rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]
and_true- For any proposition p, p ∧ True is equivalent to p.
Finset.card_erase_of_mem- Deleting an element from a finite set containing it decreases the cardinality of the set by 1.
Finset.card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the original finite set.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.coe_image- The set coercion of the image of a finite set under a function equals the image of its set coercion.
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_erase- An element a belongs to s \ {b} if and only if a ≠ b and a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Fintype.card_fin- The finite type Fin n has cardinality n.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Or.inr- From B, one can deduce A ∨ B.
Set.mem_image- An element y is in the image f '' s if and only if there exists x ∈ s such that f x = y.
SimpleGraph.Adj.reachable- Adjacent vertices in a graph are reachable from each other.
SimpleGraph.connected_iff_exists_forall_reachable- A graph is connected if and only if there exists a vertex from which every vertex is reachable.
SimpleGraph.fromEdgeSet_adj- Two vertices v and w are adjacent in the graph induced by edge set s if and only if {v, w} ∈ s and v ≠ w.
simple_graph_wild_number_le_of_is_color_connecting- If a finite edge set W is color-connecting for (G, γ), then the wild number of (G, γ) is at most the cardinality of W.
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.
theorem wild_number_complete_graph_le_sub_one {α : Type*} (n : ℕ) (hn : 1 ≤ n) (γ : (⊤ : SimpleGraph (Fin n)).edgeSet → α) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) γ ≤ n - 1 := by classical let z : Fin n := ⟨0, by omega⟩ let W : Finset (Sym2 (Fin n)) := (Finset.univ.erase z).image fun j => s(z, j) have hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) γ ↑W := by refine ⟨?_, fun e => ?_⟩ · intro f hf simp only [W, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase] at hf obtain ⟨j, ⟨hj, -⟩, rfl⟩ := hf simpa using Ne.symm hj · rw [SimpleGraph.connected_iff_exists_forall_reachable] refine ⟨z, fun y => ?_⟩ by_cases hy : y = z · rw [hy] apply SimpleGraph.Adj.reachable rw [SimpleGraph.fromEdgeSet_adj] refine ⟨Or.inr ?_, Ne.symm hy⟩ simp only [W, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase, Finset.mem_univ, and_true] exact ⟨y, hy, rfl⟩ refine (simple_graph_wild_number_le_of_is_color_connecting _ γ W hW).trans ?_ refine Finset.card_image_le.trans ?_ rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]