AFTD Auto-Formalizing Theoretical Domains

alternating_path_selected_subset_b_indep

theoremverified

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

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.

  1. 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`).

    lines 7–9

      intro u hu v hv hadj
      have huB : u ∈ B := hT hu
      have hvB : v ∈ B := hT hv
  2. 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.

    lines 10–12

    uses Set.disjoint_left.mp, Set.disjoint_right.mp

      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
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.

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

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