path_cut_word_count_cancel
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_word
path_cut_word n Sis the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the pathpathGraph 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.
- path_cut_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.
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₂).
uses
congrArg,Finset.mem_compl,decide_notunfold 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
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.
classical rcases hpart with ⟨hAB,hAC,hAD,hBC,hBD,hCD,hall⟩
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.
uses
Finset.mem_union,or_assoc,Finset.disjoint_left.mp,Finset.mem_compl,not_or,False.elimhave 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
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.
cases n with | zero => simp [path_cut_word]
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.
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] <;> decideThe 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.
uses
path_cert_word_eq_cut_wordhave 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
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.
uses
pathCertWordCountCancelhave 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
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.
uses
cut_word_compl_count_scratch,Finset.union_assochave 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
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.
uses
Fin.sum_univ_succsimp [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.
- The helper lemma cut_word_compl_count_scratch (lines 3–10) establishes that taking the complement of a vertex set preserves the cut word along a path, which is used later to substitute the cut of D for that of A ∪ B ∪ C.
- The inductive/combinatorial cancellation for n ≥ 1 is delegated to the library lemma pathCertWordCountCancel, which checks that for every individual edge, the crossing count difference is zero under all possible 4-colorings of its endpoints.
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.
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