reflexive_rel_strongly_connected_arc_cycle_cover
In a strongly connected reflexive relation, every arc u → v is realised by a single cycle cover: take a simple path v = y₀ → … → y_s = u and the cycle (y₀ … y_s), which fixes all other points.
Statement
theorem reflexive_rel_strongly_connected_arc_cycle_cover {V : Type*} [Fintype V] [DecidableEq V] (R : V → V → Prop) (hR : ∀ v, R v v) (hsc : ∀ u v : V, Relation.ReflTransGen R u v) {u v : V} (huv : R u v) : ∃ p : Equiv.Perm V, (∀ x, R x (p x)) ∧ p u = v
- Source
- step towards simple_graph_normalized_hop_group_quadratic_word_diameter
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To find a cycle cover (permutation p) of a finite strongly connected reflexive relation with p(u) = v, the proof fixes p(u) = v and seeks an injective matching of the remaining vertices S = V \ {u} into out-neighbors that avoid v, namely W(x) = {y | R x y ∧ y ≠ v}. Hall's Marriage Theorem applies because for any T ⊆ S, reflexivity ensures T \ {v} ⊆ ⋃_{x ∈ T} W(x), and any violation of Hall's condition would force T to be closed under R-arcs, which by strong connectivity would put u ∈ T, a contradiction. Extending the resulting matching g on S by setting p(u) = v gives an injection on a finite set, which is therefore a permutation satisfying all conditions.
Define candidate out-neighborhoods W(x) avoiding v
Using classical logic, for each vertex x ∈ V we define W(x) = {y ∈ V | R x y ∧ y ≠ v}, the set of out-neighbors of x other than v. We verify (hmemW) that whenever R x y and y ≠ v, y belongs to W(x).
uses
Finset.mem_filter,Finset.mem_univ,true_andclassical set W : V → Finset V := fun x => Finset.univ.filter (fun y => R x y ∧ y ≠ v) with hW have hmemW : ∀ x y : V, R x y → y ≠ v → y ∈ W x := by intro x y hxy hyv simp only [hW, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hxy, hyv⟩
Hall's condition holds for all subsets of V avoiding u
Let T ⊆ V be a subset with u ∉ T. We show |T| ≤ |⋃_{x ∈ T} W(x)| by case analysis on whether v ∈ T. If v ∈ T: by reflexivity of R, every x ∈ T \ {v} satisfies R x x and x ≠ v, so T \ {v} ⊆ ⋃_{x ∈ T} W(x). If Hall's condition failed, we would have |⋃_{x ∈ T} W(x)| < |T|, which together with |T \ {v}| = |T| - 1 forces T \ {v} = ⋃_{x ∈ T} W(x). But then T would be closed under outgoing R-arcs (any arc from x ∈ T leads either to v ∈ T or into W(x) ⊆ T \ {v} ⊆ T). By strong connectivity from v, every vertex reachable from v would belong to T, including u, contradicting u ∉ T. If v ∉ T: every x ∈ T satisfies x ≠ v and R x x, so x ∈ W(x). Thus T ⊆ ⋃_{x ∈ T} W(x), which immediately implies |T| ≤ |⋃_{x ∈ T} W(x)|.
uses
Finset.mem_erase,Finset.mem_biUnion.mpr,Finset.card_erase_of_mem,Finset.eq_of_subset_of_card_le,Finset.mem_of_mem_erase,Finset.card_le_cardhave hallV : ∀ T : Finset V, (∀ x ∈ T, x ≠ u) → T.card ≤ (T.biUnion W).card := by intro T hTD by_cases hv : v ∈ T · have hsub : T.erase v ⊆ T.biUnion W := by intro x hx rw [Finset.mem_erase] at hx exact Finset.mem_biUnion.mpr ⟨x, hx.2, hmemW x x (hR x) hx.1⟩ by_contra hcon push Not at hcon have hcard : (T.erase v).card = T.card - 1 := Finset.card_erase_of_mem hv have hAeq : T.erase v = T.biUnion W := Finset.eq_of_subset_of_card_le hsub (by omega) have hclosed : ∀ x ∈ T, ∀ y, R x y → y ∈ T := by intro x hx y hxy by_cases hyv : y = v · rw [hyv]; exact hv · have : y ∈ T.biUnion W := Finset.mem_biUnion.mpr ⟨x, hx, hmemW x y hxy hyv⟩ rw [← hAeq] at this exact Finset.mem_of_mem_erase this have key : ∀ y, Relation.ReflTransGen R v y → y ∈ T := by intro y h induction h with | refl => exact hv | tail _ hbc ih => exact hclosed _ ih _ hbc exact hTD u (key u (hsc v u)) rfl · have hsub : T ⊆ T.biUnion W := by intro x hx have hxv : x ≠ v := fun h => hv (h ▸ hx) exact Finset.mem_biUnion.mpr ⟨x, hx, hmemW x x (hR x) hxv⟩ exact Finset.card_le_card hsub
Define the domain S = V \ {u}
We set S = V \ {u} and record the basic properties that u ∉ S and every vertex x ≠ u belongs to S.
set S : Finset V := Finset.univ.erase u with hS have huS : u ∉ S := by simp [hS] have hmemS : ∀ x : V, x ≠ u → x ∈ S := by intro x hx; simp [hS, hx]
Hall's condition holds on the subtype S
For any subset T of the subtype S, the inclusion map into V is injective, so its image has size |T| and is contained in S (hence does not contain u). The union of neighborhoods ⋃_{x ∈ T} W(x) equals the union over the image of T in V. Applying the previous result hallV to this image yields |T| ≤ |⋃_{x ∈ T} W(x)|.
uses
Subtype.val_injective,Finset.mem_image.mp,Finset.card_image_of_injective,Finset.mem_biUnion,Finset.mem_image,Finset.ne_of_mem_erasehave hallS : ∀ T : Finset ↥S, T.card ≤ (T.biUnion fun x => W (x : V)).card := by intro T have hfinj : Function.Injective (fun x : ↥S => (x : V)) := Subtype.val_injective have himg : T.image (fun x : ↥S => (x : V)) ⊆ S := by intro y hy obtain ⟨x, -, rfl⟩ := Finset.mem_image.mp hy exact x.2 have hcard1 : (T.image (fun x : ↥S => (x : V))).card = T.card := Finset.card_image_of_injective T hfinj have heq : (T.biUnion fun x => W (x : V)) = (T.image fun x : ↥S => (x : V)).biUnion W := by ext z simp only [Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨x, hx, hz⟩ exact ⟨(x : V), ⟨x, hx, rfl⟩, hz⟩ · rintro ⟨z', ⟨x, hx, rfl⟩, hz⟩ exact ⟨x, hx, hz⟩ rw [heq, ← hcard1] exact hallV _ fun x hx => Finset.ne_of_mem_erase (himg hx)
Hall's Marriage Theorem yields an injective selection on S
By Hall's Marriage Theorem (Finset.all_card_le_biUnion_card_iff_exists_injective), the condition hallS gives an injective function g : S → V such that g(x) ∈ W(x) for every x ∈ S. By definition of W, this means R x (g x) and g x ≠ v for all x ∈ S.
uses
Finset.all_card_le_biUnion_card_iff_exists_injective,Finset.mem_filter.mpobtain ⟨g, hginj, hgmem⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective (fun x : ↥S => W (x : V))).mp hallS have hgR : ∀ x : ↥S, R (x : V) (g x) := fun x => (Finset.mem_filter.mp (hgmem x)).2.1 have hgv : ∀ x : ↥S, g x ≠ v := fun x => (Finset.mem_filter.mp (hgmem x)).2.2
Extend the matching to a function F : V → V
We define F : V → V by setting F(x) = g(x) if x ∈ S and F(x) = v otherwise. Since u ∉ S, this gives F(u) = v and F(x) = g(x) for all x ∈ S.
uses
dif_pos,dif_negset F : V → V := fun x => if h : x ∈ S then g ⟨x, h⟩ else v with hF have hFS : ∀ x (h : x ∈ S), F x = g ⟨x, h⟩ := by intro x h; simp only [hF]; rw [dif_pos h] have hFu : F u = v := by simp only [hF]; rw [dif_neg huS]
F is injective
Suppose F(a) = F(b). If both a, b ∈ S, injectivity of g implies a = b. If a ∈ S and b ∉ S, then b = u, so g(a) = F(u) = v, contradicting g(a) ≠ v; the symmetric case is likewise impossible. If neither belongs to S, then a = u and b = u, so a = b.
uses
congrArg,Subtype.val,dif_neghave hFinj : Function.Injective F := by intro a b hab by_cases ha : a ∈ S · by_cases hb : b ∈ S · rw [hFS a ha, hFS b hb] at hab have h3 : (⟨a, ha⟩ : ↥S) = ⟨b, hb⟩ := hginj hab exact congrArg Subtype.val h3 · exfalso rw [hFS a ha] at hab have h2 : F b = v := by simp only [hF]; rw [dif_neg hb] rw [h2] at hab exact hgv ⟨a, ha⟩ hab · by_cases hb : b ∈ S · exfalso rw [hFS b hb] at hab have h2 : F a = v := by simp only [hF]; rw [dif_neg ha] rw [h2] at hab exact hgv ⟨b, hb⟩ hab.symm · have h1 : a = u := by by_contra hne; exact ha (hmemS a hne) have h2 : b = u := by by_contra hne; exact hb (hmemS b hne) rw [h1, h2]
F is bijective
On a finite set V, any injective self-map is automatically bijective (Fintype.bijective_iff_injective_and_card).
uses
Fintype.bijective_iff_injective_and_cardhave hFbij : Function.Bijective F := (Fintype.bijective_iff_injective_and_card F).mpr ⟨hFinj, rfl⟩
The bijection F yields the required permutation p
We promote F to a permutation p of V via Equiv.ofBijective. For x ∈ S, p(x) = g(x) satisfies R x (p x); for x = u, p(u) = F(u) = v satisfies R u v by the hypothesis huv. Furthermore, p(u) = F(u) = v holds by definition.
uses
Equiv.ofBijective,Equiv.ofBijective_applyrefine ⟨Equiv.ofBijective F hFbij, ?_, ?_⟩ · intro x rw [Equiv.ofBijective_apply] by_cases hx : x ∈ S · rw [hFS x hx]; exact hgR ⟨x, hx⟩ · have hxu : x = u := by by_contra hne; exact hx (hmemS x hne) rw [hxu, hFu]; exact huv · rw [Equiv.ofBijective_apply]; exact hFu
Finset.mem_filter- An element belongs to the filtered set {y ∈ s | p y} if and only if it belongs to s and satisfies predicate p.
Finset.mem_filter.mp- If an element belongs to {y ∈ s | p y}, then it belongs to s and satisfies p.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The logical simplification (True ∧ p) = p.
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_biUnion.mpr- If an element belongs to t a for some a ∈ s, then it belongs to the union ⋃_{x ∈ s} t x.
Finset.mem_biUnion- An element belongs to ⋃_{a ∈ s} t a if and only if it belongs to t a for some a ∈ s.
Finset.card_erase_of_mem- Erasing an element a ∈ s from a finite set s decreases its cardinality by 1.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.mem_of_mem_erase- If an element belongs to s.erase a, then it belongs to s.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Subtype.val_injective- The canonical projection from a subtype to its ambient type is injective.
Subtype.val- The canonical projection extracting the underlying value from a subtype.
Finset.card_image_of_injective- An injective function preserves the cardinality of any finite set under its image.
Finset.mem_image- An element is in the image f(s) if and only if it equals f a for some a ∈ s.
Finset.mem_image.mp- If an element belongs to f(s), then it equals f a for some a ∈ s.
Finset.ne_of_mem_erase- Any element belonging to s.erase a is not equal to a.
Finset.all_card_le_biUnion_card_iff_exists_injective- Hall's Marriage Theorem for finite sets: a family of sets has an injective system of distinct representatives if and only if Hall's condition |s| ≤ |⋃_{i ∈ s} t i| holds for every finite index set s.
dif_pos- A dependent conditional if h : c then t else e evaluates to t when c holds.
dif_neg- A dependent conditional if h : c then t else e evaluates to e when ¬c holds.
congrArg- If x = y, then f x = f y.
Fintype.bijective_iff_injective_and_card- A map between finite sets of the same cardinality is bijective if and only if it is injective.
Equiv.ofBijective- Constructs an equivalence (permutation) from a bijective function.
Equiv.ofBijective_apply- The equivalence constructed by Equiv.ofBijective f evaluates to f a on input a.
- The docstring in the source suggests constructing a single cycle containing the arc u → v by finding a simple path from v to u and fixing all other vertices; however, the formal proof instead uses Hall's Marriage Theorem to construct a permutation covering all vertices with R-arcs, which may decompose into multiple disjoint cycles.
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.
/-- Every arc of a strongly connected reflexive relation is realised by one cycle cover. -/theorem reflexive_rel_strongly_connected_arc_cycle_cover {V : Type*} [Fintype V] [DecidableEq V] (R : V → V → Prop) (hR : ∀ v, R v v) (hsc : ∀ u v : V, Relation.ReflTransGen R u v) {u v : V} (huv : R u v) : ∃ p : Equiv.Perm V, (∀ x, R x (p x)) ∧ p u = v := by classical set W : V → Finset V := fun x => Finset.univ.filter (fun y => R x y ∧ y ≠ v) with hW have hmemW : ∀ x y : V, R x y → y ≠ v → y ∈ W x := by intro x y hxy hyv simp only [hW, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hxy, hyv⟩ have hallV : ∀ T : Finset V, (∀ x ∈ T, x ≠ u) → T.card ≤ (T.biUnion W).card := by intro T hTD by_cases hv : v ∈ T · have hsub : T.erase v ⊆ T.biUnion W := by intro x hx rw [Finset.mem_erase] at hx exact Finset.mem_biUnion.mpr ⟨x, hx.2, hmemW x x (hR x) hx.1⟩ by_contra hcon push Not at hcon have hcard : (T.erase v).card = T.card - 1 := Finset.card_erase_of_mem hv have hAeq : T.erase v = T.biUnion W := Finset.eq_of_subset_of_card_le hsub (by omega) have hclosed : ∀ x ∈ T, ∀ y, R x y → y ∈ T := by intro x hx y hxy by_cases hyv : y = v · rw [hyv]; exact hv · have : y ∈ T.biUnion W := Finset.mem_biUnion.mpr ⟨x, hx, hmemW x y hxy hyv⟩ rw [← hAeq] at this exact Finset.mem_of_mem_erase this have key : ∀ y, Relation.ReflTransGen R v y → y ∈ T := by intro y h induction h with | refl => exact hv | tail _ hbc ih => exact hclosed _ ih _ hbc exact hTD u (key u (hsc v u)) rfl · have hsub : T ⊆ T.biUnion W := by intro x hx have hxv : x ≠ v := fun h => hv (h ▸ hx) exact Finset.mem_biUnion.mpr ⟨x, hx, hmemW x x (hR x) hxv⟩ exact Finset.card_le_card hsub set S : Finset V := Finset.univ.erase u with hS have huS : u ∉ S := by simp [hS] have hmemS : ∀ x : V, x ≠ u → x ∈ S := by intro x hx; simp [hS, hx] have hallS : ∀ T : Finset ↥S, T.card ≤ (T.biUnion fun x => W (x : V)).card := by intro T have hfinj : Function.Injective (fun x : ↥S => (x : V)) := Subtype.val_injective have himg : T.image (fun x : ↥S => (x : V)) ⊆ S := by intro y hy obtain ⟨x, -, rfl⟩ := Finset.mem_image.mp hy exact x.2 have hcard1 : (T.image (fun x : ↥S => (x : V))).card = T.card := Finset.card_image_of_injective T hfinj have heq : (T.biUnion fun x => W (x : V)) = (T.image fun x : ↥S => (x : V)).biUnion W := by ext z simp only [Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨x, hx, hz⟩ exact ⟨(x : V), ⟨x, hx, rfl⟩, hz⟩ · rintro ⟨z', ⟨x, hx, rfl⟩, hz⟩ exact ⟨x, hx, hz⟩ rw [heq, ← hcard1] exact hallV _ fun x hx => Finset.ne_of_mem_erase (himg hx) obtain ⟨g, hginj, hgmem⟩ := (Finset.all_card_le_biUnion_card_iff_exists_injective (fun x : ↥S => W (x : V))).mp hallS have hgR : ∀ x : ↥S, R (x : V) (g x) := fun x => (Finset.mem_filter.mp (hgmem x)).2.1 have hgv : ∀ x : ↥S, g x ≠ v := fun x => (Finset.mem_filter.mp (hgmem x)).2.2 set F : V → V := fun x => if h : x ∈ S then g ⟨x, h⟩ else v with hF have hFS : ∀ x (h : x ∈ S), F x = g ⟨x, h⟩ := by intro x h; simp only [hF]; rw [dif_pos h] have hFu : F u = v := by simp only [hF]; rw [dif_neg huS] have hFinj : Function.Injective F := by intro a b hab by_cases ha : a ∈ S · by_cases hb : b ∈ S · rw [hFS a ha, hFS b hb] at hab have h3 : (⟨a, ha⟩ : ↥S) = ⟨b, hb⟩ := hginj hab exact congrArg Subtype.val h3 · exfalso rw [hFS a ha] at hab have h2 : F b = v := by simp only [hF]; rw [dif_neg hb] rw [h2] at hab exact hgv ⟨a, ha⟩ hab · by_cases hb : b ∈ S · exfalso rw [hFS b hb] at hab have h2 : F a = v := by simp only [hF]; rw [dif_neg ha] rw [h2] at hab exact hgv ⟨b, hb⟩ hab.symm · have h1 : a = u := by by_contra hne; exact ha (hmemS a hne) have h2 : b = u := by by_contra hne; exact hb (hmemS b hne) rw [h1, h2] have hFbij : Function.Bijective F := (Fintype.bijective_iff_injective_and_card F).mpr ⟨hFinj, rfl⟩ refine ⟨Equiv.ofBijective F hFbij, ?_, ?_⟩ · intro x rw [Equiv.ofBijective_apply] by_cases hx : x ∈ S · rw [hFS x hx]; exact hgR ⟨x, hx⟩ · have hxu : x = u := by by_contra hne; exact hx (hmemS x hne) rw [hxu, hFu]; exact huv · rw [Equiv.ofBijective_apply]; exact hFu