digraph_twenty_profile_overlap_cardinality_bound
If five vertices of a finite part have internal outdegrees 1 through 5 and all other part vertices have internal outdegree seven, the total common-predecessor overlap plus choose(|B|,2) plus 85 is at least 21|B|.
Statement
theorem digraph_twenty_profile_overlap_cardinality_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (low : Fin 5 → α) (hinj : Function.Injective low) (hmem : ∀ i, low i ∈ B) (hlow : ∀ i : Fin 5, (B.filter fun w => D.Adj (low i) w).card = i.val + 1) (hhigh : ∀ v ∈ B, (∀ i, v ≠ low i) → (B.filter fun w => D.Adj v w).card = 7) : 21 * B.card ≤ ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + Nat.choose B.card 2 + 85
- Source
- Internal common-predecessor pair counting for the twenty-cut equality profile; experiment 26344 tabulates consequences by part size.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
- 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…
The proof, explained
The proof evaluates the sum of $\binom{d^+_B(v)}{2}$ over all vertices $v \in B$, which equals $20 + 21(|B| - 5) = 21|B| - 85$ by using the prescribed degree profile (degrees 1 through 5 on five vertices and 7 elsewhere), giving $21|B| \le \sum_{v \in B} \binom{d^+_B(v)}{2} + 85$. To upper-bound this sum, each vertex $v \in B$ is associated with the set $NB(v)$ of pairs of its out-neighbors in $B$, so that $|NB(v)| = \binom{d^+_B(v)}{2}$. By the double-counting identity for finite families, the sum of these sizes splits into the size of their union (at most $\binom{|B|}{2}$) plus the sum of their excess multiplicities. Because every such pair is an edge of the common-predecessor graph $G_{cp}$, this excess multiplicity sum is at most the total common-predecessor overlap $\sum_{v \in \alpha} \binom{d^+(v)}{2} - |E(G_{cp})|$, which completes the bound.
Define the internal out-neighborhoods $outsB(u)$, their pairs $NB(u)$, and the subset $L \subseteq B$ of the five low-degree vertices, establishing that $L \subseteq B$ with $|L| = 5$.
For each vertex $u$, $outsB(u)$ is defined as the set of out-neighbors of $u$ belonging to $B$, and $NB(u)$ is defined as the set of unordered pairs of distinct vertices in $outsB(u)$. The set $L$ is defined as the image of the map $\text{low} : \text{Fin } 5 \to \alpha$. Since each $\text{low}(i) \in B$, $L \subseteq B$. Because $\text{low}$ is injective, the cardinality of $L$ equals $|\text{Fin } 5| = 5$.
uses
Finset.mem_image.mp,Finset.card_image_of_injectivelet outsB : α → Finset α := fun u => B.filter (fun w => D.Adj u w) let NB : α → Finset (Sym2 α) := fun u => (outsB u).offDiag.image Sym2.mk.uncurry let L : Finset α := Finset.univ.image low have hL_sub : L ⊆ B := by intro x hx obtain ⟨i, -, rfl⟩ := Finset.mem_image.mp hx exact hmem i have hL_card : L.card = 5 := by rw [Finset.card_image_of_injective Finset.univ hinj] simp
The sum over $B$ of the binomial coefficients $\binom{|outsB(v)|}{2}$ satisfies $21|B| \le \sum_{v \in B} \binom{|outsB(v)|}{2} + 85$.
The sum $\sum_{v \in B} \binom{|outsB(v)|}{2}$ is split into the sum over $L$ and the sum over $B \setminus L$. On $L$, the outdegrees into $B$ are $1, 2, 3, 4, 5$, so the sum of $\binom{i+1}{2}$ computes directly to $0 + 1 + 3 + 6 + 10 = 20$. On $B \setminus L$, each vertex has internal outdegree 7, so $\binom{|outsB(v)|}{2} = \binom{7}{2} = 21$, yielding $21 |B \setminus L|$. Since $|B \setminus L| + 5 = |B|$, the total sum is $20 + 21(|B| - 5) = 21|B| - 85$. Rearranging gives $21|B| \le \sum_{v \in B} \binom{|outsB(v)|}{2} + 85$.
uses
Finset.sum_sdiff,add_comm,Finset.sum_image,Finset.mem_sdiff.mp,Finset.mem_image.mpr,Finset.mem_univ,Finset.sum_congr,mul_comm,Finset.card_sdiff_add_card_eq_cardhave hsplit : ∑ v ∈ B, Nat.choose (outsB v).card 2 = (∑ v ∈ L, Nat.choose (outsB v).card 2) + ∑ v ∈ B \ L, Nat.choose (outsB v).card 2 := by rw [← Finset.sum_sdiff hL_sub, add_comm] have hsumL : ∑ v ∈ L, Nat.choose (outsB v).card 2 = 20 := by rw [Finset.sum_image (fun x _ y _ h => hinj h)] have heq : ∀ i : Fin 5, Nat.choose (outsB (low i)).card 2 = Nat.choose (i.val + 1) 2 := by intro i dsimp [outsB] rw [hlow i] simp_rw [heq] decide have hsumRest : ∑ v ∈ B \ L, Nat.choose (outsB v).card 2 = 21 * (B \ L).card := by have heq : ∀ v ∈ B \ L, Nat.choose (outsB v).card 2 = 21 := by intro v hv obtain ⟨hvB, hvNL⟩ := Finset.mem_sdiff.mp hv have hnot : ∀ i, v ≠ low i := by intro i heq apply hvNL apply Finset.mem_image.mpr exact ⟨i, Finset.mem_univ i, heq.symm⟩ dsimp [outsB] rw [hhigh v hvB hnot] rfl rw [Finset.sum_congr rfl heq] simp [mul_comm] have hcards : (B \ L).card + 5 = B.card := by have := Finset.card_sdiff_add_card_eq_card hL_sub omega have hB_sum : 21 * B.card ≤ (∑ v ∈ B, Nat.choose (outsB v).card 2) + 85 := by rw [hsplit, hsumL, hsumRest] omega
For each vertex $u$, the set $NB(u)$ has size $\binom{|outsB(u)|}{2}$, so the sum of $|NB(u)|$ over $B$ equals $\sum_{u \in B} \binom{|outsB(u)|}{2}$.
By the identity identifying the cardinality of the unordered off-diagonal image of a finite set as $\binom{n}{2}$, the number of distinct unordered pairs in $outsB(u)$ is precisely $\binom{|outsB(u)|}{2}$. Summing this over all $u \in B$ yields $\sum_{u \in B} |NB(u)| = \sum_{u \in B} \binom{|outsB(u)|}{2}$.
uses
Sym2.card_image_offDiag,Finset.sum_congrhave hcard_NB : ∀ u, (NB u).card = Nat.choose (outsB u).card 2 := by intro u exact Sym2.card_image_offDiag (outsB u) have hsum_NB : (∑ a ∈ B, (NB a).card) = ∑ a ∈ B, Nat.choose (outsB a).card 2 := by apply Finset.sum_congr rfl intro u _ exact hcard_NB u
The union $\bigcup_{u \in B} NB(u)$ has cardinality at most $\binom{|B|}{2}$ and is contained in the edge set of the common-predecessor graph $G_{cp}$.
Every pair in $NB(u)$ consists of distinct vertices in $B$, so the union $\bigcup_{u \in B} NB(u)$ is a subset of all unordered pairs of distinct elements of $B$, which has cardinality $\binom{|B|}{2}$. Furthermore, because $u$ is a common predecessor of both vertices in any pair $e \in NB(u)$ and the two vertices are distinct, $e$ is an edge of the common-predecessor graph $G_{cp}$.
uses
Finset.mem_biUnion.mp,Finset.mem_image.mp,Finset.mem_offDiag.mp,Finset.mem_filter.mp,Finset.mem_image.mpr,Finset.mem_offDiag.mpr,Finset.card_le_card,Sym2.card_image_offDiag,SimpleGraph.mem_edgeFinsethave hsub_all : B.biUnion NB ⊆ B.offDiag.image Sym2.mk.uncurry := by intro e he obtain ⟨u, -, heu⟩ := Finset.mem_biUnion.mp he obtain ⟨⟨x, y⟩, hxy, rfl⟩ := Finset.mem_image.mp heu obtain ⟨hx, hy, hne⟩ := Finset.mem_offDiag.mp hxy have hxB : x ∈ B := (Finset.mem_filter.mp hx).1 have hyB : y ∈ B := (Finset.mem_filter.mp hy).1 apply Finset.mem_image.mpr refine ⟨(x, y), Finset.mem_offDiag.mpr ⟨hxB, hyB, hne⟩, rfl⟩ have hcard_biUnion : (B.biUnion NB).card ≤ Nat.choose B.card 2 := by have hle : (B.biUnion NB).card ≤ (B.offDiag.image Sym2.mk.uncurry).card := Finset.card_le_card hsub_all rw [Sym2.card_image_offDiag B] at hle exact hle have hsub_edges : B.biUnion NB ⊆ (digraph_common_predecessor_graph D).edgeFinset := by intro e he obtain ⟨u, -, heu⟩ := Finset.mem_biUnion.mp he obtain ⟨⟨x, y⟩, hxy, rfl⟩ := Finset.mem_image.mp heu obtain ⟨hx, hy, hne⟩ := Finset.mem_offDiag.mp hxy have hxAdj : D.Adj u x := (Finset.mem_filter.mp hx).2 have hyAdj : D.Adj u y := (Finset.mem_filter.mp hy).2 rw [SimpleGraph.mem_edgeFinset] exact ⟨hne, ⟨u, hxAdj, hyAdj⟩⟩
The sum of excess multiplicities over the union $\bigcup_{u \in B} NB(u)$ is at most the sum of excess common predecessors over the edge set of $G_{cp}$.
For each pair $e \in \bigcup_{u \in B} NB(u)$, any vertex $a \in B$ with $e \in NB(a)$ is a predecessor of both endpoints of $e$. Thus the set of such vertices in $B$ is a subset of all common predecessors of $e$ in $\alpha$, so its excess multiplicity in $B$ is at most the excess number of common predecessors in $\alpha$. Summing these inequalities over $\bigcup_{u \in B} NB(u)$ and extending to the superset $E(G_{cp})$ (where terms are non-negative) shows the sum over the union is bounded by the sum over all edges of $G_{cp}$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_image.mp,Finset.mem_offDiag.mp,Finset.mem_filter.mp,Sym2.mem_iff.mp,Finset.card_le_card,Finset.sum_le_sum,Finset.sum_le_sum_of_subset,le_transhave hle_multiplicity : ∀ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := by intro e he have hsube : (B.filter fun a => e ∈ NB a) ⊆ (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x) := by intro a ha simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha ⊢ obtain ⟨-, hae⟩ := ha obtain ⟨⟨x, y⟩, hxy, heq⟩ := Finset.mem_image.mp hae obtain ⟨hx, hy, -⟩ := Finset.mem_offDiag.mp hxy have hxAdj : D.Adj a x := (Finset.mem_filter.mp hx).2 have hyAdj : D.Adj a y := (Finset.mem_filter.mp hy).2 subst heq intro z hz rcases Sym2.mem_iff.mp hz with rfl | rfl · exact hxAdj · exact hyAdj have := Finset.card_le_card hsube omega have hsum_le_multiplicity : ∑ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := by have h1 : ∑ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ∑ e ∈ B.biUnion NB, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := Finset.sum_le_sum hle_multiplicity have h2 : ∑ e ∈ B.biUnion NB, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := Finset.sum_le_sum_of_subset hsub_edges exact le_trans h1 h2
The inequality $21|B| \le \left(\sum_{v \in \alpha} \binom{d^+(v)}{2} - |E(G_{cp})|\right) + \binom{|B|}{2} + 85$ holds.
The double-counting overlap identity equates $\sum_{a \in B} |NB(a)|$ with $|\bigcup_{a \in B} NB(a)|$ plus the sum of excess multiplicities over the union. The common-predecessor incidence identity equates the sum of excess common predecessors over $E(G_{cp})$ with $\sum_{v \in \alpha} \binom{d^+(v)}{2} - |E(G_{cp})|$. Combining the bound on the union size $\le \binom{|B|}{2}$, the bound on the sum of excess multiplicities, and the degree-sum lower bound $21|B| \le \sum_{v \in B} \binom{|outsB(v)|}{2} + 85$, linear integer arithmetic (`omega`) closes the goal.
uses
finite_family_overlap_multiplicity_identity,digraph_common_predecessor_overlap_incidence_identityhave hfamily := finite_family_overlap_multiplicity_identity α (Sym2 α) B NB rw [hsum_NB] at hfamily have hoverlap_id := digraph_common_predecessor_overlap_incidence_identity α D rw [← hoverlap_id] omega
add_comm- Addition in an additive magma is commutative ($a + b = b + a$).
digraph_common_predecessor_overlap_incidence_identity- In a directed graph, the sum over all edges in the common-predecessor graph of the excess common predecessors ($cp(e) - 1$) equals the sum over all vertices of $\binom{d^+(v)}{2}$ minus the number of edges in the common-predecessor graph.
finite_family_overlap_multiplicity_identity- The sum of cardinalities of a finite family of sets equals the cardinality of their union plus the sum over union elements of their excess multiplicity (the number of sets containing the element minus 1).
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the domain set.
Finset.card_le_card- A subset of a finite set has cardinality at most that of the superset.
Finset.card_sdiff_add_card_eq_card- For any subset $s \subseteq t$, the cardinality of the difference $t \setminus s$ plus the cardinality of $s$ equals the cardinality of $t$.
Finset.mem_filter- An element belongs to the filtered set $\{x \in s \mid p(x)\}$ if and only if it belongs to $s$ and satisfies $p$.
Finset.mem_filter.mp- If an element belongs to $\{x \in s \mid p(x)\}$, then it belongs to $s$ and satisfies $p$.
Finset.mem_biUnion.mp- If an element belongs to the indexed union $\bigcup_{a \in s} t(a)$, then it belongs to $t(a)$ for some $a \in s$.
Finset.mem_image.mp- If an element belongs to the image $f(s)$, then it equals $f(a)$ for some $a \in s$.
Finset.mem_image.mpr- If an element is the image of some element of $s$, then it belongs to the image $f(s)$.
Finset.mem_offDiag.mp- A pair belongs to the off-diagonal of $s$ if and only if both coordinates belong to $s$ and are distinct.
Finset.mem_offDiag.mpr- If $x \in s$, $y \in s$, and $x \ne y$, then the ordered pair $(x, y)$ belongs to the off-diagonal of $s$.
Finset.mem_sdiff.mp- If an element belongs to the difference $s_1 \setminus s_2$, then it belongs to $s_1$ and does not belong to $s_2$.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set.
Finset.sum_congr- Two sums over finite sets are equal if the sets of summation are equal and the summands agree pointwise on the set.
Finset.sum_image- Summing a function over the image of an injective map on a finite set equals summing the composed function over the domain set.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all elements $i$ in a finite set, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
Finset.sum_le_sum_of_subset- For non-negative terms, summing over a subset gives a result at most summing over the superset.
Finset.sum_sdiff- A sum over a set $s_2$ can be partitioned into the sum over the difference $s_2 \setminus s_1$ and the sum over a subset $s_1 \subseteq s_2$.
le_trans- The less-than-or-equal relation is transitive ($a \le b$ and $b \le c$ imply $a \le c$).
mul_comm- Multiplication in a commutative magma is commutative ($a \cdot b = b \cdot a$).
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set of a simple graph if and only if it belongs to its edge set.
Sym2.card_image_offDiag- The number of unordered pairs of distinct elements from a finite set $s$ is $\binom{|s|}{2}$.
Sym2.mem_iff.mp- An element belongs to the unordered pair $\{x, y\}$ if and only if it equals $x$ or equals $y$.
true_and- The conjunction $\text{True} \wedge p$ is logically equivalent to $p$.
- The final step uses the `omega` tactic to combine the established inequalities and identities via linear integer arithmetic.
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.
theorem digraph_twenty_profile_overlap_cardinality_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (B : Finset α) (low : Fin 5 → α) (hinj : Function.Injective low) (hmem : ∀ i, low i ∈ B) (hlow : ∀ i : Fin 5, (B.filter fun w => D.Adj (low i) w).card = i.val + 1) (hhigh : ∀ v ∈ B, (∀ i, v ≠ low i) → (B.filter fun w => D.Adj v w).card = 7) : 21 * B.card ≤ ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + Nat.choose B.card 2 + 85 := by let outsB : α → Finset α := fun u => B.filter (fun w => D.Adj u w) let NB : α → Finset (Sym2 α) := fun u => (outsB u).offDiag.image Sym2.mk.uncurry let L : Finset α := Finset.univ.image low have hL_sub : L ⊆ B := by intro x hx obtain ⟨i, -, rfl⟩ := Finset.mem_image.mp hx exact hmem i have hL_card : L.card = 5 := by rw [Finset.card_image_of_injective Finset.univ hinj] simp have hsplit : ∑ v ∈ B, Nat.choose (outsB v).card 2 = (∑ v ∈ L, Nat.choose (outsB v).card 2) + ∑ v ∈ B \ L, Nat.choose (outsB v).card 2 := by rw [← Finset.sum_sdiff hL_sub, add_comm] have hsumL : ∑ v ∈ L, Nat.choose (outsB v).card 2 = 20 := by rw [Finset.sum_image (fun x _ y _ h => hinj h)] have heq : ∀ i : Fin 5, Nat.choose (outsB (low i)).card 2 = Nat.choose (i.val + 1) 2 := by intro i dsimp [outsB] rw [hlow i] simp_rw [heq] decide have hsumRest : ∑ v ∈ B \ L, Nat.choose (outsB v).card 2 = 21 * (B \ L).card := by have heq : ∀ v ∈ B \ L, Nat.choose (outsB v).card 2 = 21 := by intro v hv obtain ⟨hvB, hvNL⟩ := Finset.mem_sdiff.mp hv have hnot : ∀ i, v ≠ low i := by intro i heq apply hvNL apply Finset.mem_image.mpr exact ⟨i, Finset.mem_univ i, heq.symm⟩ dsimp [outsB] rw [hhigh v hvB hnot] rfl rw [Finset.sum_congr rfl heq] simp [mul_comm] have hcards : (B \ L).card + 5 = B.card := by have := Finset.card_sdiff_add_card_eq_card hL_sub omega have hB_sum : 21 * B.card ≤ (∑ v ∈ B, Nat.choose (outsB v).card 2) + 85 := by rw [hsplit, hsumL, hsumRest] omega have hcard_NB : ∀ u, (NB u).card = Nat.choose (outsB u).card 2 := by intro u exact Sym2.card_image_offDiag (outsB u) have hsum_NB : (∑ a ∈ B, (NB a).card) = ∑ a ∈ B, Nat.choose (outsB a).card 2 := by apply Finset.sum_congr rfl intro u _ exact hcard_NB u have hsub_all : B.biUnion NB ⊆ B.offDiag.image Sym2.mk.uncurry := by intro e he obtain ⟨u, -, heu⟩ := Finset.mem_biUnion.mp he obtain ⟨⟨x, y⟩, hxy, rfl⟩ := Finset.mem_image.mp heu obtain ⟨hx, hy, hne⟩ := Finset.mem_offDiag.mp hxy have hxB : x ∈ B := (Finset.mem_filter.mp hx).1 have hyB : y ∈ B := (Finset.mem_filter.mp hy).1 apply Finset.mem_image.mpr refine ⟨(x, y), Finset.mem_offDiag.mpr ⟨hxB, hyB, hne⟩, rfl⟩ have hcard_biUnion : (B.biUnion NB).card ≤ Nat.choose B.card 2 := by have hle : (B.biUnion NB).card ≤ (B.offDiag.image Sym2.mk.uncurry).card := Finset.card_le_card hsub_all rw [Sym2.card_image_offDiag B] at hle exact hle have hsub_edges : B.biUnion NB ⊆ (digraph_common_predecessor_graph D).edgeFinset := by intro e he obtain ⟨u, -, heu⟩ := Finset.mem_biUnion.mp he obtain ⟨⟨x, y⟩, hxy, rfl⟩ := Finset.mem_image.mp heu obtain ⟨hx, hy, hne⟩ := Finset.mem_offDiag.mp hxy have hxAdj : D.Adj u x := (Finset.mem_filter.mp hx).2 have hyAdj : D.Adj u y := (Finset.mem_filter.mp hy).2 rw [SimpleGraph.mem_edgeFinset] exact ⟨hne, ⟨u, hxAdj, hyAdj⟩⟩ have hle_multiplicity : ∀ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := by intro e he have hsube : (B.filter fun a => e ∈ NB a) ⊆ (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x) := by intro a ha simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha ⊢ obtain ⟨-, hae⟩ := ha obtain ⟨⟨x, y⟩, hxy, heq⟩ := Finset.mem_image.mp hae obtain ⟨hx, hy, -⟩ := Finset.mem_offDiag.mp hxy have hxAdj : D.Adj a x := (Finset.mem_filter.mp hx).2 have hyAdj : D.Adj a y := (Finset.mem_filter.mp hy).2 subst heq intro z hz rcases Sym2.mem_iff.mp hz with rfl | rfl · exact hxAdj · exact hyAdj have := Finset.card_le_card hsube omega have hsum_le_multiplicity : ∑ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := by have h1 : ∑ e ∈ B.biUnion NB, ((B.filter fun a => e ∈ NB a).card - 1) ≤ ∑ e ∈ B.biUnion NB, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := Finset.sum_le_sum hle_multiplicity have h2 : ∑ e ∈ B.biUnion NB, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) ≤ ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset, ((Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card - 1) := Finset.sum_le_sum_of_subset hsub_edges exact le_trans h1 h2 have hfamily := finite_family_overlap_multiplicity_identity α (Sym2 α) B NB rw [hsum_NB] at hfamily have hoverlap_id := digraph_common_predecessor_overlap_incidence_identity α D rw [← hoverlap_id] omega