path_inter_indep_set_card_le
Along any simple path in a simple graph G, the number of vertices lying in an independent set W is at most the number of vertices not in W plus one.
Statement
lemma path_inter_indep_set_card_le {V : Type*} [DecidableEq V] {G : SimpleGraph V} {u v : V} (p : G.Walk u v) (hp : p.IsPath) (W : Finset V) (hW : G.IsIndepSet (W : Set V)) : (p.support.toFinset ∩ W).card ≤ (p.support.toFinset \ W).card + 1
- Source
- arXiv:2611.06362, Section 2.2, Equation (1)
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- path_inter_indep_set_not_subset_of_card_ltIf a simple path in a simple graph has its vertices contained in W ∪ U, where W is an independent set and |U| + 1 < |W|, then the path…
Read back from the Lean
Let $V$ be a type with decidable equality, $G$ a simple graph on $V$, and $u, v \in V$ vertices. Let $p$ be a walk in $G$ from $u$ to $v$ such that $p$ is a path (p.IsPath, i.e., its vertex support has no duplicate vertices), and let $W$ be a finite set of vertices in $V$ such that $W$ is an independent set in $G$ (no two vertices in $W$ are adjacent in $G$). Then the number of vertices in the support of $p$ that belong to $W$ is at most the number of vertices in the support of $p$ that do not belong to $W$, plus $1$ (i.e., $|(p.\text{support}.\text{toFinset} \cap W)| \le |(p.\text{support}.\text{toFinset} \setminus W)| + 1$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
lemma path_inter_indep_set_card_le_list {α : Type*} [DecidableEq α] (W : Finset α) (l : List α) (hchain : l.IsChain (fun a b => a ∈ W → b ∉ W)) : (l.filter (· ∈ W)).length ≤ (l.filter (· ∉ W)).length + 1 ∧ (∀ a, l.head? = some a → a ∉ W → (l.filter (· ∈ W)).length ≤ (l.filter (· ∉ W)).length) := by induction l with | nil => simp | cons h t ih => obtain ⟨ih1, ih2⟩ := ih hchain.tail by_cases hh : h ∈ W · have hpos : (h :: t).filter (· ∈ W) = h :: (t.filter (· ∈ W)) := List.filter_cons_of_pos (decide_eq_true hh) have hneg : (h :: t).filter (· ∉ W) = t.filter (· ∉ W) := List.filter_cons_of_neg (by simp [hh]) have hhead : ∀ a, (h :: t).head? = some a → a ∉ W → ((h :: t).filter (· ∈ W)).length ≤ ((h :: t).filter (· ∉ W)).length := by intro a ha hna simp only [List.head?_cons, Option.some.injEq] at ha subst ha exact (hna hh).elim have hmain : ((h :: t).filter (· ∈ W)).length ≤ ((h :: t).filter (· ∉ W)).length + 1 := by rw [hpos, hneg, List.length_cons] cases t with | nil => simp | cons b t' => have hrel := hchain.rel hh have hle := ih2 b rfl hrel omega exact ⟨hmain, hhead⟩ · have hneg : (h :: t).filter (· ∈ W) = t.filter (· ∈ W) := List.filter_cons_of_neg (by simp [hh]) have hpos : (h :: t).filter (· ∉ W) = h :: (t.filter (· ∉ W)) := List.filter_cons_of_pos (by simp [hh]) have hhead : ∀ a, (h :: t).head? = some a → a ∉ W → ((h :: t).filter (· ∈ W)).length ≤ ((h :: t).filter (· ∉ W)).length := by intro a ha hna rw [hneg, hpos, List.length_cons] omega have hmain : ((h :: t).filter (· ∈ W)).length ≤ ((h :: t).filter (· ∉ W)).length + 1 := by have := hhead h rfl hh omega exact ⟨hmain, hhead⟩ /-- The intersection of any path's vertex set with an independent set has cardinality at most one more than the remaining vertices of the path. -/ lemma path_inter_indep_set_card_le {V : Type*} [DecidableEq V] {G : SimpleGraph V} {u v : V} (p : G.Walk u v) (hp : p.IsPath) (W : Finset V) (hW : G.IsIndepSet (W : Set V)) : (p.support.toFinset ∩ W).card ≤ (p.support.toFinset \ W).card + 1 := by have hnodup : p.support.Nodup := hp.support_nodup have hchain : p.support.IsChain G.Adj := p.isChain_adj_support have hchain' : p.support.IsChain (fun a b => a ∈ W → b ∉ W) := by apply hchain.imp intro a b hadj ha hb exact hW (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hb) hadj.ne hadj have h_inter : (p.support.toFinset ∩ W).card = (p.support.filter (· ∈ W)).length := by rw [← List.toFinset_card_of_nodup (hnodup.filter _)] congr 1 ext x simp have h_diff : (p.support.toFinset \ W).card = (p.support.filter (· ∉ W)).length := by rw [← List.toFinset_card_of_nodup (hnodup.filter _)] congr 1 ext x simp rw [h_inter, h_diff] exact (path_inter_indep_set_card_le_list W p.support hchain').1