digraph_oriented_degree_deficit_overlap_budget
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
- finite_endomap_local_degree_deficit_le_missing_imageFor a finite endomap whose image heads equal the original tails, the sum of positive local tail-count minus head-count deficits is at most…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 1
- digraph_arc_domination_overlap_indegree_deficit_boundIn an oriented loopless r-outregular arc-dominated digraph, the total shortfall of indegrees below r is at most choose(z+1,2), where z is…
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
uses
Classical.choose,Classical.choose_specclassical 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)
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.
uses
Classical.choose,Classical.choose_speclet 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
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.
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
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).
uses
Finset.card_bij,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univ,Subtype.ext,Prod.exthave 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]
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.
uses
Finset.card_bij,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univ,Subtype.ext,Prod.exthave 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]
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.
uses
finite_endomap_local_degree_deficit_le_missing_imagehave 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
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.
uses
digraph_oriented_arc_map_twice_missing_budgethave 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.
- Natural number subtraction in Lean (a - b) truncates at zero, so the differences between outdegree and indegree, as well as the difference between pairs and common-predecessor edges, are non-negative integers by definition.
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.
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