AFTD Auto-Formalizing Theoretical Domains

path_inter_indep_set_not_subset_of_card_lt

lemmaverified

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
See it in the graphDiscuss this resultChallenge it