AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_swap_crossing_card_le_two

theoremverified

For any proper edge coloring of a complete graph, if the image of a vertex cut U under a transposition is closed for color i, at most two ordered color-i edges cross the original cut from U to its complement.

Statement

theorem wild_closed_cut_swap_crossing_card_le_two {n k : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)
    (hclosed : w279_closed c i (U.image (Equiv.swap a b))) :
    ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv =>
      ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧
        c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)).card ≤ 2
Source
Helper for the structural exchange route in the OP-306 campaign on arXiv:2610.22142. This records a cut obstruction or a sufficient test for exchanges, not a new wild-number bound.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

To bound the number of ordered color-i edges crossing from U to its complement by 2, we define a function f to {0, 1} that maps an edge to 0 if it contains the vertex a, and to 1 otherwise. Because the cut swapped by (a b) is closed under color-i edges, every crossing color-i edge is incident to a or b; hence two crossing edges with the same f-value must share an endpoint (both contain a or both contain b). In a properly edge-colored complete graph, two crossing edges cannot share an endpoint at opposite sides of the cut (as that endpoint would be both in and out of U) nor at the same side (which would violate proper coloring at that vertex), so sharing an endpoint forces equality. Thus f is injective, and since its codomain has size 2, there are at most two such crossing edges.

  1. Define the set E of ordered color-i edges crossing from U to its complement, and define a function f : E → {0, 1} indicating incidence to a.

    We let E be the finset of ordered pairs (u, v) such that u ≠ v, u ∈ U, v ∉ U, and the edge {u, v} has color i. We then define f : Fin n × Fin n → Fin 2 by mapping (u, v) to 0 if either u = a or v = a, and to 1 otherwise.

    lines 11–15

    uses wild_kn_mem

      classical
      let E := ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv =>
          ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧
            c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i))
      let f : Fin n × Fin n → Fin 2 := fun uv => if uv.1 = a ∨ uv.2 = a then 0 else 1
  2. To prove f is injective on E, take x, y ∈ E with f(x) = f(y); each edge x and y must be incident to a or b.

    We unpack the assumption that x, y ∈ E satisfy f(x) = f(y). By definition of E, both x and y are ordered pairs of distinct vertices crossing from U to its complement with color i. Applying wild_closed_cut_swap_crossing_incident with the hypothesis that the swapped cut is color-i closed, every such crossing edge must have at least one endpoint in {a, b}.

    lines 16–21

    uses wild_closed_cut_swap_crossing_incident

      have hf : Set.InjOn f (↑E) := by
        intro x hx y hy hxy
        obtain ⟨hxne,hxU,hxnU,hxc⟩ := (Finset.mem_filter.1 hx).2
        obtain ⟨hyne,hyU,hynU,hyc⟩ := (Finset.mem_filter.1 hy).2
        have hxinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed x.1 x.2 hxne hxU hxnU hxc
        have hyinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed y.1 y.2 hyne hyU hynU hyc
  3. The edges x and y either both contain a or both contain b.

    Unfolding the definition of f, if f(x) = f(y) = 0, then both x and y are incident to a (using Or.inl). The mixed cases 0 = 1 and 1 = 0 are ruled out by numerical disequality. If f(x) = f(y) = 1, then neither x nor y is incident to a; since each must be incident to a or b, propositional logic shows that both must be incident to b (using Or.inr).

    lines 22–29

    uses Or.inl, Or.inr

        have common : (x.1 = a ∨ x.2 = a) ∧ (y.1 = a ∨ y.2 = a) ∨
            (x.1 = b ∨ x.2 = b) ∧ (y.1 = b ∨ y.2 = b) := by
          simp only [f] at hxy
          split_ifs at hxy with hxa hya
          · exact Or.inl ⟨hxa,hya⟩
          · norm_num at hxy
          · norm_num at hxy
          · exact Or.inr ⟨by tauto, by tauto⟩
  4. If two crossing edges x, y ∈ E share any endpoint z, then x = y.

    We analyze which component of x and y equals z. If both have first component z (x.1 = y.1 = z), wild_kn_same_color implies x.2 = y.2 since a vertex cannot have two incident edges of color i, so x = y by Prod.ext. If x.1 = z and y.2 = z, then z ∈ U and z ∉ U, which is contradictory and dismissed by False.elim; the symmetric case x.2 = z and y.1 = z is similarly impossible. If both have second component z (x.2 = y.2 = z), by symmetry of edge colors (w279_c_swap) and Ne.symm, wild_kn_same_color again yields x.1 = y.1, so x = y by Prod.ext.

    lines 30–46

    uses wild_kn_same_color, Prod.ext, False.elim, Ne.symm, w279_c_swap

        have hshare : ∀ z, (x.1 = z ∨ x.2 = z) → (y.1 = z ∨ y.2 = z) → x = y := by
          intro z hxz hyz
          rcases hxz with hxz | hxz <;> rcases hyz with hyz | hyz
          · have hfst : x.1 = y.1 := hxz.trans hyz.symm
            have hsnd : x.2 = y.2 := wild_kn_same_color c hxne (by simpa only [← hfst] using hyne)
              (by simpa only [← hfst] using hxc.trans hyc.symm)
            exact Prod.ext hfst hsnd
          · exact False.elim (hynU (hyz.symm ▸ hxz ▸ hxU))
          · exact False.elim (hxnU (hxz.symm ▸ hyz ▸ hyU))
          · have hsnd : x.2 = y.2 := hxz.trans hyz.symm
            have hfst : x.1 = y.1 := wild_kn_same_color c (Ne.symm hxne)
              (by simpa only [← hsnd] using Ne.symm hyne)
              (by
                have hxcol := (w279_c_swap c (Ne.symm hxne)).trans hxc
                have hycol := (w279_c_swap c (Ne.symm hyne)).trans hyc
                simpa only [← hsnd] using hxcol.trans hycol.symm)
            exact Prod.ext hfst hsnd
  5. The map f is injective on E.

    From the fact that x and y either both contain a or both contain b, we instantiate the sharing lemma with z = a or z = b respectively, showing that x = y in either case.

    lines 47–49

        rcases common with ⟨hx,hy⟩ | ⟨hx,hy⟩
        · exact hshare a hx hy
        · exact hshare b hx hy
  6. The number of crossing color-i edges is at most 2.

    Since f : E → Fin 2 is injective on E and maps into Finset.univ (by Finset.mem_univ), Finset.card_le_card_of_injOn bounds the cardinality of E by the size of Finset.univ. Applying Finset.card_univ and Fintype.card_fin, the size of Fin 2 is 2, which completes the proof.

    lines 50–51

    uses Finset.card_le_card_of_injOn, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      have hc := Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_univ _) hf
      simpa only [Finset.card_univ,Fintype.card_fin] using hc
wild_kn_mem
In a complete graph, any pair of distinct vertices forms an edge.
wild_closed_cut_swap_crossing_incident
If the cut obtained by swapping vertices a and b is closed under color-i edges, then every edge crossing the original cut with color i has at least one endpoint in {a, b}.
Or.inl
The left introduction rule for disjunction: if P holds, then P ∨ Q holds.
Or.inr
The right introduction rule for disjunction: if Q holds, then P ∨ Q holds.
wild_kn_same_color
In a properly edge-colored complete graph, if two edges incident to a vertex u have the same color, their other endpoints must be equal.
Prod.ext
Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
False.elim
From a contradiction (False), any proposition follows (principle of explosion).
Ne.symm
Inequality is symmetric: if u ≠ v, then v ≠ u.
w279_c_swap
The color of an edge is invariant under swapping the order of its endpoints.
Finset.card_le_card_of_injOn
If a function between finite sets is injective on a subset, the cardinality of the domain subset is at most that of the codomain.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The standard finite type Fin n has cardinality n.

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

open scoped Classicalset_option maxHeartbeats 1000000theorem wild_closed_cut_swap_crossing_card_le_two {n k : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)    (hclosed : w279_closed c i (U.image (Equiv.swap a b))) :    ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv =>      ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧        c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)).card ≤ 2 := by  classical  let E := ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv =>      ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧        c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i))  let f : Fin n × Fin n → Fin 2 := fun uv => if uv.1 = a ∨ uv.2 = a then 0 else 1  have hf : Set.InjOn f (↑E) := by    intro x hx y hy hxy    obtain ⟨hxne,hxU,hxnU,hxc⟩ := (Finset.mem_filter.1 hx).2    obtain ⟨hyne,hyU,hynU,hyc⟩ := (Finset.mem_filter.1 hy).2    have hxinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed x.1 x.2 hxne hxU hxnU hxc    have hyinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed y.1 y.2 hyne hyU hynU hyc    have common : (x.1 = a ∨ x.2 = a) ∧ (y.1 = a ∨ y.2 = a) ∨        (x.1 = b ∨ x.2 = b) ∧ (y.1 = b ∨ y.2 = b) := by      simp only [f] at hxy      split_ifs at hxy with hxa hya      · exact Or.inl ⟨hxa,hya⟩      · norm_num at hxy      · norm_num at hxy      · exact Or.inr ⟨by tauto, by tauto⟩    have hshare : ∀ z, (x.1 = z ∨ x.2 = z) → (y.1 = z ∨ y.2 = z) → x = y := by      intro z hxz hyz      rcases hxz with hxz | hxz <;> rcases hyz with hyz | hyz      · have hfst : x.1 = y.1 := hxz.trans hyz.symm        have hsnd : x.2 = y.2 := wild_kn_same_color c hxne (by simpa only [← hfst] using hyne)          (by simpa only [← hfst] using hxc.trans hyc.symm)        exact Prod.ext hfst hsnd      · exact False.elim (hynU (hyz.symm ▸ hxz ▸ hxU))      · exact False.elim (hxnU (hxz.symm ▸ hyz ▸ hyU))      · have hsnd : x.2 = y.2 := hxz.trans hyz.symm        have hfst : x.1 = y.1 := wild_kn_same_color c (Ne.symm hxne)          (by simpa only [← hsnd] using Ne.symm hyne)          (by            have hxcol := (w279_c_swap c (Ne.symm hxne)).trans hxc            have hycol := (w279_c_swap c (Ne.symm hyne)).trans hyc            simpa only [← hsnd] using hxcol.trans hycol.symm)        exact Prod.ext hfst hsnd    rcases common with ⟨hx,hy⟩ | ⟨hx,hy⟩    · exact hshare a hx hy    · exact hshare b hx hy  have hc := Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_univ _) hf  simpa only [Finset.card_univ,Fintype.card_fin] using hc
See it in the graphDiscuss this resultChallenge it