AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_degree_le_indegree_mul

theoremverified

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

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.

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

    lines 2–4

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. 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.

    lines 11–14

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

    lines 15–22

    uses SimpleGraph.mem_neighborFinset, Finset.mem_biUnion.mpr

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

    lines 23–29

    uses Finset.mem_filter.mp, Finset.card_erase_add_one

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

    lines 30–39

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_congr, Nat.mul_comm

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

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