AFTD Auto-Formalizing Theoretical Domains

reflexive_rel_strongly_connected_arc_cycle_cover

theoremverified

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.

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

    lines 6–11

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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⟩
  2. 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)|.

    lines 12–40

    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_card

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

    lines 41–44

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

    lines 45–63

    uses Subtype.val_injective, Finset.mem_image.mp, Finset.card_image_of_injective, Finset.mem_biUnion, Finset.mem_image, Finset.ne_of_mem_erase

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

    lines 64–67

    uses Finset.all_card_le_biUnion_card_iff_exists_injective, Finset.mem_filter.mp

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

    lines 68–72

    uses dif_pos, dif_neg

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

    lines 73–95

    uses congrArg, Subtype.val, dif_neg

      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]
  8. F is bijective

    On a finite set V, any injective self-map is automatically bijective (Fintype.bijective_iff_injective_and_card).

    lines 96–97

    uses Fintype.bijective_iff_injective_and_card

      have hFbij : Function.Bijective F :=
        (Fintype.bijective_iff_injective_and_card F).mpr ⟨hFinj, rfl⟩
  9. 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.

    lines 98–106

    uses Equiv.ofBijective, Equiv.ofBijective_apply

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

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

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