AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_edge_le_sum_choose

theoremverified

The common-predecessor graph has at most the sum over vertices of the number of pairs in each out-neighborhood.

Statement

theorem digraph_common_predecessor_edge_le_sum_choose
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] :
    (digraph_common_predecessor_graph D).edgeFinset.card ≤
      ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2
Source
General form of the auxiliary edge count in arXiv:2610.11517, Proposition 4.3.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The proof bounds the number of edges in the common-predecessor graph by associating each edge to a common predecessor. First, it shows that every edge {u, v} arises from some shared in-neighbor w, so the edge set is covered by the union over all w of the pairs of distinct vertices in the out-neighborhood of w. The result then follows by the union bound and the fact that the number of unordered pairs of distinct vertices in an out-neighborhood of size k is (k choose 2).

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

    For any two vertices u and v, adjacency in the common-predecessor graph means that u ≠ v and there exists a common predecessor w. Decidability of this bounded existential quantifier over the finite vertex type α is inferred automatically from the decidability of adjacency in the underlying digraph D.

    lines 2–4

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

    We work classically and define outs v to be the finset of all out-neighbors of v in D (vertices w such that D.Adj v w). We then define edgesAt v as the finset of unordered pairs s(x, y) formed by distinct elements x, y in outs v, obtained as the image of the off-diagonal pairs (outs v).offDiag under the canonical quotient map.

    lines 10–12

      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. Every edge of the common-predecessor graph belongs to the union over all vertices w of edgesAt w.

    Let e be an edge of the common-predecessor graph. By induction on unordered pairs, e can be written as s(u, v). By the definition of the graph, u ≠ v and there exists a vertex w with w → u and w → v in D. Thus both u and v belong to outs w. Since u ≠ v, the pair (u, v) is in (outs w).offDiag, so its image s(u, v) is in edgesAt w. Hence e belongs to the union of edgesAt w over all vertices w in the graph.

    lines 13–27

    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. The number of edges in the common-predecessor graph is at most the sum over all vertices v of (|outs v| choose 2).

    Since the edge set of the common-predecessor graph is covered by the union of edgesAt v over all v, its cardinality is at most the cardinality of that union (by Finset.card_le_card). By subadditivity of cardinality over unions (Finset.card_biUnion_le), this is bounded by the sum of |edgesAt v| over all vertices v. Finally, each edgesAt v consists of all unordered pairs of distinct elements from outs v, so its cardinality is precisely (|outs v| choose 2) by Sym2.card_image_offDiag. Combining these steps yields the desired bound.

    lines 28–35

    uses Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_congr, Sym2.card_image_offDiag

      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 : α, Nat.choose (outs v).card 2 := by
          apply Finset.sum_congr rfl
          intro v _
          exact Sym2.card_image_offDiag (outs v)
Sym2.ind
To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
SimpleGraph.mem_edgeFinset
An element belongs to the edge finset of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
Finset.mem_biUnion.mpr
If an element belongs to t a for some a in s, then it belongs to the union of the sets t a over a in s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.mem_image.mpr
If an element is the image of some a in s under f, then it belongs to the image of s under f.
Finset.mem_offDiag.mpr
A pair (u, v) belongs to the off-diagonal of s if both u and v belong to s and u ≠ v.
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 is at most the sum of the cardinalities of the individual sets.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Sym2.card_image_offDiag
The number of unordered pairs of distinct elements from a finite set s is (|s| choose 2).

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_general_edge_count_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_edge_le_sum_choose    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] :    (digraph_common_predecessor_graph D).edgeFinset.card ≤      ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 := 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]  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 : α, Nat.choose (outs v).card 2 := by      apply Finset.sum_congr rfl      intro v _      exact Sym2.card_image_offDiag (outs v)
See it in the graphDiscuss this resultChallenge it