digraph_clean_center_indegree_ge_outdegree
In a finite loopless arc-dominated digraph, a vertex with a clean out-neighborhood has indegree at least its outdegree.
Statement
theorem digraph_clean_center_indegree_ge_outdegree (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (v : α) (hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ p, D.Adj p a → D.Adj p b → p = v) : (Finset.univ.filter fun w => D.Adj v w).card ≤ (Finset.univ.filter fun w => D.Adj w v).card
- Source
- Collision counting for the small-overlap route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_linear_arc_dominated_balancedEvery finite loopless linear arc-dominated digraph is balanced, without an outregularity assumption.
The proof, explained
To show that the outdegree of v is at most its indegree, we construct an injective mapping from the out-neighborhood of v to its in-neighborhood. For each out-neighbor w of v, the arc-domination property provides a vertex f(w) that dominates both v and w, which places f(w) in the in-neighborhood of v. If two distinct out-neighbors a and b had the same image f(a) = f(b), then f(a) would be a common predecessor of both, forcing f(a) = v by the clean neighborhood condition and creating a self-loop v → v, which contradicts looplessness. Since f is injective, the cardinality of the out-neighborhood is at most the cardinality of the in-neighborhood.
Define the out-neighborhood outs, the in-neighborhood ins, and a candidate predecessor function f.
We enable classical logic (line 10) and define the finite sets outs = {w | v → w} and ins = {w | w → v} representing the out-neighbors and in-neighbors of v (lines 11–12). For each vertex w, if v → w, the arc-domination hypothesis (hdom) guarantees some vertex dominating both v and w; using Classical.choose, we pick one such common in-neighbor as f(w), setting f(w) = v otherwise (line 13).
uses
Classical.chooseclassical let outs : Finset α := Finset.univ.filter fun w => D.Adj v w let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let f : α → α := fun w => if h : D.Adj v w then Classical.choose (hdom v w h) else v
For every out-neighbor w of v, f(w) dominates both v and w.
Let w be an out-neighbor of v (line 15). By definition, f(w) evaluates to the witness chosen by Classical.choose for the arc v → w. Applying Classical.choose_spec to the arc-domination hypothesis on (v, w), we simplify the definition of f to establish that f(w) → v and f(w) → w (line 16).
uses
Classical.choose_spechave hf : ∀ w, D.Adj v w → D.Adj (f w) v ∧ D.Adj (f w) w := by intro w hw simpa [f, hw] using Classical.choose_spec (hdom v w hw)
The function f is injective on the out-neighborhood outs.
Let a, b ∈ outs be out-neighbors such that f(a) = f(b) (line 18), so v → a and v → b (lines 19–20). Suppose, for contradiction, that a ≠ b (line 21). By the property of f, f(a) dominates both v and a, and f(b) dominates both v and b (lines 22–23). Since f(a) = f(b), f(a) is a common in-neighbor of both a and b. Because the out-neighborhood of v is clean (hclean), any common in-neighbor of distinct out-neighbors a and b must be v, which forces f(a) = v (line 24). But f(a) → v, which means v → v—contradicting the assumption that the digraph has no self-loops (hloop, line 25). Thus a = b.
uses
Finset.mem_filter.mphave hinj : (outs : Set α).InjOn f := by intro a ha b hb hab have ha' : D.Adj v a := (Finset.mem_filter.mp ha).2 have hb' : D.Adj v b := (Finset.mem_filter.mp hb).2 by_contra hne have hfa := hf a ha' have hfb := hf b hb' have heq : f a = v := hclean a b hne ha' hb' (f a) hfa.2 (hab.symm ▸ hfb.2) exact hloop v (heq ▸ hfa.1)
The function f maps outs into ins.
Let w ∈ outs, so v → w (lines 27–28). By the construction of f, f(w) is an in-neighbor of v (that is, f(w) → v). Therefore, f(w) belongs to ins (line 29).
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univhave hm : Set.MapsTo f (outs : Set α) (ins : Set α) := by intro w hw have hw' : D.Adj v w := (Finset.mem_filter.mp hw).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (hf w hw').1⟩
The outdegree of v is at most the indegree of v.
Since f is an injection from the finite set outs into the finite set ins, the cardinality of outs is at most that of ins by Finset.card_le_card_of_injOn.
uses
Finset.card_le_card_of_injOnexact Finset.card_le_card_of_injOn f hm hinj
Classical.choose- Given an existential proposition ∃ x, P x, chooses an arbitrary witness satisfying P.
Classical.choose_spec- The witness selected by Classical.choose satisfies the underlying predicate.
Finset.mem_filter.mp- If an element belongs to Finset.filter p s, then it belongs to s and satisfies the predicate p.
Finset.mem_filter.mpr- If an element belongs to s and satisfies the predicate p, then it belongs to Finset.filter p s.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.card_le_card_of_injOn- If f maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
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_clean_center_indegree_ge_outdegree (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (v : α) (hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ p, D.Adj p a → D.Adj p b → p = v) : (Finset.univ.filter fun w => D.Adj v w).card ≤ (Finset.univ.filter fun w => D.Adj w v).card := by classical let outs : Finset α := Finset.univ.filter fun w => D.Adj v w let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let f : α → α := fun w => if h : D.Adj v w then Classical.choose (hdom v w h) else v have hf : ∀ w, D.Adj v w → D.Adj (f w) v ∧ D.Adj (f w) w := by intro w hw simpa [f, hw] using Classical.choose_spec (hdom v w hw) have hinj : (outs : Set α).InjOn f := by intro a ha b hb hab have ha' : D.Adj v a := (Finset.mem_filter.mp ha).2 have hb' : D.Adj v b := (Finset.mem_filter.mp hb).2 by_contra hne have hfa := hf a ha' have hfb := hf b hb' have heq : f a = v := hclean a b hne ha' hb' (f a) hfa.2 (hab.symm ▸ hfb.2) exact hloop v (heq ▸ hfa.1) have hm : Set.MapsTo f (outs : Set α) (ins : Set α) := by intro w hw have hw' : D.Adj v w := (Finset.mem_filter.mp hw).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (hf w hw').1⟩ exact Finset.card_le_card_of_injOn f hm hinj