AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_graph_edge_count_le

theoremverified

If every vertex of a finite digraph has at most seven out-neighbors, then its common-predecessor graph has at most 21 times as many edges as there are vertices.

Statement

theorem digraph_common_predecessor_graph_edge_count_le
    (α : Type) [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj]
    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) :
    (digraph_common_predecessor_graph D).edgeFinset.card ≤ 21 * Fintype.card α
Source
Counting auxiliary-graph edges by out-neighborhoods, as in arXiv:2610.11517, Proposition 4.3.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

To bound the number of edges in the common-predecessor graph, every edge is associated with a common predecessor of its endpoints. Since each vertex has out-degree at most 7, it can serve as a common predecessor for at most (7 choose 2) = 21 pairs of vertices. Summing this bound over all vertices shows that the graph has at most 21 times as many edges as there are vertices.

  1. The adjacency relation of the common-predecessor graph is decidable. automation

    To allow Lean to form the finite set of edges (edgeFinset), we show that adjacency is decidable. Given vertices u and v, unfolding the definition of the common-predecessor graph expresses adjacency as a conjunction of u ≠ v and an existential quantifier over the finite vertex type α. Because equality and the digraph relation D.Adj are decidable, typeclass resolution infers decidability of this bounded condition.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. For each vertex v, we define outs(v) as the set of its out-neighbors and edgesAt(v) as the set of unordered pairs of distinct out-neighbors.

    We work classically and define two helper functions for any vertex v: outs(v) filters the vertices w such that D has an edge from v to w, and edgesAt(v) is the set of all unordered pairs formed from distinct elements of outs(v) (the image of its off-diagonal under pairing).

    lines 12–14

      classical
      let outs : α → Finset α := fun v => Finset.univ.filter (fun w => D.Adj v w)
      let edgesAt : α → Finset (Sym2 α) := fun v => (outs v).offDiag.image Sym2.mk.uncurry
  3. The edge set of the common-predecessor graph is a subset of the union over all vertices v of edgesAt(v).

    Let e be an edge of the common-predecessor graph. By induction on unordered pairs (Sym2.ind), e can be written as {u, v}. By definition of the edge set (SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet), u ≠ v and there is some common predecessor w such that D has edges from w to u and from w to v. Thus both u and v belong to outs(w), so (u, v) is an off-diagonal pair in outs(w) (Finset.mem_offDiag.mpr). Its image under pairing is {u, v} ∈ edgesAt(w) (Finset.mem_image.mpr). Hence {u, v} belongs to the union of edgesAt(w) over all vertices w (Finset.mem_biUnion.mpr, Finset.mem_univ).

    lines 15–29

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Finset.mem_biUnion.mpr, Finset.mem_univ, Finset.mem_image.mpr, Finset.mem_offDiag.mpr

      have hcover : (digraph_common_predecessor_graph D).edgeFinset ⊆
          (Finset.univ : Finset α).biUnion edgesAt := by
        intro e he
        induction e using Sym2.ind with
        | h u v =>
          rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he
          obtain ⟨hne, w, hwu, hwv⟩ := he
          apply Finset.mem_biUnion.mpr
          refine ⟨w, Finset.mem_univ _, ?_⟩
          apply Finset.mem_image.mpr
          refine ⟨(u,v), ?_, rfl⟩
          apply Finset.mem_offDiag.mpr
          refine ⟨?_, ?_, hne⟩
          · simp [outs, hwu]
          · simp [outs, hwv]
  4. For every vertex v, the set edgesAt(v) contains at most 21 pairs.

    The number of unordered pairs of distinct elements in outs(v) is (card outs(v) choose 2) (Sym2.card_image_offDiag). Since outs(v) has size at most 7 by the out-degree assumption, monotonicity of binomial coefficients (Nat.choose_le_choose) gives |edgesAt(v)| ≤ (7 choose 2) = 21.

    lines 30–35

    uses Sym2.card_image_offDiag, Nat.choose_le_choose

      have hsmall : ∀ v, (edgesAt v).card ≤ 21 := by
        intro v
        change ((outs v).offDiag.image Sym2.mk.uncurry).card ≤ 21
        rw [Sym2.card_image_offDiag]
        have h := Nat.choose_le_choose 2 (hdeg v)
        exact h
  5. The total number of edges in the common-predecessor graph is at most 21 times the number of vertices.

    We bound the number of edges by a chain of four steps: first, the edge count is bounded by the cardinality of the union of all edgesAt(v) (Finset.card_le_card). Second, the size of the union is bounded by the sum of the individual cardinalities (Finset.card_biUnion_le). Third, replacing each cardinality |edgesAt(v)| with its upper bound 21 bounds the sum by the sum of 21 over all vertices (Finset.sum_le_sum). Finally, summing the constant 21 over all vertices of the finite type α evaluates to 21 * card α (Nat.mul_comm).

    lines 36–41

    uses Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_le_sum, Nat.mul_comm

      calc
        (digraph_common_predecessor_graph D).edgeFinset.card ≤
            ((Finset.univ : Finset α).biUnion edgesAt).card := Finset.card_le_card hcover
        _ ≤ ∑ v ∈ (Finset.univ : Finset α), (edgesAt v).card := Finset.card_biUnion_le
        _ ≤ ∑ _v ∈ (Finset.univ : Finset α), 21 := Finset.sum_le_sum (by intros; exact hsmall _)
        _ = 21 * Fintype.card α := by simp [Nat.mul_comm]
Sym2.ind
An induction principle for unordered pairs: to prove a property of an unordered pair, it suffices to prove it for pairs of the form s(x, y).
SimpleGraph.mem_edgeFinset
An edge belongs to the finite set of edges of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet
An unordered pair {v, w} is an edge of a simple graph if and only if v and w are adjacent in the graph.
Finset.mem_biUnion.mpr
An element belongs to a union of finite sets if it belongs to at least one of the constituent sets.
Finset.mem_univ
Every element of a finite type is a member of the universal finset of all elements.
Finset.mem_image.mpr
An element belongs to the image of a finite set under a function if it is the image of some element in that set.
Finset.mem_offDiag.mpr
A pair belongs to the off-diagonal of a finite set if both coordinates belong to the set and are distinct.
Sym2.card_image_offDiag
The number of unordered pairs formed by distinct elements of a finite set s equals (card s choose 2).
Nat.choose_le_choose
The binomial coefficient (n choose k) is a non-decreasing function of n.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other set's cardinality.
Finset.card_biUnion_le
The cardinality of a union of finite sets is at most the sum of the cardinalities of the individual sets.
Finset.sum_le_sum
If a function is pointwise bounded by another function on a finite set, the sum of the first is bounded by the sum of the second.
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 {α : 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_graph_edge_count_le    (α : Type) [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj]    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) :    (digraph_common_predecessor_graph D).edgeFinset.card ≤ 21 * Fintype.card α := by  classical  let outs : α → Finset α := fun v => Finset.univ.filter (fun w => D.Adj v w)  let edgesAt : α → Finset (Sym2 α) := fun v => (outs v).offDiag.image Sym2.mk.uncurry  have hcover : (digraph_common_predecessor_graph D).edgeFinset ⊆      (Finset.univ : Finset α).biUnion edgesAt := by    intro e he    induction e using Sym2.ind with    | h u v =>      rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he      obtain ⟨hne, w, hwu, hwv⟩ := he      apply Finset.mem_biUnion.mpr      refine ⟨w, Finset.mem_univ _, ?_⟩      apply Finset.mem_image.mpr      refine ⟨(u,v), ?_, rfl⟩      apply Finset.mem_offDiag.mpr      refine ⟨?_, ?_, hne⟩      · simp [outs, hwu]      · simp [outs, hwv]  have hsmall : ∀ v, (edgesAt v).card ≤ 21 := by    intro v    change ((outs v).offDiag.image Sym2.mk.uncurry).card ≤ 21    rw [Sym2.card_image_offDiag]    have h := Nat.choose_le_choose 2 (hdeg v)    exact h  calc    (digraph_common_predecessor_graph D).edgeFinset.card ≤        ((Finset.univ : Finset α).biUnion edgesAt).card := Finset.card_le_card hcover    _ ≤ ∑ v ∈ (Finset.univ : Finset α), (edgesAt v).card := Finset.card_biUnion_le    _ ≤ ∑ _v ∈ (Finset.univ : Finset α), 21 := Finset.sum_le_sum (by intros; exact hsmall _)    _ = 21 * Fintype.card α := by simp [Nat.mul_comm]
See it in the graphDiscuss this resultChallenge it