AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_degree_deficit_overlap_budget

theoremverified

In every finite loopless oriented arc-dominated digraph, twice the sum of positive outdegree-minus-indegree deficits is at most three times the repeated common-predecessor incidence count.

Statement

theorem digraph_oriented_degree_deficit_overlap_budget
    (α : 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)
    (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) :
    2 * (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card -
      (Finset.univ.filter fun w => D.Adj w v).card)) ≤
      3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
        (digraph_common_predecessor_graph D).edgeFinset.card)
Source
Overlap-to-regularity route for the four-cycle campaign; experiment 13230.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof bounds the total outdegree-minus-indegree deficit in an arc-dominated oriented digraph by analyzing a discrete dynamical system on the set of arcs. Using arc-domination, each directed edge (u, v) is mapped to (p, u) where p is a chosen common predecessor of u and v, yielding an endomap f on arcs whose head matches the tail of the input arc. By a general endomap lemma, the sum of degree deficits is bounded by the number of arcs outside the image of f. Finally, this missing-image count is connected to the common-predecessor graph through an overlap budget lemma, and linear arithmetic establishes the required inequality.

  1. Adjacency in the common-predecessor graph of D is decidable.

    For any pair of vertices u and v, adjacency in digraph_common_predecessor_graph D is defined by u ≠ v and the existence of a common predecessor w. Since α is a finite type with decidable equality and D.Adj is decidable, typeclass inference (infer_instance) automatically synthesizes decidability of this bounded existential formula.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Every directed arc has a chosen common predecessor of its endpoints.

    By the arc-domination hypothesis hdom, for every arc u → v there exists some vertex p with p → u and p → v. Using classical choice (Classical.choose), we define choose u v to select such a predecessor, and Classical.choose_spec certifies that choose u v is adjacent to both u and v.

    lines 16–20

    uses Classical.choose, Classical.choose_spec

      classical
      let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u
      have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by
        intro u v h
        simpa [choose, h] using Classical.choose_spec (hdom u v h)
  3. An endomap on arcs and a retraction on its image are well-defined.

    We define the type Arc of directed edges, an endomap f sending each arc (u, v) to (choose u v, u), and a pseudoinverse r mapping each arc to an f-preimage whenever one exists. Case-splitting on whether a preimage exists, Classical.choose_spec confirms f (r (f x)) = f x since x is always an available preimage.

    lines 21–31

    uses Classical.choose, Classical.choose_spec

      let Arc := {e : α × α // D.Adj e.1 e.2}
      let f : Arc → Arc := fun e => ⟨(choose e.val.1 e.val.2,e.val.1), (hchoice _ _ e.property).1⟩
      let r : Arc → Arc := fun y => if h : ∃ x, f x = y then Classical.choose h else y
      have hr : ∀ x, f (r (f x)) = f x := by
        intro x
        dsimp [r]
        split
        · rename_i h
          exact Classical.choose_spec h
        · rename_i h
          exact (h ⟨x,rfl⟩).elim
  4. The head of f(e) equals the tail of e for every arc e.

    By definition, the tail of (u, v) is u and its head is v. Since f(u, v) is defined as (choose u v, u), its head is u, which coincides with the tail of the input arc by definition.

    lines 32–34

      let tail : Arc → α := fun e => e.val.1
      let head : Arc → α := fun e => e.val.2
      have hf : ∀ e, head (f e) = tail e := by intro e; rfl
  5. For each vertex v, the number of arcs with tail v equals the outdegree of v in D.

    We construct a bijection between the set of arcs with tail v and the out-neighborhood {w | D.Adj v w} using Finset.card_bij, mapping each arc to its head. The map is well-defined because e is an arc starting at v; injective because an arc is uniquely determined by its endpoints (Subtype.ext, Prod.ext); and surjective because any out-neighbor w gives a valid arc (v, w).

    lines 35–51

    uses Finset.card_bij, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ, Subtype.ext, Prod.ext

      have hout (v : α) : (Finset.univ.filter fun e : Arc => tail e = v).card =
          (Finset.univ.filter fun w => D.Adj v w).card := by
        apply Finset.card_bij (fun e _ => e.val.2)
        · intro e he
          have ht : e.val.1 = v := (Finset.mem_filter.mp he).2
          exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩
        · intro e he e' he' hh
          apply Subtype.ext
          apply Prod.ext
          · have h1 : e.val.1 = v := (Finset.mem_filter.mp he).2
            have h2 : e'.val.1 = v := (Finset.mem_filter.mp he').2
            exact h1.trans h2.symm
          · exact hh
        · intro w hw
          have ha : D.Adj v w := (Finset.mem_filter.mp hw).2
          refine ⟨⟨(v,w),ha⟩, ?_, rfl⟩
          simp [tail]
  6. For each vertex v, the number of arcs with head v equals the indegree of v in D.

    Analogously, Finset.card_bij maps each arc with head v to its tail, establishing a bijection with the in-neighborhood {w | D.Adj w v}. Injectivity again follows from Subtype.ext and Prod.ext, and surjectivity from the arc (w, v) for any in-neighbor w.

    lines 52–68

    uses Finset.card_bij, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ, Subtype.ext, Prod.ext

      have hin (v : α) : (Finset.univ.filter fun e : Arc => head e = v).card =
          (Finset.univ.filter fun w => D.Adj w v).card := by
        apply Finset.card_bij (fun e _ => e.val.1)
        · intro e he
          have ht : e.val.2 = v := (Finset.mem_filter.mp he).2
          exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩
        · intro e he e' he' hh
          apply Subtype.ext
          apply Prod.ext
          · exact hh
          · have h1 : e.val.2 = v := (Finset.mem_filter.mp he).2
            have h2 : e'.val.2 = v := (Finset.mem_filter.mp he').2
            exact h1.trans h2.symm
        · intro w hw
          have ha : D.Adj w v := (Finset.mem_filter.mp hw).2
          refine ⟨⟨(w,v),ha⟩, ?_, rfl⟩
          simp [head]
  7. The sum of degree deficits is bounded by the number of arcs missing from the image of f.

    Applying the general lemma finite_endomap_local_degree_deficit_le_missing_image to the endomap f and retraction r on Arc bounds the sum of local degree differences by the size of Arc \ f(Arc). Rewriting with hout and hin identifies these differences with the vertex outdegree-minus-indegree deficits.

    lines 69–73

    uses finite_endomap_local_degree_deficit_le_missing_image

      have hfinite := finite_endomap_local_degree_deficit_le_missing_image Arc α f r tail head hr hf
      have hsum : (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card -
          (Finset.univ.filter fun w => D.Adj w v).card)) ≤
          ((Finset.univ : Finset Arc) \ Finset.univ.image f).card := by
        simpa only [hout,hin] using hfinite
  8. Twice the sum of degree deficits is at most three times the repeated common-predecessor incidence count. automation

    The lemma digraph_oriented_arc_map_twice_missing_budget bounds twice the size of the missing image Arc \ f(Arc) by three times the excess common-predecessor pairs. Combining this with the degree deficit bound multiplied by 2, linear arithmetic (omega) closes the goal.

    lines 74–76

    uses digraph_oriented_arc_map_twice_missing_budget

      have hbudget := digraph_oriented_arc_map_twice_missing_budget α D choose hloop hori hchoice
      change 2 * ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤ _ at hbudget
      omega
Classical.choose
Given an existence proof ∃ x, p x, returns an arbitrary witness satisfying p.
Classical.choose_spec
States that the witness selected by Classical.choose satisfies the given predicate.
Finset.card_bij
Two finite sets have equal cardinality if there exists an assignment between them that is well-defined, injective, and surjective.
Finset.mem_filter.mp
Extracts membership in the base finset and satisfaction of the predicate from membership in a filtered finset.
Finset.mem_filter.mpr
Constructs membership in a filtered finset from membership in the base finset and satisfaction of the predicate.
Finset.mem_univ
States that every element of a finite type belongs to the universal finset Finset.univ.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Prod.ext
Two ordered pairs are equal if their corresponding components are equal.
finite_endomap_local_degree_deficit_le_missing_image
For an endomap f on a finite set of arcs over vertices with a pseudo-inverse r on the image and satisfying head ∘ f = tail, the sum of local outdegree minus indegree deficits is at most the number of arcs missing from the image of f.
digraph_oriented_arc_map_twice_missing_budget
In a finite loopless oriented digraph where every arc has a chosen common predecessor, twice the number of arcs missing from the canonical predecessor endomap is at most three times the difference between the sum of pairs of outdegrees and the number of edges in the common-predecessor graph.

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

private instance in516_deficit_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α)    [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_oriented_degree_deficit_overlap_budget    (α : 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)    (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) :    2 * (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card -      (Finset.univ.filter fun w => D.Adj w v).card)) ≤      3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -        (digraph_common_predecessor_graph D).edgeFinset.card) := by  classical  let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u  have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by    intro u v h    simpa [choose, h] using Classical.choose_spec (hdom u v h)  let Arc := {e : α × α // D.Adj e.1 e.2}  let f : Arc → Arc := fun e => ⟨(choose e.val.1 e.val.2,e.val.1), (hchoice _ _ e.property).1⟩  let r : Arc → Arc := fun y => if h : ∃ x, f x = y then Classical.choose h else y  have hr : ∀ x, f (r (f x)) = f x := by    intro x    dsimp [r]    split    · rename_i h      exact Classical.choose_spec h    · rename_i h      exact (h ⟨x,rfl⟩).elim  let tail : Arc → α := fun e => e.val.1  let head : Arc → α := fun e => e.val.2  have hf : ∀ e, head (f e) = tail e := by intro e; rfl  have hout (v : α) : (Finset.univ.filter fun e : Arc => tail e = v).card =      (Finset.univ.filter fun w => D.Adj v w).card := by    apply Finset.card_bij (fun e _ => e.val.2)    · intro e he      have ht : e.val.1 = v := (Finset.mem_filter.mp he).2      exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩    · intro e he e' he' hh      apply Subtype.ext      apply Prod.ext      · have h1 : e.val.1 = v := (Finset.mem_filter.mp he).2        have h2 : e'.val.1 = v := (Finset.mem_filter.mp he').2        exact h1.trans h2.symm      · exact hh    · intro w hw      have ha : D.Adj v w := (Finset.mem_filter.mp hw).2      refine ⟨⟨(v,w),ha⟩, ?_, rfl⟩      simp [tail]  have hin (v : α) : (Finset.univ.filter fun e : Arc => head e = v).card =      (Finset.univ.filter fun w => D.Adj w v).card := by    apply Finset.card_bij (fun e _ => e.val.1)    · intro e he      have ht : e.val.2 = v := (Finset.mem_filter.mp he).2      exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩    · intro e he e' he' hh      apply Subtype.ext      apply Prod.ext      · exact hh      · have h1 : e.val.2 = v := (Finset.mem_filter.mp he).2        have h2 : e'.val.2 = v := (Finset.mem_filter.mp he').2        exact h1.trans h2.symm    · intro w hw      have ha : D.Adj w v := (Finset.mem_filter.mp hw).2      refine ⟨⟨(w,v),ha⟩, ?_, rfl⟩      simp [head]  have hfinite := finite_endomap_local_degree_deficit_le_missing_image Arc α f r tail head hr hf  have hsum : (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card -      (Finset.univ.filter fun w => D.Adj w v).card)) ≤      ((Finset.univ : Finset Arc) \ Finset.univ.image f).card := by    simpa only [hout,hin] using hfinite  have hbudget := digraph_oriented_arc_map_twice_missing_budget α D choose hloop hori hchoice  change 2 * ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤ _ at hbudget  omega
See it in the graphDiscuss this resultChallenge it