digraph_oriented_safe_set_indegree_bound
In a finite loopless oriented digraph of minimum indegree r, a set to which each outside vertex sends at most two arcs satisfies r times its size at most its number of unordered internal pairs plus twice the outside size.
Statement
theorem digraph_oriented_safe_set_indegree_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (r : ℕ) (hin : ∀ v, r ≤ (Finset.univ.filter fun u => D.Adj u v).card) (C : Finset α) (hsafe : ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) : r * C.card ≤ Nat.choose C.card 2 + 2 * (Fintype.card α - C.card)
- Source
- Boundary counting for the safe-cycle obstruction in OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- digraph_safe17_no_long_safe_setEvery proper set of at least five vertices in the displayed graph has an outside vertex with at least three outneighbors in the set.
- digraph_safe17_every_proper_cycle_unsafeEvery proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.
The proof, explained
The proof bounds r * |C| from above by counting incoming arcs to C partitioned into internal arcs (both endpoints in C) and external arcs (from U = V \ C into C). Because D is loopless and oriented, internal arcs embed injectively into unordered pairs of distinct vertices of C, yielding at most Nat.choose |C| 2 internal arcs. By the safety assumption, each outside vertex sends at most 2 arcs into C, contributing at most 2 * (|V| - |C|) external arcs. Summing the minimum in-degree bound r ≤ deg⁻(v) over all v ∈ C and double-counting arc sums concludes the bound.
Define the internal arcs A, the outside vertices U, and the symmetrization map edge.
We define A ⊆ C × C as the set of directed edges with both endpoints in C, U = V \ C as the set of vertices outside C, and edge as the mapping sending each directed pair (a, b) to the unordered pair s(a, b).
classical let A := (C.product C).filter fun p => D.Adj p.1 p.2 let U := (Finset.univ : Finset α) \ C let edge : α × α → Sym2 α := fun p => s(p.1,p.2)
The symmetrization map edge is injective on the internal arcs A.
Given two arcs (a, b) and (c, d) in A having the same unordered pair image, Sym2.eq_iff.mp states that either (a, b) = (c, d), in which case Prod.ext equates them, or a = d and b = c. In the second case, both (a, b) and (b, a) would be arcs of D, contradicting the hypothesis hori that D is an oriented graph with no bidirectional arcs.
uses
Finset.mem_filter.mp,Sym2.eq_iff.mp,Prod.exthave hinj : Set.InjOn edge (↑A : Set (α × α)) := by rintro ⟨a,b⟩ ha ⟨c,d⟩ hb he have hab : D.Adj a b := (Finset.mem_filter.mp ha).2 have hcd : D.Adj c d := (Finset.mem_filter.mp hb).2 rcases Sym2.eq_iff.mp he with h | h · exact Prod.ext h.1 h.2 · change a = d ∧ b = c at h have hba : D.Adj b a := by rw [h.1,h.2]; exact hcd exact (hori a b hab hba).elim
The image of A under edge consists of unordered pairs of distinct vertices in C.
For every directed edge (a, b) ∈ A, both vertices belong to C. Since D is loopless by hloop, a ≠ b, so (a, b) belongs to the off-diagonal pairs of C. Hence the unordered pair s(a, b) belongs to the image of C.offDiag under the unordered pair constructor.
uses
Finset.mem_image.mp,Finset.mem_filter.mp,Finset.mem_product.mp,Finset.mem_image.mpr,Finset.mem_offDiag.mprhave hsub : A.image edge ⊆ C.offDiag.image Sym2.mk.uncurry := by intro e he obtain ⟨⟨a,b⟩,hab,rfl⟩ := Finset.mem_image.mp he have hp := (Finset.mem_filter.mp hab).1 have ha : a ∈ C := (Finset.mem_product.mp hp).1 have hb : b ∈ C := (Finset.mem_product.mp hp).2 have hab' : D.Adj a b := (Finset.mem_filter.mp hab).2 have hne : a ≠ b := by intro h; subst b; exact hloop a hab' apply Finset.mem_image.mpr exact ⟨(a,b), Finset.mem_offDiag.mpr ⟨ha,hb,hne⟩, rfl⟩
The number of internal arcs |A| is at most Nat.choose |C| 2.
Because edge is injective on A, the size of A equals the size of its image under edge (Finset.card_image_iff.mpr). Since this image is contained in the unordered pairs of distinct elements of C, its cardinality is at most the total number of such pairs, which is Nat.choose |C| 2 by Sym2.card_image_offDiag.
uses
Finset.card_le_card,Finset.card_image_iff.mpr,Sym2.card_image_offDiaghave hA : A.card ≤ Nat.choose C.card 2 := by have hc := Finset.card_le_card hsub rw [Finset.card_image_iff.mpr hinj, Sym2.card_image_offDiag] at hc exact hc
The cardinality of A equals the sum of out-degrees within C of all vertices in C.
Writing |A| as a sum of 1s over all pairs in C × C satisfying D.Adj, Finset.sum_product decomposes the sum over the product into an outer sum over source vertices u ∈ C and an inner sum over target vertices v ∈ C, which is the definition of the internal out-degrees.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_producthave hAcount : A.card = ∑ u ∈ C, (C.filter fun v => D.Adj u v).card := by simp only [A, Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_product C C (fun p => if D.Adj p.1 p.2 then 1 else 0)
The sum of in-degrees within C over all vertices in C equals |A|.
By expressing the sum of internal in-degrees as a double sum of indicator values and interchanging the order of summation using Finset.sum_comm, the sum matches the internal out-degree count, which equals |A|.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_commhave hsumint : (∑ v ∈ C, (C.filter fun u => D.Adj u v).card) = A.card := by rw [hAcount] simp only [Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_comm
The sum of in-degrees from U to C equals the sum of out-degrees from U to C.
Both expressions count the total number of directed edges from U to C. Rewriting the cardinalities as sums of indicators and applying Finset.sum_comm swaps the summation order between target vertices in C and source vertices in U.
uses
Finset.card_eq_sum_ones,Finset.sum_filter,Finset.sum_commhave hsumext : (∑ v ∈ C, (U.filter fun u => D.Adj u v).card) = ∑ u ∈ U, (C.filter fun v => D.Adj u v).card := by simp only [Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_comm
For each vertex v, its total in-degree is the sum of its in-degree from C and its in-degree from U.
The sets of in-neighbors of v located in C and in U are disjoint because U = V \ C. Their union comprises all in-neighbors of v in the entire vertex set, so the sum of their cardinalities equals the total in-degree of v by Finset.card_union_of_disjoint.
uses
Finset.disjoint_left.mpr,Finset.mem_sdiff.mp,Finset.mem_filter.mp,Finset.card_union_of_disjoint,Finset.mem_filter.mphave hsplit (v : α) : (C.filter fun u => D.Adj u v).card + (U.filter fun u => D.Adj u v).card = (Finset.univ.filter fun u => D.Adj u v).card := by have hd : Disjoint (C.filter fun u => D.Adj u v) (U.filter fun u => D.Adj u v) := by apply Finset.disjoint_left.mpr intro x hx hy exact (Finset.mem_sdiff.mp (Finset.mem_filter.mp hy).1).2 (Finset.mem_filter.mp hx).1 rw [← Finset.card_union_of_disjoint hd] congr 1 ext x by_cases hx : x ∈ C <;> simp [U, hx]
r * |C| is at most |A| plus the total number of arcs from U to C.
Since each vertex in C has total in-degree at least r by hin, summing over all v ∈ C gives r * |C| ≤ ∑_{v ∈ C} deg⁻(v). Decomposing each in-degree into internal and external contributions splits the sum into internal in-degrees (which sum to |A|) and external in-degrees (which equal the out-degrees from U to C).
uses
Nat.mul_comm,Finset.sum_le_sum,Finset.sum_add_distribhave htotal : r * C.card ≤ A.card + ∑ u ∈ U, (C.filter fun v => D.Adj u v).card := by calc r * C.card = ∑ _v ∈ C, r := by simp [Nat.mul_comm] _ ≤ ∑ v ∈ C, (Finset.univ.filter fun u => D.Adj u v).card := by exact Finset.sum_le_sum fun v _ => hin v _ = (∑ v ∈ C, (C.filter fun u => D.Adj u v).card) + (∑ v ∈ C, (U.filter fun u => D.Adj u v).card) := by simp_rw [← hsplit] rw [Finset.sum_add_distrib] _ = _ := by rw [hsumint, hsumext]
The cardinality of U is |V| - |C|.
Since U is defined as the set difference Finset.univ \ C, its size is the total number of vertices |V| minus |C| by Finset.card_sdiff.
uses
Finset.card_sdiffhave hU : U.card = Fintype.card α - C.card := by simp [U, Finset.card_sdiff]
The total number of arcs from U to C is at most 2 * |U|.
By the safe set hypothesis hsafe, every vertex u ∉ C sends at most 2 arcs into C. Summing this upper bound of 2 over all vertices u ∈ U yields at most 2 * |U|.
uses
Finset.sum_le_sum,Finset.mem_sdiff.mp,Nat.mul_commhave hexternal : (∑ u ∈ U, (C.filter fun v => D.Adj u v).card) ≤ 2 * U.card := by calc _ ≤ ∑ _u ∈ U, 2 := by apply Finset.sum_le_sum intro u hu exact hsafe u (Finset.mem_sdiff.mp hu).2 _ = _ := by simp [Nat.mul_comm]
r * |C| ≤ Nat.choose |C| 2 + 2 * (|V| - |C|). automation
Substituting |U| = |V| - |C| into the external arc bound gives at most 2 * (|V| - |C|) external arcs. Combining this with the total in-degree lower bound r * |C| ≤ |A| + (external arcs) and the internal arc bound |A| ≤ Nat.choose |C| 2, linear integer arithmetic (omega) finishes the proof.
rw [hU] at hexternal omega
Finset.card_le_card- The cardinality of a subset is less than or equal to the cardinality of the superset.
Finset.card_image_iff.mpr- If a function is injective on a finite set, the cardinality of its image equals the cardinality of the domain set.
Sym2.card_image_offDiag- The number of unordered pairs of distinct elements from a finite set s is Nat.choose (card s) 2.
Finset.card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over each of its elements.
Finset.sum_filter- Summing a function over elements satisfying a predicate equals summing the function guarded by an if-then-else condition over the entire set.
Finset.sum_product- A sum over a Cartesian product of two finite sets equals the iterated double sum over each set.
Finset.sum_comm- The order of summation in a finite double sum can be interchanged.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first set belongs to the second set.
Finset.mem_sdiff.mp- If an element belongs to the set difference s \ t, it belongs to s and does not belong to t.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.mul_comm- Multiplication of natural numbers is commutative.
Finset.sum_le_sum- If each term in a finite sum is bounded by the corresponding term in another sum, the total sum respects the inequality.
Finset.sum_add_distrib- A sum of sums of two functions over a finite set distributes into the sum of the first function plus the sum of the second function.
Finset.card_sdiff- The cardinality of a set difference t \ s equals the cardinality of t minus the cardinality of s ∩ t.
Finset.mem_filter.mp- If an element belongs to a filtered finset, it belongs to the base finset and satisfies the filtering predicate.
Sym2.eq_iff.mp- Two unordered pairs s(a, b) and s(c, d) are equal if and only if either (a = c and b = d) or (a = d and b = c).
Prod.ext- Two ordered pairs are equal if their corresponding components are equal.
Finset.mem_image.mp- An element belongs to the image of a finset under a function if and only if it is the image of some element in the domain finset.
Finset.mem_product.mp- An element belongs to a Cartesian product of two finsets if and only if its first component is in the first set and its second is in the second.
Finset.mem_image.mpr- Constructs a membership proof in the image of a finset given a witness in the domain.
Finset.mem_offDiag.mpr- An ordered pair belongs to the off-diagonal of a finset if and only if both components belong to the finset and are distinct.
- The final step concludes via linear arithmetic automation (`omega`), combining the total in-degree lower bound with the upper bounds on internal and external arcs.
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_oriented_safe_set_indegree_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (r : ℕ) (hin : ∀ v, r ≤ (Finset.univ.filter fun u => D.Adj u v).card) (C : Finset α) (hsafe : ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) : r * C.card ≤ Nat.choose C.card 2 + 2 * (Fintype.card α - C.card) := by classical let A := (C.product C).filter fun p => D.Adj p.1 p.2 let U := (Finset.univ : Finset α) \ C let edge : α × α → Sym2 α := fun p => s(p.1,p.2) have hinj : Set.InjOn edge (↑A : Set (α × α)) := by rintro ⟨a,b⟩ ha ⟨c,d⟩ hb he have hab : D.Adj a b := (Finset.mem_filter.mp ha).2 have hcd : D.Adj c d := (Finset.mem_filter.mp hb).2 rcases Sym2.eq_iff.mp he with h | h · exact Prod.ext h.1 h.2 · change a = d ∧ b = c at h have hba : D.Adj b a := by rw [h.1,h.2]; exact hcd exact (hori a b hab hba).elim have hsub : A.image edge ⊆ C.offDiag.image Sym2.mk.uncurry := by intro e he obtain ⟨⟨a,b⟩,hab,rfl⟩ := Finset.mem_image.mp he have hp := (Finset.mem_filter.mp hab).1 have ha : a ∈ C := (Finset.mem_product.mp hp).1 have hb : b ∈ C := (Finset.mem_product.mp hp).2 have hab' : D.Adj a b := (Finset.mem_filter.mp hab).2 have hne : a ≠ b := by intro h; subst b; exact hloop a hab' apply Finset.mem_image.mpr exact ⟨(a,b), Finset.mem_offDiag.mpr ⟨ha,hb,hne⟩, rfl⟩ have hA : A.card ≤ Nat.choose C.card 2 := by have hc := Finset.card_le_card hsub rw [Finset.card_image_iff.mpr hinj, Sym2.card_image_offDiag] at hc exact hc have hAcount : A.card = ∑ u ∈ C, (C.filter fun v => D.Adj u v).card := by simp only [A, Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_product C C (fun p => if D.Adj p.1 p.2 then 1 else 0) have hsumint : (∑ v ∈ C, (C.filter fun u => D.Adj u v).card) = A.card := by rw [hAcount] simp only [Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_comm have hsumext : (∑ v ∈ C, (U.filter fun u => D.Adj u v).card) = ∑ u ∈ U, (C.filter fun v => D.Adj u v).card := by simp only [Finset.card_eq_sum_ones, Finset.sum_filter] exact Finset.sum_comm have hsplit (v : α) : (C.filter fun u => D.Adj u v).card + (U.filter fun u => D.Adj u v).card = (Finset.univ.filter fun u => D.Adj u v).card := by have hd : Disjoint (C.filter fun u => D.Adj u v) (U.filter fun u => D.Adj u v) := by apply Finset.disjoint_left.mpr intro x hx hy exact (Finset.mem_sdiff.mp (Finset.mem_filter.mp hy).1).2 (Finset.mem_filter.mp hx).1 rw [← Finset.card_union_of_disjoint hd] congr 1 ext x by_cases hx : x ∈ C <;> simp [U, hx] have htotal : r * C.card ≤ A.card + ∑ u ∈ U, (C.filter fun v => D.Adj u v).card := by calc r * C.card = ∑ _v ∈ C, r := by simp [Nat.mul_comm] _ ≤ ∑ v ∈ C, (Finset.univ.filter fun u => D.Adj u v).card := by exact Finset.sum_le_sum fun v _ => hin v _ = (∑ v ∈ C, (C.filter fun u => D.Adj u v).card) + (∑ v ∈ C, (U.filter fun u => D.Adj u v).card) := by simp_rw [← hsplit] rw [Finset.sum_add_distrib] _ = _ := by rw [hsumint, hsumext] have hU : U.card = Fintype.card α - C.card := by simp [U, Finset.card_sdiff] have hexternal : (∑ u ∈ U, (C.filter fun v => D.Adj u v).card) ≤ 2 * U.card := by calc _ ≤ ∑ _u ∈ U, 2 := by apply Finset.sum_le_sum intro u hu exact hsafe u (Finset.mem_sdiff.mp hu).2 _ = _ := by simp [Nat.mul_comm] rw [hU] at hexternal omega