AFTD Auto-Formalizing Theoretical Domains

reflexive_rel_swap_is_cycle_cover

theoremverified

If R is reflexive and symmetric and R x y holds, then swap x y is a cycle cover of R (it maps every vertex to an R-neighbor).

Statement

theorem reflexive_rel_swap_is_cycle_cover {V : Type*} [DecidableEq V]
    (R : V → V → Prop) (hR : ∀ v, R v v) (hR_symm : ∀ u v, R u v → R v u)
    {x y : V} (hxy : R x y) :
    ∀ z : V, R z (Equiv.swap x y z)
Source
step towards reflexive_rel_symmetric_cycle_cover_quadratic_diameter
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that the transposition $\operatorname{swap}(x, y)$ maps every vertex to an $R$-neighbor, we consider an arbitrary vertex $z$ and split into three cases: $z = x$, $z = y$, or $z \notin \{x, y\}$. In the first two cases, the swap interchanges $x$ and $y$, so the relation holds by the edge assumption $R(x, y)$ and symmetry. In the third case, $z$ is fixed by the swap, and the relation holds by reflexivity.

  1. Fix an arbitrary vertex $z \in V$.

    To prove the universal statement, we introduce an arbitrary element $z \in V$; we must show that $R(z, \operatorname{swap}(x, y)(z))$ holds.

    line 6

      intro z
  2. If $z = x$, then $R(z, \operatorname{swap}(x, y)(z))$ holds.

    We split into cases on whether $z = x$. When $z = x$, rewriting with the equality and `Equiv.swap_apply_left` simplifies the goal to $R(x, y)$, which is given directly by the assumption `hxy`.

    lines 7–9

    uses Equiv.swap_apply_left

      by_cases hzx : z = x
      · rw [hzx, Equiv.swap_apply_left]
        exact hxy
  3. If $z \ne x$ and $z = y$, then $R(z, \operatorname{swap}(x, y)(z))$ holds.

    Having assumed $z \ne x$, we split on whether $z = y$. When $z = y$, rewriting with this equality and `Equiv.swap_apply_right` changes the goal to $R(y, x)$. This follows from the assumption $R(x, y)$ by the symmetry of $R$ (`hR_symm`).

    lines 10–12

    uses Equiv.swap_apply_right

      · by_cases hzy : z = y
        · rw [hzy, Equiv.swap_apply_right]
          exact hR_symm x y hxy
  4. If $z$ is neither $x$ nor $y$, then $R(z, \operatorname{swap}(x, y)(z))$ holds.

    Since $z \ne x$ and $z \ne y$, the transposition fixes $z$ by `Equiv.swap_apply_of_ne_of_ne`. The goal reduces to $R(z, z)$, which holds by the reflexivity of $R$ (`hR`).

    lines 13–14

    uses Equiv.swap_apply_of_ne_of_ne

        · rw [Equiv.swap_apply_of_ne_of_ne hzx hzy]
          exact hR z
Equiv.swap_apply_left
Applying the transposition of $a$ and $b$ to $a$ yields $b$.
Equiv.swap_apply_right
Applying the transposition of $a$ and $b$ to $b$ yields $a$.
Equiv.swap_apply_of_ne_of_ne
Applying the transposition of $a$ and $b$ to an element distinct from both leaves it unchanged.

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 reflexive and symmetric relation R, any transposition along an edge (R x y) is a cycle cover of R. -/theorem reflexive_rel_swap_is_cycle_cover {V : Type*} [DecidableEq V]    (R : V → V → Prop) (hR : ∀ v, R v v) (hR_symm : ∀ u v, R u v → R v u)    {x y : V} (hxy : R x y) :    ∀ z : V, R z (Equiv.swap x y z) := by  intro z  by_cases hzx : z = x  · rw [hzx, Equiv.swap_apply_left]    exact hxy  · by_cases hzy : z = y    · rw [hzy, Equiv.swap_apply_right]      exact hR_symm x y hxy    · rw [Equiv.swap_apply_of_ne_of_ne hzx hzy]      exact hR z
See it in the graphDiscuss this resultChallenge it