AFTD Auto-Formalizing Theoretical Domains

path_cut_word_count_cancel

theoremverified

For a four-partition A,B,C,D of the vertices of the path P_n, the total number of edges crossing the cuts defined by A, B, C, D equals the total number crossing the cuts of A ∪ B, A ∪ C and B ∪ C.

Statement

theorem path_cut_word_count_cancel (n : ℕ) (A B C D : Finset (Fin n))
    (hpart : is_four_partition A B C D) :
    (path_cut_word n A).countP id + (path_cut_word n B).countP id +
        (path_cut_word n C).countP id + (path_cut_word n D).countP id =
      (path_cut_word n (A ∪ B)).countP id + (path_cut_word n (A ∪ C)).countP id +
        (path_cut_word n (B ∪ C)).countP id
Source
step towards claw_free_tree_graph_state_mmi
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • path_cut_wordpath_cut_word n S is the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the path pathGraph n (i.e. the…
  • pathCertSignThe signs of the seven terms in the tripartite cut-rank sum.
  • path_cert_word_eq_cut_wordThe Boolean edge word used by the finite-state certificate is the ordinary path cut word of the corresponding color mask.
  • pathCertMaskThe seven party-union masks for a four-color path word.
  • pathCertWordCountCancelAcross a four-color word the signed sum of the seven crossing-edge counts vanishes.
  • is_four_partitionGiven a finite type V with decidable equality and four finite subsets A, B, C, D : Finset V, is_four_partition A B C D is the proposition…
  • pathCertWordThe sequence of cut-crossing flags for one party-union mask along a colored vertex word.
Used by 1
  • path_cut_word_odd_run_ineqFor a four-partition A,B,C,D of the vertices of the path P_n, the sum of the numbers of maximal odd-length crossing runs for A, B, C and D…

The proof, explained

To prove that the crossing-edge counts for a 4-partition A, B, C, D of a path satisfy cut(A) + cut(B) + cut(C) + cut(D) = cut(AB) + cut(AC) + cut(BC), we first show that a set and its complement have identical cut words. Next, we identify D with (A ∪ B ∪ C)ᶜ and assign each vertex a color 0, 1, 2, 3 according to the partition. The crossing-edge counts for the seven candidate sets then reduce via pathCertWordCountCancel to a signed sum that cancels to zero along any colored path.

  1. The cut word of the complement of a set S on a path of length n equals the cut word of S. automation

    Unfolding path_cut_word and applying List.ofFn congruence and function extensionality reduces the equality of cut words to checking each edge. Rewriting with Finset.mem_compl and decide_not converts membership in Sᶜ into the boolean negation of membership in S. An exhaustive check on whether the two endpoints belong to S shows that (!b₁ != !b₂) is identical to (b₁ != b₂).

    lines 5–10

    uses congrArg, Finset.mem_compl, decide_not

      unfold path_cut_word
      apply congrArg List.ofFn
      funext k
      simp only [Finset.mem_compl, decide_not]
      cases (decide ((⟨k.val, by omega⟩ : Fin n) ∈ S)) <;>
        cases (decide ((⟨k.val + 1, by omega⟩ : Fin n) ∈ S)) <;> decide
  2. Unpack the partition hypothesis into pairwise disjointness of A, B, C, D and the fact that their union is the entire vertex set.

    The assumption that A, B, C, D form a 4-partition is destructed into pairwise disjointness of each pair and their covering of the universe.

    lines 19–20

      classical
      rcases hpart with ⟨hAB,hAC,hAD,hBC,hBD,hCD,hall⟩
  3. The fourth set D is the complement of A ∪ B ∪ C.

    Every vertex v lies in A, B, C, or D because their union is the universe. Since D is disjoint from A, B, and C, an element belongs to D if and only if it does not belong to A, B, or C.

    lines 21–39

    uses Finset.mem_union, or_assoc, Finset.disjoint_left.mp, Finset.mem_compl, not_or, False.elim

      have hD : D = (A ∪ B ∪ C)ᶜ := by
        ext v
        have hcover : v ∈ A ∨ v ∈ B ∨ v ∈ C ∨ v ∈ D := by
          have hh : v ∈ A ∪ B ∪ C ∪ D := by rw [hall]; simp
          simpa only [Finset.mem_union, or_assoc] using hh
        have hda := Finset.disjoint_left.mp hAD
        have hdb := Finset.disjoint_left.mp hBD
        have hdc := Finset.disjoint_left.mp hCD
        simp only [Finset.mem_compl, Finset.mem_union, not_or]
        constructor
        · intro hd
          exact ⟨⟨fun ha => hda ha hd, fun hb => hdb hb hd⟩, fun hc => hdc hc hd⟩
        · intro h
          rcases h with ⟨⟨ha,hb⟩,hc⟩
          rcases hcover with ha' | hb' | hc' | hd
          · exact False.elim (ha ha')
          · exact False.elim (hb hb')
          · exact False.elim (hc hc')
          · exact hd
  4. The identity holds vacuously when the path has zero vertices. automation

    When n = 0, the path has no vertices and no edges, so all cut words are empty and both sides evaluate to 0.

    lines 40–41

      cases n with
      | zero => simp [path_cut_word]
  5. For each of the seven certificate indices j ∈ Fin 7, the set of vertices whose color has the corresponding bit set equals the j-th set in the collection ![A, B, C, AB, AC, BC, ABC]. automation

    We define a vertex coloring assigning vertices in A, B, C, D the colors 0, 1, 2, 3 respectively. Case analysis on each of the 7 indices and each vertex's membership in A, B, C shows that testing the bit in pathCertMask j matches membership in the corresponding set.

    lines 42–49

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.disjoint_left

      | succ m =>
        let color : Fin (m+1) → Fin 4 := fun v => if v ∈ A then 0 else if v ∈ B then 1 else if v ∈ C then 2 else 3
        let sets : Fin 7 → Finset (Fin (m+1)) := ![A,B,C,A ∪ B,A ∪ C,B ∪ C,A ∪ B ∪ C]
        have hmask (j : Fin 7) :
            (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) = sets j := by
          fin_cases j <;> ext v : 1 <;> simp only [Finset.mem_filter, Finset.mem_univ, true_and] <;>
            by_cases ha : v ∈ A <;> by_cases hb : v ∈ B <;> by_cases hc : v ∈ C <;>
            simp_all [sets, color, pathCertMask, Finset.disjoint_left] <;> decide
  6. The certificate word for each mask j equals the path cut word for the corresponding set in our collection.

    Applying path_cert_word_eq_cut_word rewrites the path certificate word evaluated on the vertex color sequence into the cut word of the set defined by the mask.

    lines 50–55

    uses path_cert_word_eq_cut_word

        have hm (j : Fin 7) :
            pathCertWord (color ⟨0, by omega⟩)
              (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) j =
              path_cut_word (m+1) (sets j) := by
          rw [← hmask j]
          exact path_cert_word_eq_cut_word (m+1) (by omega) color j
  7. The signed sum of the cut counts of the seven sets is zero.

    We instantiate the combinatorial cancellation lemma pathCertWordCountCancel on the path coloring and rewrite each certificate word into the cut word of the corresponding set.

    lines 56–58

    uses pathCertWordCountCancel

        have hw := pathCertWordCountCancel (color ⟨0, by omega⟩)
          (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩)
        simp_rw [hm] at hw
  8. The cut word of D equals the cut word of A ∪ B ∪ C.

    Since D is the complement of A ∪ B ∪ C, their cut words coincide by cut_word_compl_count_scratch.

    lines 59–62

    uses cut_word_compl_count_scratch, Finset.union_assoc

        have hcomp : path_cut_word (m+1) D = path_cut_word (m+1) (A ∪ B ∪ C) := by
          rw [hD]
          exact cut_word_compl_count_scratch _ _
        simp only [Finset.union_assoc] at hcomp
  9. The crossing count identity follows by rearranging the signed cancellation identity. automation

    Expanding the sum over the 7 indices with their explicit signs (+1 for A, B, C, A ∪ B ∪ C and -1 for A ∪ B, A ∪ C, B ∪ C) and substituting the cut count of D for that of A ∪ B ∪ C, linear integer arithmetic (omega) yields the desired equation.

    lines 63–64

    uses Fin.sum_univ_succ

        simp [Fin.sum_univ_succ, pathCertSign, sets, ← hcomp] at hw
        omega
congrArg
Application of a function respects equality: if a₁ = a₂ then f a₁ = f a₂.
decide_not
The boolean decision of the negation ¬p equals the boolean negation !decide p.
Finset.mem_union
The members of a union A ∪ B are the elements in A or in B.
or_assoc
Disjunction is associative: (A ∨ B) ∨ C is equivalent to A ∨ B ∨ C.
Finset.disjoint_left.mp
If two sets s and t are disjoint, any element of s is not in t.
Finset.disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_compl
An element is in the complement of a set if and only if it is not in the set.
not_or
The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
False.elim
From False, anything follows (principle of explosion).
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal set univ.
true_and
The conjunction True ∧ p simplifies to p.
path_cert_word_eq_cut_word
For any vertex coloring of a path, the cut word of the set of vertices matching a given certificate mask equals the path certificate word.
pathCertWordCountCancel
The signed sum of crossing-edge counts for the seven certificate words along any path of colors is zero.
cut_word_compl_count_scratch
The cut word of the complement of a set S on a path of length n equals the cut word of S.
Finset.union_assoc
Union of finite sets is associative: (s₁ ∪ s₂) ∪ s₃ = s₁ ∪ (s₂ ∪ s₃).
Fin.sum_univ_succ
Splits a sum over Fin (n + 1) into the term at 0 and the sum of the remaining terms.

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 Classical BigOperatorslemma cut_word_compl_count_scratch (n : ℕ) (S : Finset (Fin n)) :    path_cut_word n Sᶜ = path_cut_word n S := by  unfold path_cut_word  apply congrArg List.ofFn  funext k  simp only [Finset.mem_compl, decide_not]  cases (decide ((⟨k.val, by omega⟩ : Fin n) ∈ S)) <;>    cases (decide ((⟨k.val + 1, by omega⟩ : Fin n) ∈ S)) <;> decide/-- Crossing-edge counts of A,B,C,D and of AB,AC,BC agree along a path. -/theorem path_cut_word_count_cancel (n : ℕ) (A B C D : Finset (Fin n))    (hpart : is_four_partition A B C D) :    (path_cut_word n A).countP id + (path_cut_word n B).countP id +        (path_cut_word n C).countP id + (path_cut_word n D).countP id =      (path_cut_word n (A ∪ B)).countP id + (path_cut_word n (A ∪ C)).countP id +        (path_cut_word n (B ∪ C)).countP id := by  classical  rcases hpart with ⟨hAB,hAC,hAD,hBC,hBD,hCD,hall⟩  have hD : D = (A ∪ B ∪ C)ᶜ := by    ext v    have hcover : v ∈ A ∨ v ∈ B ∨ v ∈ C ∨ v ∈ D := by      have hh : v ∈ A ∪ B ∪ C ∪ D := by rw [hall]; simp      simpa only [Finset.mem_union, or_assoc] using hh    have hda := Finset.disjoint_left.mp hAD    have hdb := Finset.disjoint_left.mp hBD    have hdc := Finset.disjoint_left.mp hCD    simp only [Finset.mem_compl, Finset.mem_union, not_or]    constructor    · intro hd      exact ⟨⟨fun ha => hda ha hd, fun hb => hdb hb hd⟩, fun hc => hdc hc hd⟩    · intro h      rcases h with ⟨⟨ha,hb⟩,hc⟩      rcases hcover with ha' | hb' | hc' | hd      · exact False.elim (ha ha')      · exact False.elim (hb hb')      · exact False.elim (hc hc')      · exact hd  cases n with  | zero => simp [path_cut_word]  | succ m =>    let color : Fin (m+1) → Fin 4 := fun v => if v ∈ A then 0 else if v ∈ B then 1 else if v ∈ C then 2 else 3    let sets : Fin 7 → Finset (Fin (m+1)) := ![A,B,C,A ∪ B,A ∪ C,B ∪ C,A ∪ B ∪ C]    have hmask (j : Fin 7) :        (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) = sets j := by      fin_cases j <;> ext v : 1 <;> simp only [Finset.mem_filter, Finset.mem_univ, true_and] <;>        by_cases ha : v ∈ A <;> by_cases hb : v ∈ B <;> by_cases hc : v ∈ C <;>        simp_all [sets, color, pathCertMask, Finset.disjoint_left] <;> decide    have hm (j : Fin 7) :        pathCertWord (color ⟨0, by omega⟩)          (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) j =          path_cut_word (m+1) (sets j) := by      rw [← hmask j]      exact path_cert_word_eq_cut_word (m+1) (by omega) color j    have hw := pathCertWordCountCancel (color ⟨0, by omega⟩)      (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩)    simp_rw [hm] at hw    have hcomp : path_cut_word (m+1) D = path_cut_word (m+1) (A ∪ B ∪ C) := by      rw [hD]      exact cut_word_compl_count_scratch _ _    simp only [Finset.union_assoc] at hcomp    simp [Fin.sum_univ_succ, pathCertSign, sets, ← hcomp] at hw    omega
See it in the graphDiscuss this resultChallenge it