path_inter_indep_set_not_subset_of_card_lt
If 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 cannot contain all vertices of W.
Statement
lemma path_inter_indep_set_not_subset_of_card_lt {V : Type*} [DecidableEq V] {G : SimpleGraph V} {u v : V} (p : G.Walk u v) (hp : p.IsPath) (W U : Finset V) (hW : G.IsIndepSet (W : Set V)) (hsub : p.support.toFinset ⊆ W ∪ U) (hcard : U.card + 1 < W.card) : ¬ (W ⊆ p.support.toFinset)
- Source
- arXiv:2611.06362, Section 2.2, Claim 2.2
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- path_inter_indep_set_card_leAlong 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…
Read back from the Lean
Let $V$ be a type with decidable equality, and let $G$ be a simple graph on $V$. For any vertices $u, v \in V$, let $p$ be a walk in $G$ from $u$ to $v$ such that $p$ is a path (i.e., visits no vertex more than once). Let $W$ and $U$ be finite sets of vertices of $V$. If:
1. $W$ is an independent set in $G$ (no two vertices in $W$ are adjacent in $G$),
2. the set of vertices visited by $p$ (p.support.toFinset) is a subset of $W \cup U$, and
3. $|U| + 1 < |W|$,
then $W$ is not a subset of the set of vertices visited by $p$ (¬ (W ⊆ p.support.toFinset)).
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
/-- A simple path supported on W ∪ U cannot contain all of W if W is an independent set and |U| + 1 < |W|. -/ lemma path_inter_indep_set_not_subset_of_card_lt {V : Type*} [DecidableEq V] {G : SimpleGraph V} {u v : V} (p : G.Walk u v) (hp : p.IsPath) (W U : Finset V) (hW : G.IsIndepSet (W : Set V)) (hsub : p.support.toFinset ⊆ W ∪ U) (hcard : U.card + 1 < W.card) : ¬ (W ⊆ p.support.toFinset) := by intro hWsub have h1 := path_inter_indep_set_card_le p hp W hW have h2 : p.support.toFinset ∩ W = W := Finset.inter_eq_right.mpr hWsub have h3 : p.support.toFinset \ W ⊆ U := by intro x hx simp only [Finset.mem_sdiff] at hx have hx_union := hsub hx.1 simp only [Finset.mem_union] at hx_union rcases hx_union with hxW | hxU · exact (hx.2 hxW).elim · exact hxU have h4 : (p.support.toFinset \ W).card ≤ U.card := Finset.card_le_card h3 rw [h2] at h1 omega