digraph_digon_cycle_packing_step
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
- digraph_small_overlap_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2…
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.
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`.
classical have huvne : u ≠ v := by intro h; subst v; exact hloop u huv
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.
uses
Finset.card_insert_of_notMem,Finset.card_le_card,Finset.subset_univlet 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
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`).
uses
Finset.card_le_card,Finset.not_nonempty_iff_eq_empty.mphave 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
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`).
uses
Finset.card_le_card,Finset.card_union_le,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_union_lefthave 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
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.
obtain ⟨t, ht, hpair⟩ := hpack T hT hTdegThe 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.
have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by refine ⟨[u,v], ?_⟩ simp [huvne, huv, hvu]
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.
uses
and_true,Finset.disjoint_left.mpr,Finset.mem_erase,Finset.mem_insert,Finset.mem_singleton,Finset.mem_univhave 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
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.
uses
Fin.caseslet 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
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.
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.
- The definition `digraph_directed_cycle_on D s` requires an explicit duplicate-free list of vertices of length at least 2 forming a directed cycle; for the digon {u, v}, the two-element list [u, v] is provided and verified by `simp`.
- Extending the family of k cycles by the digon {u, v} to an indexed family over Fin (k + 1) is handled formally using `Fin.cases`, leading to nested case analyses when checking pairwise disjointness.
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.
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)