component_transversal_exchange_iff
Let T be a transversal of the connected components of a simple graph G, meaning that T intersects every connected component of G and contains at most one vertex per component. For any v ∈ T and any vertex v', the swapped set (T \ {v}) ∪ {v'} intersects every connected component of G if and only if v and v' are in the same connected component of G.
Statement
theorem component_transversal_exchange_iff {V : Type*} (G : SimpleGraph V) (T : Set V) (h_cov : ∀ v : V, ∃ t ∈ T, G.Reachable v t) (h_uniq : ∀ ⦃t1 t2⦄, t1 ∈ T → t2 ∈ T → G.Reachable t1 t2 → t1 = t2) (v v' : V) (hv : v ∈ T) : (∀ u : V, ∃ t ∈ (T \ {v}) ∪ {v'}, G.Reachable u t) ↔ G.Reachable v v'
- Source
- arXiv:2611.06626 Claim 2.5
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Arena.Reachable.transReachability is transitive.
Read back from the Lean
Let $V$ be a type, $G$ be a simple graph on $V$, and $T \subseteq V$ be a set of vertices such that:
1. (h_cov) For every $v \in V$, there exists some $t \in T$ such that $v$ is reachable from $t$ in $G$ (i.e., G.Reachable v t).
2. (h_uniq) For all $t_1, t_2 \in T$, if $t_1$ and $t_2$ are reachable from each other in $G$ (G.Reachable t1 t2), then $t_1 = t_2$.
Let $v, v' \in V$ with $v \in T$ (hv).
Then, every vertex $u \in V$ can reach some vertex in $(T \setminus \{v\}) \cup \{v'\}$ (that is, $\forall u \in V, \exists t \in (T \setminus \{v\}) \cup \{v'\}, G.\text{Reachable } u\ t$) if and only if $v$ and $v'$ are reachable from each other in $G$ ($G.\text{Reachable } v\ v'$).
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 proceeds by showing both directions of the equivalence. For the forward direction, assuming the swapped set covers all components, applying coverage to v yields a witness that cannot lie in T \ {v} without violating the uniqueness of transversal representatives, forcing it to be v' and hence showing that v can reach v'. Conversely, assuming v can reach v', any vertex u represented by some t ≠ v in T still reaches t in the swapped set, whereas any u represented by v can reach v' by path transitivity.
The equivalence reduces to proving two implications: the swapped set covers all components only if v can reach v', and reachability between v and v' implies that the swapped set covers all components.
We split the if-and-only-if statement into the forward direction (coverage implies reachability) and the reverse direction (reachability implies coverage).
constructorAssuming the swapped set covers all components, applying coverage to v yields a witness t reachable from v that is either in T \ {v} or equals v'.
Assume the hypothesis that (T \ {v}) ∪ {v'} intersects every component (hypothesis h). Evaluating this coverage at u = v yields a vertex t ∈ (T \ {v}) ∪ {v'} reachable from v. By definition of the union, either t ∈ T \ {v} or t = v'.
· intro h obtain ⟨t, ht, hr⟩ := h v rcases ht with ⟨htT, htv⟩ | rfl
The case t ∈ T \ {v} is impossible because it violates the uniqueness of transversal representatives.
If t ∈ T \ {v}, then both v and t belong to T, and v can reach t. By the hypothesis that T contains at most one vertex per connected component (h_uniq), this requires v = t. But t ∈ T \ {v} means t ∉ {v}, which contradicts v = t via Set.mem_singleton_iff.mpr.
uses
Set.mem_singleton_iff.mpr· exfalso have heq := h_uniq hv htT hr exact htv (Set.mem_singleton_iff.mpr heq.symm)
In the remaining case t = v', v can reach v'.
Since t = v' and v can reach t, v can reach v', completing the forward direction.
· exact hrConversely, assuming v can reach v', any vertex u has a representative t ∈ T, which either equals v or does not.
Assume v can reach v' (hypothesis hvv') and consider an arbitrary vertex u. By the component coverage property of T (h_cov), there exists some representative t ∈ T reachable from u. We split into cases depending on whether t = v.
· intro hvv' u obtain ⟨t, ht, hr⟩ := h_cov u by_cases heq : t = v
If t = v, then u can reach v', which belongs to the swapped set.
When t = v, u can reach v. Since v can reach v', transitivity of reachability shows that u can reach v'. Furthermore, v' ∈ {v'} by Set.mem_singleton, so v' belongs to (T \ {v}) ∪ {v'} by Set.mem_union_right.
uses
Set.mem_union_right,Set.mem_singleton· subst heq exact ⟨v', Set.mem_union_right _ (Set.mem_singleton v'), hr.trans hvv'⟩
If t ≠ v, then u can reach t, which remains in the swapped set.
When t ≠ v, the representative t satisfies t ∈ T and t ∉ {v}, so t ∈ T \ {v}. Therefore t belongs to (T \ {v}) ∪ {v'} by Set.mem_union_left, and u can reach t directly.
uses
Set.mem_union_left· exact ⟨t, Set.mem_union_left _ ⟨ht, heq⟩, hr⟩
Set.mem_singleton_iff.mpr- An element equal to a given value belongs to the singleton set of that value.
Set.mem_singleton- Every element belongs to its own singleton set.
Set.mem_union_left- If an element belongs to a set a, then it belongs to the union a ∪ b.
Set.mem_union_right- If an element belongs to a set b, then it belongs to the union a ∪ b.
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.
/-- Single-edge swap in a component transversal preserves component coverage if and only if the swapped vertices are reachable. -/theorem component_transversal_exchange_iff {V : Type*} (G : SimpleGraph V) (T : Set V) (h_cov : ∀ v : V, ∃ t ∈ T, G.Reachable v t) (h_uniq : ∀ ⦃t1 t2⦄, t1 ∈ T → t2 ∈ T → G.Reachable t1 t2 → t1 = t2) (v v' : V) (hv : v ∈ T) : (∀ u : V, ∃ t ∈ (T \ {v}) ∪ {v'}, G.Reachable u t) ↔ G.Reachable v v' := by constructor · intro h obtain ⟨t, ht, hr⟩ := h v rcases ht with ⟨htT, htv⟩ | rfl · exfalso have heq := h_uniq hv htT hr exact htv (Set.mem_singleton_iff.mpr heq.symm) · exact hr · intro hvv' u obtain ⟨t, ht, hr⟩ := h_cov u by_cases heq : t = v · subst heq exact ⟨v', Set.mem_union_right _ (Set.mem_singleton v'), hr.trans hvv'⟩ · exact ⟨t, Set.mem_union_left _ ⟨ht, heq⟩, hr⟩