AFTD Auto-Formalizing Theoretical Domains

simple_graph_wild_number_le_of_block_cut_condition

theoremverified

Let a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing every nontrivial cut of the block labels, the wild number is at most n-q. The witness joins every nonroot vertex to its block root.

Statement

theorem simple_graph_wild_number_le_of_block_cut_condition
    {n q : ℕ} {α : Type*} (hn : 0 < n)
    (γ : (⊤ : SimpleGraph (Fin n)).edgeSet → α)
    (p : Fin n → Fin q) (r : Fin q → Fin n)
    (hr : ∀ i, p (r i) = i)
    (hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),
      S.Nonempty → S ≠ Finset.univ →
      ∃ u v : Fin n, ∃ huv : u ≠ v,
        p u ∈ S ∧ p v ∉ S ∧
        γ ⟨s(u, v), by simpa using huv⟩ = γ e) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) γ ≤ n - q
Source
Helper for OP-306 and its proposed permutation-event proof; arXiv:2610.22142, Section 3.3.2, the seal-free block-partition criterion. The hypotheses are stated directly as crossing edges for every block cut; no properness or minimum-color hypothesis is needed for this implication.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 8

The proof, explained

The proof constructs an explicit color-connecting edge set W by connecting each nonroot vertex to the designated root of its block, which requires at most n - q edges. For any edge color, every vertex can reach its block root along edges in W; if the resulting monochromatic subgraph were disconnected, the set of block roots reachable from a vertex would define a nontrivial cut of block labels, contradicting the cut hypothesis. Since W is color-connecting and has size at most n - q, the wild number is bounded above by n - q.

  1. In the cut hypothesis, any pair of distinct vertices forms an edge of the complete graph Kn. automation

    The coloring γ is defined on the edge set of Kn, where edges are pairs of distinct vertices. In the hypothesis hcut, an inline simplification proof shows that u ≠ v (huv) guarantees that s(u, v) belongs to the edge set of the complete graph.

    line 10

            γ ⟨s(u, v), by simpa using huv⟩ = γ e) :
  2. Define the set of block roots and the candidate edge set W joining each nonroot vertex to its block root.

    Working classically, define roots as the image of r, containing the root r(i) for each block i. Then define W as the set of edges {v, r(p(v))} for all vertices v not in roots, connecting each nonroot vertex to the designated root of its block.

    lines 12–15

      classical
      let roots : Finset (Fin n) := Finset.univ.image r
      let W : Finset (Sym2 (Fin n)) :=
        (Finset.univ \ roots).image (fun v => s(v, r (p v)))
  3. Any vertex v distinct from its block root r(p(v)) does not belong to roots.

    If v were in roots, we would have v = r(i) for some block index i. Projecting by p gives p(v) = p(r(i)) = i by the section property hr, so r(p(v)) = r(i) = v. By contraposition, v ≠ r(p(v)) implies v ∉ roots.

    lines 16–20

    uses Finset.mem_image.mp

      have hnonroot : ∀ v : Fin n, v ≠ r (p v) → v ∉ roots := by
        intro v hv hvroot
        obtain ⟨i, -, hi⟩ := Finset.mem_image.mp hvroot
        apply hv
        rw [← hi, hr]
  4. Every pair in W is a valid edge of the complete graph Kn.

    Each element of W has the form {v, r(p(v))} with v ∉ roots. If v were equal to r(p(v)), v would belong to roots, contradiction. Hence v ≠ r(p(v)), which means {v, r(p(v))} is not a self-loop and is an edge of Kn.

    lines 21–28

    uses Finset.mem_image.mp, Finset.mem_sdiff.mp, Finset.mem_image.mpr, Finset.mem_univ

      have hWedge : (↑W : Set (Sym2 (Fin n))) ⊆ (⊤ : SimpleGraph (Fin n)).edgeSet := by
        intro e he
        obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp he
        have hvr : v ≠ r (p v) := by
          intro h
          apply (Finset.mem_sdiff.mp hv).2
          exact Finset.mem_image.mpr ⟨p v, Finset.mem_univ _, h.symm⟩
        simpa using hvr
  5. For any edge e, in the graph H with edges of color γ(e) plus W, every vertex can reach its block root.

    Fix an edge e and consider the graph H whose edges are the monochromatic edges of color γ(e) together with W. For any vertex v, either v = r(p(v)) (so v reaches its root trivially), or v ≠ r(p(v)). In the latter case, v ∉ roots, so {v, r(p(v))} ∈ W ⊆ E(H), meaning v is adjacent to r(p(v)) in H and therefore reachable from it.

    lines 29–43

    uses SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj, Or.inr, Finset.mem_image.mpr, Finset.mem_sdiff.mpr, Finset.mem_univ

      have hWconn : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) γ ↑W := by
        refine ⟨hWedge, ?_⟩
        intro e
        let H : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet
          ({f | ∃ hf : f ∈ (⊤ : SimpleGraph (Fin n)).edgeSet, γ ⟨f, hf⟩ = γ e} ∪ ↑W)
        have hstar : ∀ v : Fin n, H.Reachable v (r (p v)) := by
          intro v
          by_cases hv : v = r (p v)
          · rw [← hv]
          · apply SimpleGraph.Adj.reachable
            change (SimpleGraph.fromEdgeSet _).Adj _ _
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨Or.inr ?_, hv⟩
            exact Finset.mem_image.mpr ⟨v,
              Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, hnonroot v hv⟩, rfl⟩
  6. The graph H is connected, so W is a color-connecting set for γ.

    Since n > 0, the graph is nonempty. Suppose for contradiction that H is disconnected, so some u cannot reach some v. Let S be the set of block indices whose roots u can reach in H. Since u reaches r(p(u)), p(u) ∈ S, making S nonempty. Also p(v) ∉ S (otherwise u would reach r(p(v)) and thus v, contradiction), so S is not all of Fin q. By the block-cut hypothesis hcut, there is an edge {a, b} of color γ(e) crossing the cut (p(a) ∈ S and p(b) ∉ S). Since p(a) ∈ S, u reaches r(p(a)), and a reaches r(p(a)), so u reaches a. Because {a, b} has color γ(e), it is an edge in H, so a is adjacent to b, and b reaches r(p(b)). Thus u reaches r(p(b)), implying p(b) ∈ S, a contradiction.

    lines 44–64

    uses Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_filter.mp, SimpleGraph.fromEdgeSet_adj, Or.inl

        change H.Connected
        haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩
        refine ⟨?_⟩
        intro u v
        by_contra huv
        let S : Finset (Fin q) := Finset.univ.filter (fun i => H.Reachable u (r i))
        have hu : p u ∈ S := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hstar u⟩
        have hv : p v ∉ S := by
          intro h
          exact huv ((Finset.mem_filter.mp h).2.trans (hstar v).symm)
        have hS : S ≠ Finset.univ := by
          intro h
          exact hv (h.symm ▸ Finset.mem_univ (p v))
        obtain ⟨a, b, hab, ha, hb, hc⟩ := hcut e S ⟨p u, hu⟩ hS
        have hua : H.Reachable u a := (Finset.mem_filter.mp ha).2.trans (hstar a).symm
        have habH : H.Adj a b := by
          change (SimpleGraph.fromEdgeSet _).Adj _ _
          rw [SimpleGraph.fromEdgeSet_adj]
          exact ⟨Or.inl ⟨by simpa using hab, hc⟩, hab⟩
        exact hb (Finset.mem_filter.mpr ⟨Finset.mem_univ _,
          hua.trans (habH.reachable.trans (hstar b))⟩)
  7. The root map r is injective, so the number of roots is q.

    If r(i) = r(j), applying p gives i = p(r(i)) = p(r(j)) = j by hr, so r is injective. Therefore, the size of roots is the size of Fin q, which is q.

    lines 65–69

    uses congrArg, Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

      have hinj : Function.Injective r := by
        intro i j hij
        simpa only [hr] using congrArg p hij
      have hroots : roots.card = q := by
        rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]
  8. The wild number of Kn under γ is at most n - q.

    By definition, the wild number is at most the cardinality of any color-connecting set. Since W is the image of the nonroot vertices Fin n \ roots under v ↦ {v, r(p(v))}, its size is at most |Fin n \ roots| = n - q.

    lines 70–74

    uses simple_graph_wild_number_le_of_is_color_connecting, Finset.card_image_le, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Fintype.card_fin

      refine (simple_graph_wild_number_le_of_is_color_connecting _ γ W hWconn).trans ?_
      calc W.card ≤ (Finset.univ \ roots).card := Finset.card_image_le
        _ = n - q := by
          rw [Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ,
            Fintype.card_fin, hroots]
congrArg
Equal inputs to a function yield equal outputs: if a = b then f(a) = f(b).
Finset.card_image_of_injective
The cardinality of the image of a finite set under an injective map equals the cardinality of the domain set.
Finset.card_image_le
The cardinality of the image of a finite set is at most the cardinality of the domain set.
Finset.card_sdiff_of_subset
If A ⊆ B, then the cardinality of B \ A is |B| - |A|.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.mem_filter.mp
An element in a filtered finset satisfies the filtering predicate.
Finset.mem_filter.mpr
If an element belongs to a finset and satisfies a predicate, it belongs to the filtered finset.
Finset.mem_image.mp
An element belongs to the image of a finset under f only if it is the image of some element in the finset.
Finset.mem_image.mpr
If an element belongs to a finset, its image under f belongs to the image finset.
Finset.mem_sdiff.mp
An element in a set difference A \ B belongs to A and does not belong to B.
Finset.mem_sdiff.mpr
If an element belongs to A and does not belong to B, it belongs to A \ B.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.subset_univ
Any finset of elements of a finite type is a subset of the universal finset.
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.
Or.inl
Infers a disjunction A ∨ B from a proof of A.
Or.inr
Infers a disjunction A ∨ B from a proof of B.
simple_graph_wild_number_le_of_is_color_connecting
The wild number of a graph under an edge coloring is at most the cardinality of any color-connecting edge set.
SimpleGraph.Adj.reachable
Adjacent vertices in a graph can reach each other.
SimpleGraph.fromEdgeSet_adj
Two vertices are adjacent in a graph defined from an edge set if and only if the edge between them is in the set and they are distinct.

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_of_block_cut_condition    {n q : ℕ} {α : Type*} (hn : 0 < n)    (γ : (⊤ : SimpleGraph (Fin n)).edgeSet → α)    (p : Fin n → Fin q) (r : Fin q → Fin n)    (hr : ∀ i, p (r i) = i)    (hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),      S.Nonempty → S ≠ Finset.univ →      ∃ u v : Fin n, ∃ huv : u ≠ v,        p u ∈ S ∧ p v ∉ S ∧        γ ⟨s(u, v), by simpa using huv⟩ = γ e) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) γ ≤ n - q := by  classical  let roots : Finset (Fin n) := Finset.univ.image r  let W : Finset (Sym2 (Fin n)) :=    (Finset.univ \ roots).image (fun v => s(v, r (p v)))  have hnonroot : ∀ v : Fin n, v ≠ r (p v) → v ∉ roots := by    intro v hv hvroot    obtain ⟨i, -, hi⟩ := Finset.mem_image.mp hvroot    apply hv    rw [← hi, hr]  have hWedge : (↑W : Set (Sym2 (Fin n))) ⊆ (⊤ : SimpleGraph (Fin n)).edgeSet := by    intro e he    obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp he    have hvr : v ≠ r (p v) := by      intro h      apply (Finset.mem_sdiff.mp hv).2      exact Finset.mem_image.mpr ⟨p v, Finset.mem_univ _, h.symm⟩    simpa using hvr  have hWconn : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) γ ↑W := by    refine ⟨hWedge, ?_⟩    intro e    let H : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet      ({f | ∃ hf : f ∈ (⊤ : SimpleGraph (Fin n)).edgeSet, γ ⟨f, hf⟩ = γ e} ∪ ↑W)    have hstar : ∀ v : Fin n, H.Reachable v (r (p v)) := by      intro v      by_cases hv : v = r (p v)      · rw [← hv]      · apply SimpleGraph.Adj.reachable        change (SimpleGraph.fromEdgeSet _).Adj _ _        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨Or.inr ?_, hv⟩        exact Finset.mem_image.mpr ⟨v,          Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, hnonroot v hv⟩, rfl⟩    change H.Connected    haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩    refine ⟨?_⟩    intro u v    by_contra huv    let S : Finset (Fin q) := Finset.univ.filter (fun i => H.Reachable u (r i))    have hu : p u ∈ S := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hstar u⟩    have hv : p v ∉ S := by      intro h      exact huv ((Finset.mem_filter.mp h).2.trans (hstar v).symm)    have hS : S ≠ Finset.univ := by      intro h      exact hv (h.symm ▸ Finset.mem_univ (p v))    obtain ⟨a, b, hab, ha, hb, hc⟩ := hcut e S ⟨p u, hu⟩ hS    have hua : H.Reachable u a := (Finset.mem_filter.mp ha).2.trans (hstar a).symm    have habH : H.Adj a b := by      change (SimpleGraph.fromEdgeSet _).Adj _ _      rw [SimpleGraph.fromEdgeSet_adj]      exact ⟨Or.inl ⟨by simpa using hab, hc⟩, hab⟩    exact hb (Finset.mem_filter.mpr ⟨Finset.mem_univ _,      hua.trans (habH.reachable.trans (hstar b))⟩)  have hinj : Function.Injective r := by    intro i j hij    simpa only [hr] using congrArg p hij  have hroots : roots.card = q := by    rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]  refine (simple_graph_wild_number_le_of_is_color_connecting _ γ W hWconn).trans ?_  calc W.card ≤ (Finset.univ \ roots).card := Finset.card_image_le    _ = n - q := by      rw [Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ,        Fintype.card_fin, hroots]
See it in the graphDiscuss this resultChallenge it