simple_graph_connected_component_swap_iff
Let G be a simple graph on V. If S ⊆ V contains exactly one representative from each connected component of G, then for any u ∈ S and any v ∈ V, the swapped set (S \ {u}) ∪ {v} intersects every connected component of G if and only if u and v belong to the same connected component (that is, G.Reachable u v).
Statement
theorem simple_graph_connected_component_swap_iff {V : Type*} (G : SimpleGraph V) (S : Set V) (hS : ∀ c : G.ConnectedComponent, ∃! x, x ∈ S ∧ G.connectedComponentMk x = c) (u : V) (hu : u ∈ S) (v : V) : (∀ c : G.ConnectedComponent, ∃ w ∈ (S \ {u}) ∪ {v}, G.connectedComponentMk w = c) ↔ G.Reachable u v
- Source
- arXiv:2611.06626 Claim 2.5
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any type $V$, simple graph $G$ on $V$, and subset $S \subseteq V$ such that every connected component $c$ of $G$ contains a unique vertex $x \in S$ (i.e., $S$ is a set of unique representatives for the connected components of $G$), and for any $u \in S$ and $v \in V$: every connected component of $G$ contains at least one vertex in $(S \setminus \{u\}) \cup \{v\}$ if and only if $u$ and $v$ are reachable from each other in $G$.
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 equivalence is proved in two directions. For the forward direction, assuming the swapped set intersects every component, specializing to the component of u reveals that its representative cannot come from S \ {u} without violating the uniqueness of representatives in S, forcing the representative to be v and hence making u and v reachable. For the backward direction, assuming u and v are reachable, the component of u is represented by v, while every other component retains its original representative from S, which is unaffected because it cannot equal u.
In the forward direction, assuming the swapped set intersects every component, there is a witness w in (S \ {u}) ∪ {v} belonging to the component of u.
We split the equivalence into both implications. In the forward direction, we assume that the modified set (S \ {u}) ∪ {v} intersects every connected component of G. Specializing this assumption to the connected component containing u yields a witness vertex w ∈ (S \ {u}) ∪ {v} in that same component, which must fall into one of two cases: w ∈ S \ {u} or w ∈ {v}.
constructor · intro h obtain ⟨w, hw, hw_eq⟩ := h (G.connectedComponentMk u) rcases hw with hw | hw
The witness w cannot lie in S \ {u}.
Suppose w ∈ S \ {u}. Then both w and u belong to S and to the connected component of u. Since S contains a unique representative in each component, w must equal u (by ExistsUnique.unique). But w ∈ S \ {u} implies w ≠ u, which is a contradiction.
uses
ExistsUnique.unique· exfalso have hu_uniq := ExistsUnique.unique (hS (G.connectedComponentMk u)) ⟨hw.1, hw_eq⟩ ⟨hu, rfl⟩ exact hw.2 hu_uniq
The witness w must be v, which proves u and v are reachable.
Because w cannot lie in S \ {u}, it must belong to {v}, meaning w = v (by Set.mem_singleton_iff.mp). Since w is in the component of u, v is in the component of u as well, so u and v are reachable (by SimpleGraph.ConnectedComponent.eq.mp).
uses
Set.mem_singleton_iff.mp,SimpleGraph.ConnectedComponent.eq.mp· have hw_v : w = v := Set.mem_singleton_iff.mp hw rw [hw_v] at hw_eq exact SimpleGraph.ConnectedComponent.eq.mp hw_eq.symm
In the backward direction, assuming u and v are reachable, the component of u is represented by v in the swapped set.
Assume u and v are reachable and let c be an arbitrary connected component. We case-split on whether c is the component of u. If c is the component of u, we choose v as the representative: v belongs to (S \ {u}) ∪ {v} via the right-hand singleton {v} (Set.mem_union_right and Set.mem_singleton), and since u and v are reachable, v indeed belongs to the component of u (SimpleGraph.ConnectedComponent.eq.mpr).
uses
Set.mem_union_right,Set.mem_singleton,SimpleGraph.ConnectedComponent.eq.mpr· intro h c by_cases hc : c = G.connectedComponentMk u · subst hc refine ⟨v, Set.mem_union_right _ (Set.mem_singleton v), ?_⟩ exact SimpleGraph.ConnectedComponent.eq.mpr h.symm
Any component other than that of u is represented by its original representative in S \ {u}.
If c is not the component of u, let x ∈ S be the unique representative of c in S. If x were equal to u, then c would be the component of u, contradicting our case assumption. Thus x ≠ u, so x ∈ S \ {u} ⊆ (S \ {u}) ∪ {v} (by Set.mem_union_left), providing the required representative for c.
uses
Set.mem_union_left· obtain ⟨x, ⟨hxS, hxc⟩, -⟩ := hS c refine ⟨x, Set.mem_union_left _ ⟨hxS, ?_⟩, hxc⟩ rintro rfl exact hc hxc.symm
ExistsUnique.unique- If an element uniquely satisfies a property, any two elements satisfying that property are equal.
Set.mem_singleton_iff.mp- If an element belongs to the singleton set {a}, then it is equal to a.
Set.mem_union_left- If an element belongs to a set A, then it belongs to the union A ∪ B.
Set.mem_singleton- Every element a belongs to the singleton set {a}.
Set.mem_union_right- If an element belongs to a set B, then it belongs to the union A ∪ B.
SimpleGraph.ConnectedComponent.eq.mp- If two vertices belong to the same connected component, then they are reachable from each other.
SimpleGraph.ConnectedComponent.eq.mpr- If two vertices are reachable from each other, then they belong to the same connected component.
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.
/-- Swapping a vertex in a transversal of connected components preserves hitting all components iff the vertices are in the same component. -/theorem simple_graph_connected_component_swap_iff {V : Type*} (G : SimpleGraph V) (S : Set V) (hS : ∀ c : G.ConnectedComponent, ∃! x, x ∈ S ∧ G.connectedComponentMk x = c) (u : V) (hu : u ∈ S) (v : V) : (∀ c : G.ConnectedComponent, ∃ w ∈ (S \ {u}) ∪ {v}, G.connectedComponentMk w = c) ↔ G.Reachable u v := by constructor · intro h obtain ⟨w, hw, hw_eq⟩ := h (G.connectedComponentMk u) rcases hw with hw | hw · exfalso have hu_uniq := ExistsUnique.unique (hS (G.connectedComponentMk u)) ⟨hw.1, hw_eq⟩ ⟨hu, rfl⟩ exact hw.2 hu_uniq · have hw_v : w = v := Set.mem_singleton_iff.mp hw rw [hw_v] at hw_eq exact SimpleGraph.ConnectedComponent.eq.mp hw_eq.symm · intro h c by_cases hc : c = G.connectedComponentMk u · subst hc refine ⟨v, Set.mem_union_right _ (Set.mem_singleton v), ?_⟩ exact SimpleGraph.ConnectedComponent.eq.mpr h.symm · obtain ⟨x, ⟨hxS, hxc⟩, -⟩ := hS c refine ⟨x, Set.mem_union_left _ ⟨hxS, ?_⟩, hxc⟩ rintro rfl exact hc hxc.symm