alternating_path_selected_subset_b_indep
If the induced graph C[{ρ}ᶜ] is bipartite with parts A and B, then any subset T ⊆ B is an independent set in C[{ρ}ᶜ].
Statement
theorem alternating_path_selected_subset_b_indep {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) : ∀ u ∈ T, ∀ v ∈ T, ¬ (C.induce ({ρ}ᶜ : Set V)).Adj u v
- Source
- arXiv:2611.06985 Lemma 3.3 proof step 2
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- 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…
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 $A$ and $B$ be subsets of the vertex set of the subgraph of $C$ induced by $\{\rho\}^c = V \setminus \{\rho\}$. Assume that this induced subgraph $C[V \setminus \{\rho\}]$ is bipartite with parts $A$ and $B$ ((C.induce {ρ}ᶜ).IsBipartiteWith A B). Let $T$ be a subset of the vertex set of $C[V \setminus \{\rho\}]$ such that $T \subseteq B$. Then for all $u \in T$ and all $v \in T$, $u$ and $v$ are not adjacent in the induced subgraph $C[V \setminus \{\rho\}]$ (that is, $T$ is an independent set in $C[V \setminus \{\rho\}]$).
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
To show that any subset $T \subseteq B$ is independent in the induced subgraph $C[\{\rho\}^c]$, we suppose for contradiction that some pair of vertices $u, v \in T$ are adjacent. Since $T \subseteq B$, both $u$ and $v$ belong to the part $B$. But by definition of a bipartite graph, every edge must connect a vertex in $A$ to a vertex in $B$, forcing one of the two vertices to also lie in $A$. This contradicts the assumption that $A$ and $B$ are disjoint.
Assuming two vertices $u, v \in T$ are adjacent, both $u$ and $v$ must belong to the bipartite part $B$.
To show that no two vertices in $T$ are adjacent, we assume for contradiction that some $u, v \in T$ are adjacent in the induced subgraph $C[\{\rho\}^c]$ (`hadj`). Since $T \subseteq B$ by assumption (`hT`), both $u$ and $v$ belong to $B$ (`huB`, `hvB`).
intro u hu v hv hadj have huB : u ∈ B := hT hu have hvB : v ∈ B := hT hv
The adjacency of $u$ and $v$ contradicts the bipartiteness of $C[\{\rho\}^c]$, so $T$ is an independent set.
By the definition of a bipartite graph (`h_bip.mem_of_adj`), any edge must connect a vertex in $A$ to a vertex in $B$. Thus the edge between $u$ and $v$ leaves two possibilities: either $u \in A$, or $v \in A$. In the first case, $u \in A$ and $u \in B$ contradict the disjointness of $A$ and $B$ via `Set.disjoint_left.mp`. In the second case, $v \in B$ and $v \in A$ contradict disjointness via `Set.disjoint_right.mp`. Both cases yield a contradiction, completing the proof.
uses
Set.disjoint_left.mp,Set.disjoint_right.mprcases h_bip.mem_of_adj hadj with ⟨huA, -⟩ | ⟨-, hvA⟩ · exact Set.disjoint_left.mp h_bip.disjoint huA huB · exact Set.disjoint_right.mp h_bip.disjoint hvB hvA
Set.disjoint_left.mp- If two sets are disjoint, any element of the first set does not belong to the second set.
Set.disjoint_right.mp- If two sets are disjoint, any element of the second set does not belong to the first set.
- The vertices in the induced subgraph $C[\{\rho\}^c]$ are formally terms of the subtype $\{\rho\}^c$, representing vertices in $V$ other than $\rho$.
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.
/-- In a bipartite graph on {ρ}ᶜ with parts A and B, any subset T ⊆ B is an independent set. -/theorem alternating_path_selected_subset_b_indep {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) : ∀ u ∈ T, ∀ v ∈ T, ¬ (C.induce ({ρ}ᶜ : Set V)).Adj u v := by intro u hu v hv hadj have huB : u ∈ B := hT hu have hvB : v ∈ B := hT hv rcases h_bip.mem_of_adj hadj with ⟨huA, -⟩ | ⟨-, hvA⟩ · exact Set.disjoint_left.mp h_bip.disjoint huA huB · exact Set.disjoint_right.mp h_bip.disjoint hvB hvA