AFTD Auto-Formalizing Theoretical Domains

component_transversal_exchange_iff

theoremverified

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

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.

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

    line 7

      constructor
  2. Assuming 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'.

    lines 8–10

      · intro h
        obtain ⟨t, ht, hr⟩ := h v
        rcases ht with ⟨htT, htv⟩ | rfl
  3. 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.

    lines 11–13

    uses Set.mem_singleton_iff.mpr

        · exfalso
          have heq := h_uniq hv htT hr
          exact htv (Set.mem_singleton_iff.mpr heq.symm)
  4. 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.

    line 14

        · exact hr
  5. Conversely, 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.

    lines 15–17

      · intro hvv' u
        obtain ⟨t, ht, hr⟩ := h_cov u
        by_cases heq : t = v
  6. 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.

    lines 18–19

    uses Set.mem_union_right, Set.mem_singleton

        · subst heq
          exact ⟨v', Set.mem_union_right _ (Set.mem_singleton v'), hr.trans hvv'⟩
  7. 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.

    line 20

    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

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