cycle_alternating_path_selection_isIndepSet
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
- cycle_alternating_path_selection_independentLet 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…
- alternating_path_selected_setFor a simple graph C on vertex type V, a vertex ρ : V, and subsets A and T of the subtype {ρ}ᶜ, alternating_path_selected_set C ρ A T is…
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.
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.
uses
Set.mem_imageintro x hx y hy hxy simp only [Set.mem_image] at hx hy obtain ⟨a, ha, rfl⟩ := hx obtain ⟨b, hb, rfl⟩ := hy
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.
uses
cycle_alternating_path_selection_independentexact 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
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.
/-- 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