reflexive_rel_swap_is_cycle_cover
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.
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.
intro zIf $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`.
uses
Equiv.swap_apply_leftby_cases hzx : z = x · rw [hzx, Equiv.swap_apply_left] exact hxy
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`).
uses
Equiv.swap_apply_right· by_cases hzy : z = y · rw [hzy, Equiv.swap_apply_right] exact hR_symm x y hxy
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`).
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
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.
/-- 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