AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_overlap_incidence_identity

theoremverified

For a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its out-neighborhoods minus the number of distinct common-predecessor edges.

Statement

theorem digraph_common_predecessor_overlap_incidence_identity
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] :
    (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,
      ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1)) =
    (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card
Source
Exact incidence identity needed for the small-overlap structural route to OP-110.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 7

The proof, explained

The proof expresses the edge set of the common-predecessor graph as the union over all vertices u of the sets N(u) of unordered pairs of distinct out-neighbors of u. Each set N(u) has cardinality (card (outs u) choose 2), and for any edge e, the vertices p with e ∈ N(p) are precisely the common predecessors of the endpoints of e. Applying the general finite-family overlap multiplicity identity and subtracting the total number of edges completes the proof.

  1. Adjacency in the common-predecessor graph of D is decidable for all pairs of vertices.

    For any two vertices u and v, unfolding the definition of the common-predecessor graph shows that u and v are adjacent if and only if u ≠ v and there exists some w adjacent in D to both u and v. Because equality on α and adjacency in D are decidable and α is finite, this existential condition over α is decidable, and Lean synthesizes the instance automatically via typeclass inference.

    lines 3–5

    uses digraph_common_predecessor_graph

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Define the out-neighborhood outs(u) and the set N(u) of unordered pairs of distinct out-neighbors for each vertex u.

    Working classically, for each vertex u ∈ α we define outs(u) as the finset of out-neighbors {w ∈ α | D.Adj u w}. We then define N(u) as the set of unordered pairs of distinct out-neighbors of u, obtained by taking the off-diagonal pairs (x, y) with x ≠ y from outs(u) and mapping them into Sym2 α via the unordered pair constructor.

    lines 13–15

      classical
      let outs : α → Finset α := fun u => Finset.univ.filter (fun w => D.Adj u w)
      let N : α → Finset (Sym2 α) := fun u => (outs u).offDiag.image Sym2.mk.uncurry
  3. An unordered pair s(a, b) belongs to N(u) if and only if a ≠ b and u is adjacent to both a and b.

    We prove both directions of the equivalence. If s(a, b) ∈ N(u), it is the image of some pair (x, y) in the off-diagonal of outs(u) by Finset.mem_image.mp. By Finset.mem_offDiag.mp and Finset.mem_filter.mp, x ≠ y and u is adjacent to both x and y. By Sym2.eq_iff.mp, either (x = a ∧ y = b) or (x = b ∧ y = a), so a ≠ b, D.Adj u a, and D.Adj u b. Conversely, if a ≠ b and u is adjacent to both a and b, then a, b ∈ outs(u) are distinct, so (a, b) belongs to the off-diagonal by Finset.mem_offDiag.mpr, and its image is s(a, b) ∈ N(u) by Finset.mem_image.mpr.

    lines 16–30

    uses Finset.mem_image.mp, Finset.mem_offDiag.mp, Finset.mem_filter.mp, Sym2.eq_iff.mp, Finset.mem_image.mpr, Finset.mem_offDiag.mpr

      have hN : ∀ u a b, s(a,b) ∈ N u ↔ a ≠ b ∧ D.Adj u a ∧ D.Adj u b := by
        intro u a b
        constructor
        · intro h
          obtain ⟨⟨x,y⟩, hxy, he⟩ := Finset.mem_image.mp h
          obtain ⟨hx,hy,hne⟩ := Finset.mem_offDiag.mp hxy
          have hx' : D.Adj u x := (Finset.mem_filter.mp hx).2
          have hy' : D.Adj u y := (Finset.mem_filter.mp hy).2
          rcases Sym2.eq_iff.mp he with ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩
          · exact ⟨hne,hx',hy'⟩
          · exact ⟨hne.symm,hy',hx'⟩
        · rintro ⟨hne, ha, hb⟩
          apply Finset.mem_image.mpr
          refine ⟨(a,b), Finset.mem_offDiag.mpr ?_, rfl⟩
          exact ⟨by simp [outs,ha], by simp [outs,hb], hne⟩
  4. The union of N(u) over all vertices u equals the edge set of the common-predecessor graph.

    By extensionality, an unordered pair e ∈ Sym2 α belongs to ⋃_u N(u) if and only if it is an edge of the common-predecessor graph. Representing e as s(a, b) by induction on unordered pairs (Sym2.ind), s(a, b) is an edge if and only if a ≠ b and some u is adjacent to both a and b (by SimpleGraph.mem_edgeFinset and SimpleGraph.mem_edgeSet). On the other hand, s(a, b) ∈ ⋃_u N(u) means ∃ u, s(a, b) ∈ N(u) (by Finset.mem_biUnion, Finset.mem_univ, and true_and), which by the previous characterization of N(u) is equivalent to a ≠ b ∧ ∃ u, D.Adj u a ∧ D.Adj u b. The two conditions match.

    lines 31–44

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Finset.mem_biUnion, Finset.mem_univ, true_and

      have hE : (Finset.univ : Finset α).biUnion N =
          (digraph_common_predecessor_graph D).edgeFinset := by
        ext e
        induction e using Sym2.ind with
        | h a b =>
          rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]
          change s(a,b) ∈ (Finset.univ : Finset α).biUnion N ↔
            a ≠ b ∧ ∃ u, D.Adj u a ∧ D.Adj u b
          simp only [Finset.mem_biUnion, Finset.mem_univ, true_and, hN]
          constructor
          · rintro ⟨u,hne,ha,hb⟩
            exact ⟨hne,u,ha,hb⟩
          · rintro ⟨hne,u,ha,hb⟩
            exact ⟨u,hne,ha,hb⟩
  5. For every edge e of the common-predecessor graph, the vertices p with e ∈ N(p) are exactly the common predecessors of all endpoints of e.

    Let e be an edge in the common-predecessor graph. Writing e = s(a, b) via Sym2.ind, the edge assumption gives a ≠ b by SimpleGraph.mem_edgeFinset and SimpleGraph.mem_edgeSet. For any vertex p, membership s(a, b) ∈ N(p) reduces by Finset.mem_filter, Finset.mem_univ, true_and, and the characterization of N to a ≠ b ∧ D.Adj p a ∧ D.Adj p b. If this holds, then for any x ∈ s(a, b), either x = a or x = b by Sym2.mem_iff.mp, so D.Adj p x holds in either case. Conversely, if D.Adj p x for all x ∈ s(a, b), evaluating at a via Sym2.mem_mk_left and at b via Sym2.mem_mk_right gives D.Adj p a and D.Adj p b, which with a ≠ b implies s(a, b) ∈ N(p).

    lines 45–62

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Finset.mem_filter, Finset.mem_univ, true_and, Sym2.mem_iff.mp, Sym2.mem_mk_left, Sym2.mem_mk_right

      have hparent : ∀ e ∈ (digraph_common_predecessor_graph D).edgeFinset,
          (Finset.univ.filter fun p => e ∈ N p) =
            (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x) := by
        intro e he
        induction e using Sym2.ind with
        | h a b =>
          have hne : a ≠ b := by
            rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he
            exact he.1
          ext p
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, hN]
          constructor
          · rintro ⟨_,ha,hb⟩ x hx
            rcases Sym2.mem_iff.mp hx with rfl | rfl
            · exact ha
            · exact hb
          · intro h
            exact ⟨hne, h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩
  6. The sum of (card (outs u) choose 2) over all vertices equals the number of edges plus the sum of excess multiplicities over all edges.

    We instantiate finite_family_overlap_multiplicity_identity for the family N(u) over all vertices u. This identity relates the sum of sizes ∑_u |N(u)| to the cardinality of their union |⋃_u N(u)| plus the sum over e in the union of (|{p | e ∈ N(p)}| - 1). We rewrite the union as the edge set of the common-predecessor graph using our previous identification. Next, for each vertex u, the number of unordered pairs |N(u)| is given by Nat.choose (card (outs u)) 2 by Sym2.card_image_offDiag. Using Finset.sum_congr, we substitute this into the identity.

    lines 63–70

    uses finite_family_overlap_multiplicity_identity, Finset.sum_congr, Sym2.card_image_offDiag

      have hmain := finite_family_overlap_multiplicity_identity α (Sym2 α) Finset.univ N
      rw [hE] at hmain
      have hsum : (∑ u : α, (N u).card) =
          ∑ u : α, Nat.choose (outs u).card 2 := by
        apply Finset.sum_congr rfl
        intro u _
        exact Sym2.card_image_offDiag (outs u)
      rw [hsum] at hmain
  7. The total excess multiplicity of edges equals the sum of (card (outs v) choose 2) minus the number of edges. automation

    Using our characterization of predecessor sets, we replace |{p | e ∈ N(p)}| with |{p | ∀ x ∈ e, D.Adj p x}| in the sum over edges via Finset.sum_congr. The resulting identity has the form ∑_u (outs u choose 2) = |E| + ∑_{e ∈ E} (|pred(e)| - 1). Subtracting the edge count |E| from both sides yields the target identity, which is closed by linear integer arithmetic (omega).

    lines 71–81

    uses Finset.sum_congr

      have hfilters :
          (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,
            ((Finset.univ.filter fun p => e ∈ N p).card - 1)) =
          (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,
            ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1)) := by
        apply Finset.sum_congr rfl
        intro e he
        rw [hparent e he]
      rw [hfilters] at hmain
      change _ = (∑ v : α, Nat.choose (outs v).card 2) - _
      omega
digraph_common_predecessor_graph
The simple graph on the vertices of a digraph where two distinct vertices are adjacent if and only if they share a common predecessor.
finite_family_overlap_multiplicity_identity
For any finite family of subsets N(a) indexed by a ∈ S, the sum of their cardinalities equals the size of their union plus the sum of excess multiplicities of elements in the union.
Finset.mem_image.mp
An element belongs to the image of a finset under a function only if it is the value of the function on some element of that finset.
Finset.mem_image.mpr
If y = f(x) for some x ∈ s, then y belongs to the image of s under f.
Finset.mem_offDiag.mp
A pair (x, y) belongs to the off-diagonal of a finset s only if x ∈ s, y ∈ s, and x ≠ y.
Finset.mem_offDiag.mpr
If x ∈ s, y ∈ s, and x ≠ y, then (x, y) belongs to the off-diagonal of s.
Finset.mem_filter.mp
An element belongs to {x ∈ s | p x} only if it belongs to s and satisfies p.
Finset.mem_filter
An element a belongs to filter p s if and only if a ∈ s and p a holds.
Finset.mem_biUnion
An element belongs to the union ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.sum_congr
Two finset sums are equal if their index sets are equal and their summands agree on all elements of the index set.
SimpleGraph.mem_edgeFinset
An unordered pair 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.
Sym2.ind
To prove a property for all unordered pairs in Sym2 α, it suffices to prove it for pairs of the form s(x, y).
Sym2.eq_iff.mp
Two unordered pairs s(a, b) and s(c, d) are equal only if (a = c ∧ b = d) or (a = d ∧ b = c).
Sym2.mem_iff.mp
An element x belongs to the unordered pair s(a, b) only if x = a or x = b.
Sym2.mem_mk_left
The element x belongs to the unordered pair s(x, y).
Sym2.mem_mk_right
The element y belongs to the unordered pair s(x, y).
Sym2.card_image_offDiag
The number of unordered pairs of distinct elements in a finset s equals (card s choose 2).
true_and
The proposition True ∧ p is equivalent to p.

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 in504_overlap_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_overlap_incidence_identity    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] :    (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,      ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1)) =    (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card := by  classical  let outs : α → Finset α := fun u => Finset.univ.filter (fun w => D.Adj u w)  let N : α → Finset (Sym2 α) := fun u => (outs u).offDiag.image Sym2.mk.uncurry  have hN : ∀ u a b, s(a,b) ∈ N u ↔ a ≠ b ∧ D.Adj u a ∧ D.Adj u b := by    intro u a b    constructor    · intro h      obtain ⟨⟨x,y⟩, hxy, he⟩ := Finset.mem_image.mp h      obtain ⟨hx,hy,hne⟩ := Finset.mem_offDiag.mp hxy      have hx' : D.Adj u x := (Finset.mem_filter.mp hx).2      have hy' : D.Adj u y := (Finset.mem_filter.mp hy).2      rcases Sym2.eq_iff.mp he with ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩      · exact ⟨hne,hx',hy'⟩      · exact ⟨hne.symm,hy',hx'⟩    · rintro ⟨hne, ha, hb⟩      apply Finset.mem_image.mpr      refine ⟨(a,b), Finset.mem_offDiag.mpr ?_, rfl⟩      exact ⟨by simp [outs,ha], by simp [outs,hb], hne⟩  have hE : (Finset.univ : Finset α).biUnion N =      (digraph_common_predecessor_graph D).edgeFinset := by    ext e    induction e using Sym2.ind with    | h a b =>      rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]      change s(a,b) ∈ (Finset.univ : Finset α).biUnion N ↔        a ≠ b ∧ ∃ u, D.Adj u a ∧ D.Adj u b      simp only [Finset.mem_biUnion, Finset.mem_univ, true_and, hN]      constructor      · rintro ⟨u,hne,ha,hb⟩        exact ⟨hne,u,ha,hb⟩      · rintro ⟨hne,u,ha,hb⟩        exact ⟨u,hne,ha,hb⟩  have hparent : ∀ e ∈ (digraph_common_predecessor_graph D).edgeFinset,      (Finset.univ.filter fun p => e ∈ N p) =        (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x) := by    intro e he    induction e using Sym2.ind with    | h a b =>      have hne : a ≠ b := by        rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he        exact he.1      ext p      simp only [Finset.mem_filter, Finset.mem_univ, true_and, hN]      constructor      · rintro ⟨_,ha,hb⟩ x hx        rcases Sym2.mem_iff.mp hx with rfl | rfl        · exact ha        · exact hb      · intro h        exact ⟨hne, h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩  have hmain := finite_family_overlap_multiplicity_identity α (Sym2 α) Finset.univ N  rw [hE] at hmain  have hsum : (∑ u : α, (N u).card) =      ∑ u : α, Nat.choose (outs u).card 2 := by    apply Finset.sum_congr rfl    intro u _    exact Sym2.card_image_offDiag (outs u)  rw [hsum] at hmain  have hfilters :      (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,        ((Finset.univ.filter fun p => e ∈ N p).card - 1)) =      (∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset,        ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1)) := by    apply Finset.sum_congr rfl    intro e he    rw [hparent e he]  rw [hfilters] at hmain  change _ = (∑ v : α, Nat.choose (outs v).card 2) - _  omega
See it in the graphDiscuss this resultChallenge it