simple_graph_wild_number_le_of_block_cut_condition
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
- simple_graph_wild_number_le_of_is_color_connectingThe wild number is at most the size of any colour-connecting set.
- 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_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- Arena.Reachable.transReachability is transitive.
- Used by 8
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- wild_no_closed_union_of_blocksIf every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of…
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
- wild_number_complete_graph_upper_sub_four_add_parityFor every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c…
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.
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.
γ ⟨s(u, v), by simpa using huv⟩ = γ e) :
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.
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)))
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.
uses
Finset.mem_image.mphave 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]
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.
uses
Finset.mem_image.mp,Finset.mem_sdiff.mp,Finset.mem_image.mpr,Finset.mem_univhave 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
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.
uses
SimpleGraph.Adj.reachable,SimpleGraph.fromEdgeSet_adj,Or.inr,Finset.mem_image.mpr,Finset.mem_sdiff.mpr,Finset.mem_univhave 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⟩
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.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mp,SimpleGraph.fromEdgeSet_adj,Or.inlchange 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))⟩)
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.
uses
congrArg,Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finhave 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]
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.
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_finrefine (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.
- Line 10 contains an inline tactic proof (`by simpa using huv`) within the statement of the hypothesis `hcut`, verifying that the distinct vertices u ≠ v form an edge in the complete graph.
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_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]