AFTD Auto-Formalizing Theoretical Domains

simple_graph_wild_number_le_card_edge_finset

theoremverified

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
Used by 1

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.

  1. 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)|.

    line 4

    uses Nat.sInf_le

      apply Nat.sInf_le
  2. The 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.

    lines 5–6

    uses SimpleGraph.coe_edgeFinset, simple_graph_is_color_connecting_edge_set

      exact ⟨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

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⟩
See it in the graphDiscuss this resultChallenge it