AFTD Auto-Formalizing Theoretical Domains

digraph_clean_center_indegree_ge_outdegree

theoremverified

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

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.

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

    lines 10–13

    uses Classical.choose

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

    lines 14–16

    uses Classical.choose_spec

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

    lines 17–25

    uses Finset.mem_filter.mp

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

    lines 26–29

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ

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

    line 30

    uses Finset.card_le_card_of_injOn

      exact 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

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