AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_graph_le_sub_one

theoremverifiedformalization

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

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.

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

    lines 4–6

      classical
      let z : Fin n := ⟨0, by omega⟩
      let W : Finset (Sym2 (Fin n)) := (Finset.univ.erase z).image fun j => s(z, j)
  2. 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.

    lines 7–12

    uses Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_erase, Ne.symm

      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
  3. 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.

    lines 13–22

    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⟩
  4. 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.

    lines 23–25

    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_fin

      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]
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

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