digraph_common_predecessor_overlap_incidence_identity
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
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- finite_family_overlap_multiplicity_identityFor a finite family of finite sets, total incidences equal the covered-set size plus the sum of multiplicity minus one over covered…
- Used by 7
- digraph_twenty_profile_overlap_cardinality_boundIf five vertices of a finite part have internal outdegrees 1 through 5 and all other part vertices have internal outdegree seven, the…
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- digraph_nested_parents_overlap_generalFor k transitive low vertices pointing to q, nested common-predecessor counts k+3−t force common-predecessor overlap at least twice…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
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.
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.
uses
digraph_common_predecessor_graphintro u v unfold digraph_common_predecessor_graph infer_instance
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.
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
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.
uses
Finset.mem_image.mp,Finset.mem_offDiag.mp,Finset.mem_filter.mp,Sym2.eq_iff.mp,Finset.mem_image.mpr,Finset.mem_offDiag.mprhave 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⟩
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.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.mem_biUnion,Finset.mem_univ,true_andhave 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⟩
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).
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_righthave 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 _ _)⟩
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.
uses
finite_family_overlap_multiplicity_identity,Finset.sum_congr,Sym2.card_image_offDiaghave 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
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).
uses
Finset.sum_congrhave 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.
- The private instance `in504_overlap_count_decAdj` at lines 1–5 is required for Lean to synthesize a `Fintype` instance for the edge set of the common-predecessor graph, making `(digraph_common_predecessor_graph D).edgeFinset` well-defined.
- Unordered pairs of vertices are represented by the symmetric square quotient type `Sym2 α`, where `s(a, b)` denotes the unordered pair containing `a` and `b`.
- The final step uses the `omega` decision procedure to perform subtraction in ℕ across the identity.
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 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