digraph_common_predecessor_graph_edge_count_le
If every vertex of a finite digraph has at most seven out-neighbors, then its common-predecessor graph has at most 21 times as many edges as there are vertices.
Statement
theorem digraph_common_predecessor_graph_edge_count_le (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) : (digraph_common_predecessor_graph D).edgeFinset.card ≤ 21 * Fintype.card α
- Source
- Counting auxiliary-graph edges by out-neighborhoods, as in arXiv:2610.11517, Proposition 4.3.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 2
- digraph_common_predecessor_graph_129_contradictionNo digraph on 129 vertices can have outdegree at most seven while its common-predecessor graph is connected and has no independent set of…
- digraph_127_four_cycles_under_extremal_and_cycle_criteriaA 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed…
The proof, explained
To bound the number of edges in the common-predecessor graph, every edge is associated with a common predecessor of its endpoints. Since each vertex has out-degree at most 7, it can serve as a common predecessor for at most (7 choose 2) = 21 pairs of vertices. Summing this bound over all vertices shows that the graph has at most 21 times as many edges as there are vertices.
The adjacency relation of the common-predecessor graph is decidable. automation
To allow Lean to form the finite set of edges (edgeFinset), we show that adjacency is decidable. Given vertices u and v, unfolding the definition of the common-predecessor graph expresses adjacency as a conjunction of u ≠ v and an existential quantifier over the finite vertex type α. Because equality and the digraph relation D.Adj are decidable, typeclass resolution infers decidability of this bounded condition.
intro u v unfold digraph_common_predecessor_graph infer_instance
For each vertex v, we define outs(v) as the set of its out-neighbors and edgesAt(v) as the set of unordered pairs of distinct out-neighbors.
We work classically and define two helper functions for any vertex v: outs(v) filters the vertices w such that D has an edge from v to w, and edgesAt(v) is the set of all unordered pairs formed from distinct elements of outs(v) (the image of its off-diagonal under pairing).
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
The edge set of the common-predecessor graph is a subset of the union over all vertices v of edgesAt(v).
Let e be an edge of the common-predecessor graph. By induction on unordered pairs (Sym2.ind), e can be written as {u, v}. By definition of the edge set (SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet), u ≠ v and there is some common predecessor w such that D has edges from w to u and from w to v. Thus both u and v belong to outs(w), so (u, v) is an off-diagonal pair in outs(w) (Finset.mem_offDiag.mpr). Its image under pairing is {u, v} ∈ edgesAt(w) (Finset.mem_image.mpr). Hence {u, v} belongs to the union of edgesAt(w) over all vertices w (Finset.mem_biUnion.mpr, Finset.mem_univ).
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.mem_biUnion.mpr,Finset.mem_univ,Finset.mem_image.mpr,Finset.mem_offDiag.mprhave 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]
For every vertex v, the set edgesAt(v) contains at most 21 pairs.
The number of unordered pairs of distinct elements in outs(v) is (card outs(v) choose 2) (Sym2.card_image_offDiag). Since outs(v) has size at most 7 by the out-degree assumption, monotonicity of binomial coefficients (Nat.choose_le_choose) gives |edgesAt(v)| ≤ (7 choose 2) = 21.
uses
Sym2.card_image_offDiag,Nat.choose_le_choosehave hsmall : ∀ v, (edgesAt v).card ≤ 21 := by intro v change ((outs v).offDiag.image Sym2.mk.uncurry).card ≤ 21 rw [Sym2.card_image_offDiag] have h := Nat.choose_le_choose 2 (hdeg v) exact h
The total number of edges in the common-predecessor graph is at most 21 times the number of vertices.
We bound the number of edges by a chain of four steps: first, the edge count is bounded by the cardinality of the union of all edgesAt(v) (Finset.card_le_card). Second, the size of the union is bounded by the sum of the individual cardinalities (Finset.card_biUnion_le). Third, replacing each cardinality |edgesAt(v)| with its upper bound 21 bounds the sum by the sum of 21 over all vertices (Finset.sum_le_sum). Finally, summing the constant 21 over all vertices of the finite type α evaluates to 21 * card α (Nat.mul_comm).
uses
Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_le_sum,Nat.mul_commcalc (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 ∈ (Finset.univ : Finset α), 21 := Finset.sum_le_sum (by intros; exact hsmall _) _ = 21 * Fintype.card α := by simp [Nat.mul_comm]
Sym2.ind- An induction principle for unordered pairs: to prove a property of an unordered pair, it suffices to prove it for pairs of the form s(x, y).
SimpleGraph.mem_edgeFinset- An edge belongs to the finite set of edges of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair {v, w} is an edge of a simple graph if and only if v and w are adjacent in the graph.
Finset.mem_biUnion.mpr- An element belongs to a union of finite sets if it belongs to at least one of the constituent sets.
Finset.mem_univ- Every element of a finite type is a member of the universal finset of all elements.
Finset.mem_image.mpr- An element belongs to the image of a finite set under a function if it is the image of some element in that set.
Finset.mem_offDiag.mpr- A pair belongs to the off-diagonal of a finite set if both coordinates belong to the set and are distinct.
Sym2.card_image_offDiag- The number of unordered pairs formed by distinct elements of a finite set s equals (card s choose 2).
Nat.choose_le_choose- The binomial coefficient (n choose k) is a non-decreasing function of n.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the other set's cardinality.
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_le_sum- If a function is pointwise bounded by another function on a finite set, the sum of the first is bounded by the sum of the second.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
- Lines 1–5 establish that the adjacency relation in the common-predecessor graph is decidable. This is a technical Lean requirement so that the finite edge set (edgeFinset) can be defined, having no counterpart in an informal paper proof.
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 {α : 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_graph_edge_count_le (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card ≤ 7) : (digraph_common_predecessor_graph D).edgeFinset.card ≤ 21 * Fintype.card α := 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] have hsmall : ∀ v, (edgesAt v).card ≤ 21 := by intro v change ((outs v).offDiag.image Sym2.mk.uncurry).card ≤ 21 rw [Sym2.card_image_offDiag] have h := Nat.choose_le_choose 2 (hdeg v) exact h 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 ∈ (Finset.univ : Finset α), 21 := Finset.sum_le_sum (by intros; exact hsmall _) _ = 21 * Fintype.card α := by simp [Nat.mul_comm]