digraph_common_predecessor_degree_le_indegree_mul
In an r-outregular finite digraph, the degree of a vertex in the common-predecessor graph is at most (r−1) times its directed indegree.
Statement
theorem digraph_common_predecessor_degree_le_indegree_mul (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) : ∀ v, (digraph_common_predecessor_graph D).degree v ≤ (r - 1) * (Finset.univ.filter fun w => D.Adj w v).card
- Source
- Auxiliary-graph transfer and counting steps for the OP-110 campaign.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
The proof, explained
To bound the degree of a vertex v in the common-predecessor graph of an r-outregular digraph D, we observe that every neighbor u of v shares an in-neighbor w with v, placing u in the out-neighborhood of w minus {v}. Consequently, the neighborhood of v is covered by the union of these punctured out-neighborhoods over all in-neighbors w of v. By r-outregularity, each punctured out-neighborhood has size r - 1. Summing these sizes yields an upper bound of (r - 1) times the indegree of v.
Adjacency in the common-predecessor graph is decidable.
For any two vertices u and v, adjacency in the common-predecessor graph requires u ≠ v and the existence of a common predecessor w. Since the vertex type is finite and edge adjacency in D is decidable, typeclass synthesis automatically infers decidability of this existential condition.
intro u v unfold digraph_common_predecessor_graph infer_instance
Fix a vertex v, and define the set of its in-neighbors and the punctured out-neighborhoods of those in-neighbors.
We fix an arbitrary vertex v and enable classical logic. We define ins to be the finset of all in-neighbors of v in D, and for each w, we define outs(w) to be the out-neighborhood of w with v removed.
classical intro v let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let outs : α → Finset α := fun w => (Finset.univ.filter fun z => D.Adj w z).erase v
The neighbor finset of v in the common-predecessor graph is a subset of the union of outs(w) over all w ∈ ins.
If u is a neighbor of v in the common-predecessor graph, then u ≠ v and there is a common predecessor w such that D.Adj w v and D.Adj w u. Since D.Adj w v, w belongs to ins. Since D.Adj w u and u ≠ v, u belongs to outs(w). Hence u belongs to the union of outs(w) over all w ∈ ins.
uses
SimpleGraph.mem_neighborFinset,Finset.mem_biUnion.mprhave hcover : (digraph_common_predecessor_graph D).neighborFinset v ⊆ ins.biUnion outs := by intro u hu have hu' := (SimpleGraph.mem_neighborFinset _ _ _).mp hu obtain ⟨hne, w, hwv, hwu⟩ := hu' apply Finset.mem_biUnion.mpr refine ⟨w, ?_, ?_⟩ · simp [ins, hwv] · simp [outs, hne.symm, hwu]
For every in-neighbor w ∈ ins, the punctured out-neighborhood outs(w) has cardinality r - 1.
For w ∈ ins, v is an out-neighbor of w. Removing v from the out-neighborhood of w therefore reduces its cardinality by 1. Since w has outdegree r by r-outregularity, the punctured out-neighborhood outs(w) has cardinality r - 1 by linear arithmetic.
uses
Finset.mem_filter.mp,Finset.card_erase_add_onehave hsize : ∀ w ∈ ins, (outs w).card = r - 1 := by intro w hw have hwv : D.Adj w v := (Finset.mem_filter.mp hw).2 have he := Finset.card_erase_add_one (s := Finset.univ.filter fun z => D.Adj w z) (a := v) (by simp [hwv]) have hd := hreg w change (outs w).card + 1 = _ at he omega
The degree of v in the common-predecessor graph is at most (r - 1) times the indegree of v.
The degree of v equals the cardinality of its neighbor finset. By the covering inclusion, this cardinality is at most that of the union of outs(w) over w ∈ ins, which by subadditivity is at most the sum of |outs(w)|. Each term equals r - 1, so the sum evaluates to (r - 1) * |ins|. Finally, |ins| is by definition the indegree of v in D.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_congr,Nat.mul_commrw [← SimpleGraph.card_neighborFinset_eq_degree] calc _ ≤ (ins.biUnion outs).card := Finset.card_le_card hcover _ ≤ ∑ w ∈ ins, (outs w).card := Finset.card_biUnion_le _ = ∑ _w ∈ ins, (r - 1) := by apply Finset.sum_congr rfl intro w hw exact hsize w hw _ = (r - 1) * ins.card := by simp [Nat.mul_comm] _ = (r - 1) * (Finset.univ.filter fun w => D.Adj w v).card := rfl
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v in a graph G if and only if v and w are adjacent in G.
Finset.mem_biUnion.mpr- An element u belongs to the union ⋃_{a ∈ s} t(a) if there is some a ∈ s such that u ∈ t(a).
Finset.mem_filter.mp- An element belonging to a filtered finset satisfies the filtering predicate.
Finset.card_erase_add_one- Removing an element that belongs to a finset yields a finset of cardinality one less.
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex in a graph equals the cardinality of its neighbor finset.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_biUnion_le- The cardinality of a union of finite sets indexed by a finset is at most the sum of their individual cardinalities.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
- An auxiliary instance is proved first to establish decidability of adjacency in the common-predecessor graph, which is required by Mathlib to define neighbor finsets and degrees.
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 in478_digraph_common_predecessor_degree_le_indegree_mul_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_common_predecessor_degree_le_indegree_mul (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) : ∀ v, (digraph_common_predecessor_graph D).degree v ≤ (r - 1) * (Finset.univ.filter fun w => D.Adj w v).card := by classical intro v let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let outs : α → Finset α := fun w => (Finset.univ.filter fun z => D.Adj w z).erase v have hcover : (digraph_common_predecessor_graph D).neighborFinset v ⊆ ins.biUnion outs := by intro u hu have hu' := (SimpleGraph.mem_neighborFinset _ _ _).mp hu obtain ⟨hne, w, hwv, hwu⟩ := hu' apply Finset.mem_biUnion.mpr refine ⟨w, ?_, ?_⟩ · simp [ins, hwv] · simp [outs, hne.symm, hwu] have hsize : ∀ w ∈ ins, (outs w).card = r - 1 := by intro w hw have hwv : D.Adj w v := (Finset.mem_filter.mp hw).2 have he := Finset.card_erase_add_one (s := Finset.univ.filter fun z => D.Adj w z) (a := v) (by simp [hwv]) have hd := hreg w change (outs w).card + 1 = _ at he omega rw [← SimpleGraph.card_neighborFinset_eq_degree] calc _ ≤ (ins.biUnion outs).card := Finset.card_le_card hcover _ ≤ ∑ w ∈ ins, (outs w).card := Finset.card_biUnion_le _ = ∑ _w ∈ ins, (r - 1) := by apply Finset.sum_congr rfl intro w hw exact hsize w hw _ = (r - 1) * ins.card := by simp [Nat.mul_comm] _ = (r - 1) * (Finset.univ.filter fun w => D.Adj w v).card := rfl