AFTD Auto-Formalizing Theoretical Domains

cycle_alternating_path_selection_isIndepSet

theoremverified

Let C be a simple graph on vertex type V and ρ : V a vertex such that (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B holds for subsets A, B of the subtype {ρ}ᶜ. For any subset T ⊆ B, the image under Subtype.val of the alternating path selected set alternating_path_selected_set C ρ A T is an independent set in C (that is, C.IsIndepSet (Subtype.val '' alternating_path_selected_set C ρ A T)).

Statement

theorem cycle_alternating_path_selection_isIndepSet {V : Type*} (C : SimpleGraph V) (ρ : V)
    (A B : Set ({ρ}ᶜ : Set V))
    (h_bip : (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B)
    (T : Set ({ρ}ᶜ : Set V)) (hT : T ⊆ B) :
    C.IsIndepSet (Subtype.val '' alternating_path_selected_set C ρ A T)
Source
arXiv:2611.06985 Lemma 3.3
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

Let $V$ be a type, $C$ be a simple graph on $V$, and $\rho \in V$ be a vertex. Let $\{ρ\}^c$ denote the subtype of vertices in $V$ distinct from $\rho$. Let $A$ and $B$ be subsets of $\{ρ\}^c$. Assume that the induced subgraph of $C$ on $\{ρ\}^c$ is bipartite with parts $A$ and $B$. Let $T$ be a subset of $\{ρ\}^c$ such that $T \subseteq B$. Then the image under the subtype inclusion $\text{Subtype.val} : \{ρ\}^c \to V$ of the set $\text{alternating\_path\_selected\_set}(C, \rho, A, T)$ is an independent set in $C$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof reduces the independence of the image set in C to the pairwise non-adjacency of elements in the alternating path selected set. Unfolding the definition of an independent set and characterizing the image under the subtype inclusion, any two distinct vertices in the image are the embeddings of vertices a and b from the alternating path selected set. The non-adjacency of a and b in C then follows immediately from the previously established lemma cycle_alternating_path_selection_independent.

  1. It suffices to show that any two vertices a, b in the alternating path selected set are non-adjacent in C.

    To show that the image is an independent set in C, let x and y be distinct vertices in the image of the alternating path selected set under the subtype embedding. By the definition of the image of a set (Set.mem_image), x and y are the images of some elements a and b in the alternating path selected set. This reduces the problem to showing that a and b are not adjacent in C.

    lines 7–10

    uses Set.mem_image

      intro x hx y hy hxy
      simp only [Set.mem_image] at hx hy
      obtain ⟨a, ha, rfl⟩ := hx
      obtain ⟨b, hb, rfl⟩ := hy
  2. Vertices a and b are not adjacent in C (¬ C.Adj a b).

    This is precisely the conclusion of cycle_alternating_path_selection_independent, which states that no two vertices in the alternating path selected set are adjacent in C.

    line 11

    uses cycle_alternating_path_selection_independent

      exact cycle_alternating_path_selection_independent C ρ A B h_bip T hT a ha b hb
Set.mem_image
An element y belongs to the image f '' s of a set s under a function f if and only if there exists some x ∈ s such that f x = y.
cycle_alternating_path_selection_independent
In a graph C where the induced subgraph on {ρ}ᶜ is bipartite with parts A and B, for any T ⊆ B, any two vertices in the alternating path selected set are non-adjacent in C.

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

/-- The image of the alternating path selected set S in V is an independent set of C in the sense of SimpleGraph.IsIndepSet. -/theorem cycle_alternating_path_selection_isIndepSet {V : Type*} (C : SimpleGraph V) (ρ : V)    (A B : Set ({ρ}ᶜ : Set V))    (h_bip : (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B)    (T : Set ({ρ}ᶜ : Set V)) (hT : T ⊆ B) :    C.IsIndepSet (Subtype.val '' alternating_path_selected_set C ρ A T) := by  intro x hx y hy hxy  simp only [Set.mem_image] at hx hy  obtain ⟨a, ha, rfl⟩ := hx  obtain ⟨b, hb, rfl⟩ := hy  exact cycle_alternating_path_selection_independent C ρ A B h_bip T hT a ha b hb
See it in the graphDiscuss this resultChallenge it