digraph_common_predecessor_vertex_incidence_bound
For an r-outregular finite digraph, the number of common-predecessor edge incidences repeated at a given vertex is at most the total number of repeated edge incidences.
Statement
theorem digraph_common_predecessor_vertex_incidence_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) (v : α) : (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card + (digraph_common_predecessor_graph D).edgeFinset.card ≤ (digraph_common_predecessor_graph D).degree v + Fintype.card α * Nat.choose r 2
- Source
- Exceptional-vertex incidence bound in the general minimum-counterexample campaign route to OP-110.
- Verified
- 03 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.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
The proof, explained
For an r-out-regular finite digraph D, each vertex w contributes Nat.choose r 2 pairs of distinct out-neighbors that share w as a common predecessor. The edge set of the common-predecessor graph G is partitioned into edges incident to v (whose count is degree_G(v)) and edges non-incident to v, with the non-incident edges covered by the non-incident pairs across all vertices. Furthermore, the incident pairs contributed by vertex w number r - 1 precisely when w is an in-neighbor of v and 0 otherwise, summing over all vertices to (r - 1) * indeg(v). Combining these bounds with the total count of pairs |α| * Nat.choose r 2 via linear arithmetic proves the required inequality.
Adjacency in the common-predecessor graph of D is decidable.
Unfolding the definition of the common-predecessor graph shows that two vertices u and v are adjacent if and only if u ≠ v and there exists a vertex w with w → u and w → v. Since the vertex type is finite and equality and digraph adjacency are decidable, typeclass synthesis automatically infers decidability of this existential quantification over a finite domain.
private instance in478_predecessor_incidence_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_instance
The edges of G split into those incident to v (numbering degree_G(v)) and those not incident to v.
Let G be the common-predecessor graph of D, and define edgesAt(w) as the unordered pairs of distinct out-neighbors of w. The edge set of G splits into edges containing v and edges not containing v by Finset.card_filter_add_card_filter_not. The edges containing v form the incidence set of v (SimpleGraph.incidenceFinset_eq_filter), whose size is precisely degree_G(v) (SimpleGraph.card_incidenceFinset_eq_degree).
uses
Finset.card_filter_add_card_filter_not,SimpleGraph.incidenceFinset_eq_filter,SimpleGraph.card_incidenceFinset_eq_degreelet G := digraph_common_predecessor_graph D let edgesAt : α → Finset (Sym2 α) := fun w => ((Finset.univ.filter (fun u => D.Adj w u)).offDiag).image (Function.uncurry Sym2.mk) have h_edge_split := Finset.card_filter_add_card_filter_not (s := G.edgeFinset) (v ∈ ·) have h_deg : (G.edgeFinset.filter (v ∈ ·)).card = G.degree v := by rw [← SimpleGraph.incidenceFinset_eq_filter, SimpleGraph.card_incidenceFinset_eq_degree]
The number of edges of G not incident to v is at most the sum over all vertices w of the number of pairs in edgesAt(w) not containing v.
Any edge e of G not incident to v is of the form s(x, y) with x ≠ y sharing some predecessor w (Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet). Thus e belongs to edgesAt(w), and because v ∉ e, it belongs to the non-incident filter of edgesAt(w). This establishes that the non-incident edges of G are a subset of the union of the non-incident subsets of edgesAt(w) over all w (Finset.mem_biUnion.mpr). By subset monotonicity (Finset.card_le_card) and the union bound (Finset.card_biUnion_le), the cardinality is bounded by the sum of their individual sizes.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.mem_biUnion.mpr,Finset.card_le_card,Finset.card_biUnion_lehave h_edge_le : (G.edgeFinset.filter (v ∉ ·)).card ≤ ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card := by have hsub : G.edgeFinset.filter (v ∉ ·) ⊆ (Finset.univ : Finset α).biUnion (fun w => (edgesAt w).filter (v ∉ ·)) := by intro e he rw [Finset.mem_filter] at he have he_edge := he.1 have hve := he.2 induction e using Sym2.ind with | h x y => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he_edge dsimp [digraph_common_predecessor_graph, G] at he_edge rcases he_edge with ⟨hne, w, hwx, hwy⟩ apply Finset.mem_biUnion.mpr refine ⟨w, Finset.mem_univ _, ?_⟩ rw [Finset.mem_filter] refine ⟨?_, hve⟩ simp only [edgesAt, Finset.mem_image, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨x, y, ⟨hwx, hwy, hne⟩, rfl⟩ calc (G.edgeFinset.filter (v ∉ ·)).card ≤ ((Finset.univ : Finset α).biUnion (fun w => (edgesAt w).filter (v ∉ ·))).card := Finset.card_le_card hsub _ ≤ ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card := Finset.card_biUnion_le
For each vertex w, the number of pairs in edgesAt(w) containing v is r - 1 if w → v, and 0 otherwise.
We split into cases depending on whether w → v. If w → v, any pair in edgesAt(w) containing v has the form s(v, u) for an out-neighbor u of w distinct from v. Mapping u to s(v, u) gives an injection (Finset.card_image_of_injOn, Sym2.eq_iff, Sym2.eq_swap) from the out-neighbors of w with v removed. Since the out-degree is r, removing v leaves r - 1 vertices (Finset.card_erase_add_one), giving r - 1 pairs. If w does not have an edge to v, neither endpoint of any pair in edgesAt(w) can be v (Sym2.mem_iff), so the filtered set is empty (Finset.filter_eq_empty_iff) and its cardinality is 0 (Finset.card_eq_zero.mpr).
uses
Sym2.mem_iff,Sym2.eq_swap,Finset.card_image_of_injOn,Finset.card_erase_add_one,Sym2.eq_iff,Finset.card_eq_zero.mpr,Finset.filter_eq_empty_iffhave h_filter_v : ∀ w, ((edgesAt w).filter (v ∈ ·)).card = if D.Adj w v then r - 1 else 0 := by intro w split_ifs with hwv · have h_img : (edgesAt w).filter (v ∈ ·) = (((Finset.univ.filter (fun u => D.Adj w u)).erase v).image (fun u => s(v, u))) := by ext e simp only [edgesAt, Finset.mem_filter, Finset.mem_image, Finset.mem_erase, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists] constructor · rintro ⟨⟨x, y, ⟨hx, hy, hne⟩, rfl⟩, hve⟩ simp only [Sym2.mem_iff] at hve rcases hve with rfl | rfl · exact ⟨y, ⟨hne.symm, hy⟩, rfl⟩ · exact ⟨x, ⟨hne, hx⟩, Sym2.eq_swap⟩ · rintro ⟨u, ⟨hne, hu⟩, rfl⟩ refine ⟨⟨v, u, ⟨?_, hu, hne.symm⟩, rfl⟩, by simp⟩ simp [hwv] rw [h_img] rw [Finset.card_image_of_injOn] · have he : ((Finset.univ.filter (fun u => D.Adj w u)).erase v).card + 1 = (Finset.univ.filter (fun u => D.Adj w u)).card := Finset.card_erase_add_one (by simp [hwv]) have hd : (Finset.univ.filter (fun u => D.Adj w u)).card = r := hreg w omega · intro x hx y _ hxy have hxne : x ≠ v := (Finset.mem_erase.mp hx).1 simp only [Sym2.eq_iff] at hxy rcases hxy with ⟨_, rfl⟩ | ⟨_, rfl⟩ · rfl · exact (hxne rfl).elim · apply Finset.card_eq_zero.mpr rw [Finset.filter_eq_empty_iff] intro e he hve simp only [edgesAt, Finset.mem_image, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists] at he rcases he with ⟨x, y, ⟨hx, hy, _⟩, rfl⟩ simp only [Sym2.mem_iff] at hve simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy rcases hve with rfl | rfl · exact hwv hx · exact hwv hy
The sum over all w of the number of pairs in edgesAt(w) containing v equals (r - 1) times the in-degree of v.
By the previous step, each term in the sum is r - 1 if w → v and 0 otherwise (Finset.sum_congr). Splitting the sum (Finset.sum_ite) isolates the vertices with w → v, which are the in-neighbors of v, yielding (r - 1) * indeg(v) after commuting multiplication (Nat.mul_comm).
uses
Finset.sum_congr,Finset.sum_ite,Nat.mul_commhave h_sum_filter_v : ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card = (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card := by calc ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card = ∑ w : α, (if D.Adj w v then r - 1 else 0) := by apply Finset.sum_congr rfl intro w _ exact h_filter_v w _ = (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card := by rw [Finset.sum_ite] simp [Nat.mul_comm]
For every vertex w, the set edgesAt(w) has cardinality Nat.choose r 2.
The set edgesAt(w) is formed by taking the quotient to unordered pairs of the off-diagonal pairs of the out-neighborhood of w. By Sym2.card_image_offDiag, its size is Nat.choose k 2 where k is the out-degree of w, which equals r by out-regularity.
uses
Sym2.card_image_offDiaghave h_edgesAt_card : ∀ w, (edgesAt w).card = Nat.choose r 2 := by intro w change (((Finset.univ.filter (fun u => D.Adj w u)).offDiag).image (Function.uncurry Sym2.mk)).card = Nat.choose r 2 rw [Sym2.card_image_offDiag] rw [hreg w]
The sum of pairs in edgesAt(w) containing v and pairs not containing v over all vertices w equals |α| * Nat.choose r 2.
Recombining the two sums with Finset.sum_add_distrib and applying Finset.card_filter_add_card_filter_not shows that for each w, the two parts sum to the total cardinality of edgesAt(w). Since each edgesAt(w) has size Nat.choose r 2, summing this constant over all |α| vertices yields |α| * Nat.choose r 2.
uses
Finset.sum_add_distrib,Finset.sum_congr,Finset.card_filter_add_card_filter_nothave h_sum_both : ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card + ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card = Fintype.card α * Nat.choose r 2 := by rw [← Finset.sum_add_distrib] calc ∑ w : α, (((edgesAt w).filter (v ∈ ·)).card + ((edgesAt w).filter (v ∉ ·)).card) = ∑ w : α, (edgesAt w).card := by apply Finset.sum_congr rfl intro w _ exact Finset.card_filter_add_card_filter_not (v ∈ ·) _ = ∑ _w : α, Nat.choose r 2 := by apply Finset.sum_congr rfl intro w _ exact h_edgesAt_card w _ = Fintype.card α * Nat.choose r 2 := by simp
(r - 1) * indeg(v) + |E(G)| ≤ degree_G(v) + |α| * Nat.choose r 2.
We combine the edge partition |E(G)| = degree_G(v) + |E_non_v|, the bound |E_non_v| ≤ ∑_w |edgesAt(w)_non_v|, the incidence sum ∑_w |edgesAt(w)_v| = (r - 1) * indeg(v), and the total sum identity ∑_w |edgesAt(w)_v| + ∑_w |edgesAt(w)_non_v| = |α| * Nat.choose r 2. Adding the incidence sum to the edge partition and substituting the bound and total sum identity yields the desired inequality via linear arithmetic (linarith).
linarith
Finset.card_filter_add_card_filter_not- The number of elements of a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
SimpleGraph.incidenceFinset_eq_filter- The incidence finset of a vertex in a simple graph equals the filter of edges containing that vertex.
SimpleGraph.card_incidenceFinset_eq_degree- The cardinality of the incidence finset of a vertex equals its degree.
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 unordered pair belongs to the edge finset of a 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 graph if and only if v and w are adjacent.
Finset.mem_biUnion.mpr- An element belongs to a indexed union of finite sets if it belongs to one of the component sets.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the other's cardinality.
Finset.card_biUnion_le- The cardinality of a finite union of finite sets is at most the sum of their individual cardinalities.
Sym2.mem_iff- A vertex belongs to the unordered pair s(b, c) if and only if it equals b or c.
Sym2.eq_swap- An unordered pair is symmetric under swapping its two endpoints: s(a, b) = s(b, a).
Finset.card_image_of_injOn- The image of a finite set under a map injective on that set has the same cardinality as the original set.
Finset.card_erase_add_one- Removing an element from a finite set containing it decreases its cardinality by one.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if x = z and y = w, or x = w and y = z.
Finset.card_eq_zero.mpr- An empty finset has cardinality zero.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate yields the empty set if and only if no element satisfies the predicate.
Finset.sum_congr- Two sums over equal finite sets are equal if their terms agree on all elements.
Finset.sum_ite- The sum of an if-then-else function over a finite set splits into the sum over elements satisfying the condition plus the sum over elements that do not.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Sym2.card_image_offDiag- The number of unordered pairs of distinct elements from a finite set s is Nat.choose (s.card) 2.
Finset.sum_add_distrib- The sum of a pointwise sum of functions over a finite set equals the sum of the individual sums.
- Lines 1–4 define a private typeclass instance showing that adjacency in the common-predecessor graph is decidable, a formal prerequisite for forming edge finsets and vertex degrees in Mathlib.
- The final step is completed by `linarith`, which automates linear arithmetic over ℕ to combine the four established bounds and identities.
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 in478_predecessor_incidence_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_vertex_incidence_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) (v : α) : (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card + (digraph_common_predecessor_graph D).edgeFinset.card ≤ (digraph_common_predecessor_graph D).degree v + Fintype.card α * Nat.choose r 2 := by let G := digraph_common_predecessor_graph D let edgesAt : α → Finset (Sym2 α) := fun w => ((Finset.univ.filter (fun u => D.Adj w u)).offDiag).image (Function.uncurry Sym2.mk) have h_edge_split := Finset.card_filter_add_card_filter_not (s := G.edgeFinset) (v ∈ ·) have h_deg : (G.edgeFinset.filter (v ∈ ·)).card = G.degree v := by rw [← SimpleGraph.incidenceFinset_eq_filter, SimpleGraph.card_incidenceFinset_eq_degree] have h_edge_le : (G.edgeFinset.filter (v ∉ ·)).card ≤ ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card := by have hsub : G.edgeFinset.filter (v ∉ ·) ⊆ (Finset.univ : Finset α).biUnion (fun w => (edgesAt w).filter (v ∉ ·)) := by intro e he rw [Finset.mem_filter] at he have he_edge := he.1 have hve := he.2 induction e using Sym2.ind with | h x y => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he_edge dsimp [digraph_common_predecessor_graph, G] at he_edge rcases he_edge with ⟨hne, w, hwx, hwy⟩ apply Finset.mem_biUnion.mpr refine ⟨w, Finset.mem_univ _, ?_⟩ rw [Finset.mem_filter] refine ⟨?_, hve⟩ simp only [edgesAt, Finset.mem_image, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨x, y, ⟨hwx, hwy, hne⟩, rfl⟩ calc (G.edgeFinset.filter (v ∉ ·)).card ≤ ((Finset.univ : Finset α).biUnion (fun w => (edgesAt w).filter (v ∉ ·))).card := Finset.card_le_card hsub _ ≤ ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card := Finset.card_biUnion_le have h_filter_v : ∀ w, ((edgesAt w).filter (v ∈ ·)).card = if D.Adj w v then r - 1 else 0 := by intro w split_ifs with hwv · have h_img : (edgesAt w).filter (v ∈ ·) = (((Finset.univ.filter (fun u => D.Adj w u)).erase v).image (fun u => s(v, u))) := by ext e simp only [edgesAt, Finset.mem_filter, Finset.mem_image, Finset.mem_erase, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists] constructor · rintro ⟨⟨x, y, ⟨hx, hy, hne⟩, rfl⟩, hve⟩ simp only [Sym2.mem_iff] at hve rcases hve with rfl | rfl · exact ⟨y, ⟨hne.symm, hy⟩, rfl⟩ · exact ⟨x, ⟨hne, hx⟩, Sym2.eq_swap⟩ · rintro ⟨u, ⟨hne, hu⟩, rfl⟩ refine ⟨⟨v, u, ⟨?_, hu, hne.symm⟩, rfl⟩, by simp⟩ simp [hwv] rw [h_img] rw [Finset.card_image_of_injOn] · have he : ((Finset.univ.filter (fun u => D.Adj w u)).erase v).card + 1 = (Finset.univ.filter (fun u => D.Adj w u)).card := Finset.card_erase_add_one (by simp [hwv]) have hd : (Finset.univ.filter (fun u => D.Adj w u)).card = r := hreg w omega · intro x hx y _ hxy have hxne : x ≠ v := (Finset.mem_erase.mp hx).1 simp only [Sym2.eq_iff] at hxy rcases hxy with ⟨_, rfl⟩ | ⟨_, rfl⟩ · rfl · exact (hxne rfl).elim · apply Finset.card_eq_zero.mpr rw [Finset.filter_eq_empty_iff] intro e he hve simp only [edgesAt, Finset.mem_image, Finset.mem_offDiag, Function.uncurry_apply_pair, Prod.exists] at he rcases he with ⟨x, y, ⟨hx, hy, _⟩, rfl⟩ simp only [Sym2.mem_iff] at hve simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy rcases hve with rfl | rfl · exact hwv hx · exact hwv hy have h_sum_filter_v : ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card = (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card := by calc ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card = ∑ w : α, (if D.Adj w v then r - 1 else 0) := by apply Finset.sum_congr rfl intro w _ exact h_filter_v w _ = (r - 1) * (Finset.univ.filter fun u => D.Adj u v).card := by rw [Finset.sum_ite] simp [Nat.mul_comm] have h_edgesAt_card : ∀ w, (edgesAt w).card = Nat.choose r 2 := by intro w change (((Finset.univ.filter (fun u => D.Adj w u)).offDiag).image (Function.uncurry Sym2.mk)).card = Nat.choose r 2 rw [Sym2.card_image_offDiag] rw [hreg w] have h_sum_both : ∑ w : α, ((edgesAt w).filter (v ∈ ·)).card + ∑ w : α, ((edgesAt w).filter (v ∉ ·)).card = Fintype.card α * Nat.choose r 2 := by rw [← Finset.sum_add_distrib] calc ∑ w : α, (((edgesAt w).filter (v ∈ ·)).card + ((edgesAt w).filter (v ∉ ·)).card) = ∑ w : α, (edgesAt w).card := by apply Finset.sum_congr rfl intro w _ exact Finset.card_filter_add_card_filter_not (v ∈ ·) _ = ∑ _w : α, Nat.choose r 2 := by apply Finset.sum_congr rfl intro w _ exact h_edgesAt_card w _ = Fintype.card α * Nat.choose r 2 := by simp linarith