AFTD Auto-Formalizing Theoretical Domains

simple_graph_connected_component_swap_iff

theoremverified

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.

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

    lines 7–10

      constructor
      · intro h
        obtain ⟨w, hw, hw_eq⟩ := h (G.connectedComponentMk u)
        rcases hw with hw | hw
  2. 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.

    lines 11–13

    uses ExistsUnique.unique

        · exfalso
          have hu_uniq := ExistsUnique.unique (hS (G.connectedComponentMk u)) ⟨hw.1, hw_eq⟩ ⟨hu, rfl⟩
          exact hw.2 hu_uniq
  3. 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).

    lines 14–16

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

    lines 17–21

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

    lines 22–25

    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

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