AFTD Auto-Formalizing Theoretical Domains

digraph_digon_cycle_packing_step

theoremverified

A directed two-cycle can be added to any k-cycle packing theorem two outdegree units lower.

Statement

theorem digraph_digon_cycle_packing_step
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ)
    (hloop : ∀ v, ¬ D.Adj v v)
    (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hpack : ∀ T : Finset α, T.Nonempty →
      (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧
        Pairwise (fun i j => Disjoint (s i) (s j)))
    (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) :
    ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))
Source
General form of the proved four-cycle digon reduction for OP-110.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
Used by 1

The proof, explained

The proof extends a cycle packing theorem to find k + 1 pairwise disjoint directed cycles in a directed graph of minimum outdegree d + 2, given a directed 2-cycle (digon) on vertices u and v. Removing {u, v} from the vertex set decreases the outdegree of every remaining vertex by at most 2, leaving a nonempty induced subgraph T with minimum outdegree at least d. Applying the induction/packing hypothesis to T yields k pairwise disjoint directed cycles; since they are contained in T and thus disjoint from {u, v}, combining them with the digon gives k + 1 pairwise disjoint directed cycles.

  1. The vertices u and v of the digon are distinct.

    If u = v, then the assumed directed edge from u to v would be a self-loop at u, contradicting the looplessness hypothesis `hloop`.

    lines 12–13

      classical
      have huvne : u ≠ v := by intro h; subst v; exact hloop u huv
  2. The vertex set α has at least 3 vertices.

    Let O be the out-neighborhood of u. Since D has no self-loops, u ∉ O. Thus |O ∪ {u}| = |O| + 1 by `Finset.card_insert_of_notMem`. Since u has outdegree at least d + 2, |O| ≥ d + 2 ≥ 2, so |O ∪ {u}| ≥ 3. Because O ∪ {u} ⊆ Finset.univ by `Finset.subset_univ`, monotonicity of cardinality (`Finset.card_le_card`) implies that the total number of vertices is at least 3.

    lines 14–21

    uses Finset.card_insert_of_notMem, Finset.card_le_card, Finset.subset_univ

      let T : Finset α := (Finset.univ.erase u).erase v
      let O : Finset α := Finset.univ.filter fun w => D.Adj u w
      have huO : u ∉ O := by simp [O, hloop]
      have hi : (insert u O).card ≤ (Finset.univ : Finset α).card :=
        Finset.card_le_card (Finset.subset_univ _)
      have hi' : (insert u O).card = O.card + 1 := Finset.card_insert_of_notMem huO
      have hd : d + 2 ≤ O.card := hdeg u
      have hcard : 3 ≤ (Finset.univ : Finset α).card := by omega
  3. The set T = α \ {u, v} is nonempty.

    We argue by contradiction (`by_contra`). If T were empty (`Finset.not_nonempty_iff_eq_empty.mp`), then every vertex of α would belong to {u, v}. Since u ≠ v, |{u, v}| ≤ 2, which by `Finset.card_le_card` would force |α| ≤ 2. But |α| ≥ 3 from the previous step, which is impossible (`omega`).

    lines 22–36

    uses Finset.card_le_card, Finset.not_nonempty_iff_eq_empty.mp

      have hT : T.Nonempty := by
        by_contra hn
        have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn
        have hs : (Finset.univ : Finset α) ⊆ {u,v} := by
          intro x hx
          by_cases hxu : x = u
          · simp [hxu]
          by_cases hxv : x = v
          · simp [hxv]
          have : x ∈ T := by simp [T, hxu, hxv]
          rw [he] at this
          simp at this
        have hh := Finset.card_le_card hs
        have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]
        omega
  4. Every vertex in T has at least d out-neighbors in T.

    For any x ∈ T, every out-neighbor w of x in the entire graph either belongs to T or belongs to {u, v} (by `Finset.mem_filter.mp`, `Finset.mem_union_left`, and `Finset.mem_filter.mpr`). Hence the out-neighborhood of x is a subset of its out-neighborhood in T union {u, v}. Using `Finset.card_le_card` and subadditivity `Finset.card_union_le`, the outdegree in α is at most the outdegree in T plus |{u, v}| ≤ 2. Because x has outdegree at least d + 2 by `hdeg`, its outdegree into T is at least d (`omega`).

    lines 37–53

    uses Finset.card_le_card, Finset.card_union_le, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_union_left

      have hTdeg : ∀ x ∈ T, d ≤ (T.filter fun w => D.Adj x w).card := by
        intro x hx
        have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆
            (T.filter fun w => D.Adj x w) ∪ {u,v} := by
          intro w hw
          have hadj := (Finset.mem_filter.mp hw).2
          by_cases hwu : w = u
          · simp [hwu]
          by_cases hwv : w = v
          · simp [hwv]
          have hwT : w ∈ T := by simp [T, hwu, hwv]
          exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)
        have hh := Finset.card_le_card hs
        have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α)
        have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]
        have hd := hdeg x
        omega
  5. There exist k pairwise disjoint directed cycles contained in T.

    We apply the cycle packing hypothesis `hpack` to the induced subgraph on T, which is nonempty and has minimum outdegree at least d. This yields a family t : Fin k → Finset α of k pairwise disjoint directed cycles with each t i ⊆ T.

    line 54

      obtain ⟨t, ht, hpair⟩ := hpack T hT hTdeg
  6. The set {u, v} forms a directed cycle in D.

    The two-element list [u, v] serves as an explicit witness for `digraph_directed_cycle_on`: it has length 2, no duplicate vertices since u ≠ v, and the directed edges u → v and v → u form a directed cycle.

    lines 55–57

      have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by
        refine ⟨[u,v], ?_⟩
        simp [huvne, huv, hvu]
  7. The digon {u, v} is disjoint from each of the k cycles t i.

    By `Finset.disjoint_left.mpr`, we check that no vertex x belongs to both {u, v} and t i. Any vertex in t i belongs to T, which excludes u and v by definition (using `Finset.mem_erase`, `Finset.mem_univ`, and `and_true`). But x ∈ {u, v} implies x = u or x = v (by `Finset.mem_insert` and `Finset.mem_singleton`), which is a contradiction.

    lines 58–65

    uses and_true, Finset.disjoint_left.mpr, Finset.mem_erase, Finset.mem_insert, Finset.mem_singleton, Finset.mem_univ

      have hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by
        intro i
        apply Finset.disjoint_left.mpr
        intro x hx hxt
        have hxT := (ht i).1 hxt
        simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with rfl | rfl <;> simp_all
  8. The combined family f : Fin (k + 1) → Finset α consists of directed cycles.

    We define f using `Fin.cases` by sending index 0 to {u, v} and index i + 1 to t i. For index 0, {u, v} is a directed cycle; for each successor index i + 1, t i is a directed cycle by the packing hypothesis.

    lines 66–71

    uses Fin.cases

      let f : Fin (k + 1) → Finset α := Fin.cases {u,v} t
      refine ⟨f, ?_, ?_⟩
      · intro i
        refine Fin.cases ?_ (fun i => ?_) i
        · exact h2
        · exact (ht i).2
  9. The k + 1 directed cycles in the family f are pairwise disjoint.

    Given distinct indices i, j ∈ Fin (k + 1), case analysis via `Fin.cases` on both indices covers all possibilities: the case i = 0, j = 0 contradicts i ≠ j; the cross cases between 0 and a successor follow from the disjointness of {u, v} from each t m (or its symmetry); and the case of two successor indices i' + 1 and j' + 1 follows from the pairwise disjointness of the original family t.

    lines 72–85

    uses Fin.cases

      · intro i
        refine Fin.cases ?_ (fun i => ?_) i
        · intro j
          refine Fin.cases ?_ (fun j => ?_) j
          · intro hij
            exact (hij rfl).elim
          · intro _
            exact hdis j
        · intro j
          refine Fin.cases ?_ (fun j => ?_) j
          · intro _
            exact (hdis i).symm
          · intro hij
            exact hpair (by simpa using hij)
and_true
For any proposition p, the conjunction p ∧ True is equivalent to p.
Fin.cases
Given a base value for 0 and an inductive step for successors, this defines a dependent function on Fin (n + 1).
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not already contain it increases the set's cardinality by 1.
Finset.card_le_card
If s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second.
Finset.mem_erase
An element belongs to s with b erased if and only if it is not equal to b and belongs to s.
Finset.mem_filter.mp
An element of a filtered finite set belongs to the original set and satisfies the filter predicate.
Finset.mem_filter.mpr
An element that belongs to a set and satisfies a predicate belongs to the corresponding filtered set.
Finset.mem_insert
An element belongs to the insertion insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to a singleton set {a} if and only if it equals a.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_union_left
If an element belongs to s, then it belongs to s ∪ t.
Finset.not_nonempty_iff_eq_empty.mp
If a finite set is not nonempty, then it is the empty set.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal set.

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

theorem digraph_digon_cycle_packing_step    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ)    (hloop : ∀ v, ¬ D.Adj v v)    (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hpack : ∀ T : Finset α, T.Nonempty →      (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) →      ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧        Pairwise (fun i j => Disjoint (s i) (s j)))    (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) :    ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j)) := by  classical  have huvne : u ≠ v := by intro h; subst v; exact hloop u huv  let T : Finset α := (Finset.univ.erase u).erase v  let O : Finset α := Finset.univ.filter fun w => D.Adj u w  have huO : u ∉ O := by simp [O, hloop]  have hi : (insert u O).card ≤ (Finset.univ : Finset α).card :=    Finset.card_le_card (Finset.subset_univ _)  have hi' : (insert u O).card = O.card + 1 := Finset.card_insert_of_notMem huO  have hd : d + 2 ≤ O.card := hdeg u  have hcard : 3 ≤ (Finset.univ : Finset α).card := by omega  have hT : T.Nonempty := by    by_contra hn    have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn    have hs : (Finset.univ : Finset α) ⊆ {u,v} := by      intro x hx      by_cases hxu : x = u      · simp [hxu]      by_cases hxv : x = v      · simp [hxv]      have : x ∈ T := by simp [T, hxu, hxv]      rw [he] at this      simp at this    have hh := Finset.card_le_card hs    have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]    omega  have hTdeg : ∀ x ∈ T, d ≤ (T.filter fun w => D.Adj x w).card := by    intro x hx    have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆        (T.filter fun w => D.Adj x w) ∪ {u,v} := by      intro w hw      have hadj := (Finset.mem_filter.mp hw).2      by_cases hwu : w = u      · simp [hwu]      by_cases hwv : w = v      · simp [hwv]      have hwT : w ∈ T := by simp [T, hwu, hwv]      exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)    have hh := Finset.card_le_card hs    have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α)    have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]    have hd := hdeg x    omega  obtain ⟨t, ht, hpair⟩ := hpack T hT hTdeg  have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by    refine ⟨[u,v], ?_⟩    simp [huvne, huv, hvu]  have hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by    intro i    apply Finset.disjoint_left.mpr    intro x hx hxt    have hxT := (ht i).1 hxt    simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with rfl | rfl <;> simp_all  let f : Fin (k + 1) → Finset α := Fin.cases {u,v} t  refine ⟨f, ?_, ?_⟩  · intro i    refine Fin.cases ?_ (fun i => ?_) i    · exact h2    · exact (ht i).2  · intro i    refine Fin.cases ?_ (fun i => ?_) i    · intro j      refine Fin.cases ?_ (fun j => ?_) j      · intro hij        exact (hij rfl).elim      · intro _        exact hdis j    · intro j      refine Fin.cases ?_ (fun j => ?_) j      · intro _        exact (hdis i).symm      · intro hij        exact hpair (by simpa using hij)
See it in the graphDiscuss this resultChallenge it