simple_graph_wild_number_le_card_edge_finset
The wild number of a finite connected edge-coloured graph is at most its number of edges.
Statement
theorem simple_graph_wild_number_le_card_edge_finset {V α : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (γ : G.edgeSet → α) (hG : G.Connected) : simple_graph_wild_number G γ ≤ G.edgeFinset.card
- Source
- Sanity lemma for the wild number, arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2.
- 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_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 1
- simple_graph_wild_number_attainedFor any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.
The proof, explained
The wild number of an edge-coloured graph is defined as the minimum cardinality of a color-connecting subset of edges. To show that this minimum is at most the total number of edges |E(G)|, it suffices to exhibit a single color-connecting edge set of size |E(G)|. The proof takes the entire edge set of G as the witness, which trivially has size |E(G)| and is color-connecting because G is connected.
It suffices to exhibit a color-connecting set of edges of size |E(G)|.
By definition, the wild number is the infimum of the cardinalities of all color-connecting edge sets. By Nat.sInf_le, the infimum of a set of natural numbers is bounded above by any element of the set, so it suffices to show that |E(G)| belongs to the set—that is, to show that some color-connecting set of edges has cardinality |E(G)|.
uses
Nat.sInf_leapply Nat.sInf_leThe entire edge set E(G) is color-connecting and has cardinality |E(G)|, completing the proof.
Taking the witness W to be the entire edge set G.edgeFinset, its cardinality is |E(G)| by definition. Using SimpleGraph.coe_edgeFinset to identify G.edgeFinset with the underlying edge set G.edgeSet, the color-connecting requirement is discharged by simple_graph_is_color_connecting_edge_set, which shows that the complete edge set of any connected graph is color-connecting.
uses
SimpleGraph.coe_edgeFinset,simple_graph_is_color_connecting_edge_setexact ⟨G.edgeFinset, rfl, by rw [SimpleGraph.coe_edgeFinset]; exact simple_graph_is_color_connecting_edge_set G γ hG⟩
Nat.sInf_le- The infimum of a set of natural numbers is at most any member of that set.
SimpleGraph.coe_edgeFinset- The coercion of the finite set of edges of a graph to a set equals its edge set.
simple_graph_is_color_connecting_edge_set- The full edge set of a connected graph is color-connecting for any edge colouring.
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 simple_graph_wild_number_le_card_edge_finset {V α : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (γ : G.edgeSet → α) (hG : G.Connected) : simple_graph_wild_number G γ ≤ G.edgeFinset.card := by apply Nat.sInf_le exact ⟨G.edgeFinset, rfl, by rw [SimpleGraph.coe_edgeFinset]; exact simple_graph_is_color_connecting_edge_set G γ hG⟩