digraph_common_predecessor_seven_bounded_indegree_degree_bound
If all outdegrees equal seven and all indegrees are at most seven, every vertex of the common-predecessor graph has degree at most 42.
Statement
theorem digraph_common_predecessor_seven_bounded_indegree_degree_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7) : ∀ v, (digraph_common_predecessor_graph D).degree v ≤ 42
- Source
- Auxiliary-graph transfer and counting steps for the OP-110 campaign.
- 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 1
- digraph_common_predecessor_balanced_seven_card_le_121A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has…
The proof, explained
To bound the degree of an arbitrary vertex v in the common-predecessor graph, the proof covers the neighborhood of v by the out-neighbors of all predecessors of v. Any neighbor u of v shares an in-neighbor w with v, meaning w is a predecessor of v and u is a successor of w other than v. Since each vertex has outdegree 7, each predecessor has exactly 7 - 1 = 6 successors other than v. Because v has at most 7 predecessors by the indegree bound, the union of these successor sets has size at most 7 * 6 = 42, which bounds the degree of v.
Adjacency in the common-predecessor graph is decidable.
Unfolding the definition of the common-predecessor graph shows that adjacency is an existential quantification over the finite vertex type α of a decidable relation; Lean's typeclass inference synthesizes the decidability instance automatically.
private instance in478_digraph_common_predecessor_seven_bounded_indegree_degree_bound_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
Fix an arbitrary vertex v and define the set of its in-neighbors and, for each predecessor w, the set of its out-neighbors excluding v.
We enable classical reasoning and consider a fixed vertex v. We let ins be the set of predecessors {w | D.Adj w v} of v, and for each predecessor w, let outs w be the set of out-neighbors {z | D.Adj w z} ∖ {v} of w with v removed.
classical intro v let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let outs : α → Finset α := fun w => (Finset.univ.filter fun z => D.Adj w z).erase v
Every neighbor of v in the common-predecessor graph belongs to the union ⋃ (w ∈ ins), outs w.
Let u be a neighbor of v in the common-predecessor graph (SimpleGraph.mem_neighborFinset). By definition of the common-predecessor graph, u ≠ v and there exists a vertex w such that D.Adj w v and D.Adj w u. This means w ∈ ins and u ∈ outs w, so u belongs to the union of outs w over all w ∈ ins (Finset.mem_biUnion.mpr).
uses
SimpleGraph.mem_neighborFinset,Finset.mem_biUnion.mprhave hcover : (digraph_common_predecessor_graph D).neighborFinset v ⊆ ins.biUnion outs := by intro u hu have hu' := (SimpleGraph.mem_neighborFinset _ _ _).mp hu obtain ⟨hne, w, hwv, hwu⟩ := hu' apply Finset.mem_biUnion.mpr refine ⟨w, ?_, ?_⟩ · simp [ins, hwv] · simp [outs, hne.symm, hwu]
For every predecessor w ∈ ins, the set outs w has cardinality 6.
For w ∈ ins, w has an outgoing edge to v (Finset.mem_filter.mp). Since v is an out-neighbor of w, removing v decreases the cardinality of w's out-neighborhood by one (Finset.card_erase_add_one). The total outdegree of w is 7 by the outdegree regularity assumption hreg, so linear arithmetic (omega) determines that |outs w| = 7 - 1 = 6.
uses
Finset.mem_filter.mp,Finset.card_erase_add_onehave hsize : ∀ w ∈ ins, (outs w).card = 6 := by intro w hw have hwv : D.Adj w v := (Finset.mem_filter.mp hw).2 have he := Finset.card_erase_add_one (s := Finset.univ.filter fun z => D.Adj w z) (a := v) (by simp [hwv]) have hd := hreg w change (outs w).card + 1 = _ at he omega
The degree of v in the common-predecessor graph is at most 42.
The degree of v equals the cardinality of its neighbor finset (SimpleGraph.card_neighborFinset_eq_degree). By inclusion in the union ⋃ (w ∈ ins), outs w, this cardinality is at most the size of the union (Finset.card_le_card), which is bounded by the sum of cardinalities ∑ (w ∈ ins), |outs w| (Finset.card_biUnion_le). Since each summand is 6 (Finset.sum_congr), the sum evaluates to 6 * |ins| (Nat.mul_comm). Finally, since the indegree |ins| of v is at most 7 by assumption hinde, linear arithmetic (omega) yields 6 * |ins| ≤ 42.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_congr,Nat.mul_commrw [← SimpleGraph.card_neighborFinset_eq_degree] calc _ ≤ (ins.biUnion outs).card := Finset.card_le_card hcover _ ≤ ∑ w ∈ ins, (outs w).card := Finset.card_biUnion_le _ = ∑ _w ∈ ins, (6 : ℕ) := by apply Finset.sum_congr rfl intro w hw exact hsize w hw _ = 6 * ins.card := by simp [Nat.mul_comm] _ ≤ 42 := by have h := hinde v; change ins.card ≤ 7 at h; omega
SimpleGraph.mem_neighborFinset- An element belongs to the neighbor finset of a vertex v in a simple graph if and only if it is adjacent to v.
Finset.mem_biUnion.mpr- If an element belongs to the image set t(a) for some a in s, then it belongs to the union of sets ⋃ (a ∈ s), t(a).
Finset.mem_filter.mp- If an element belongs to a filtered finset {x ∈ s | p x}, then it belongs to s and satisfies the predicate p.
Finset.card_erase_add_one- If an element a belongs to a finset s, then the size of s with a erased plus one equals the size of s.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex v in a simple graph equals the degree of v.
Finset.card_le_card- If a finset s is a subset of a finset t, then the cardinality of s is at most the cardinality of t.
Finset.card_biUnion_le- The cardinality of a union ⋃ (a ∈ s), t(a) is at most the sum of the cardinalities ∑ (a ∈ s), |t(a)|.
Finset.sum_congr- Two sums over finsets are equal if their index sets are equal and their summands agree on every element of the index set.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
- The helper instance in478_digraph_common_predecessor_seven_bounded_indegree_degree_bound_decAdj sets up decidability of adjacency in the common-predecessor graph via typeclass inference, which Lean requires to define degrees and neighborhoods in simple graphs.
- Classical logic is invoked via classical to make all predicates decidable during the combinatorial reasoning.
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_digraph_common_predecessor_seven_bounded_indegree_degree_bound_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_seven_bounded_indegree_degree_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7) : ∀ v, (digraph_common_predecessor_graph D).degree v ≤ 42 := by classical intro v let ins : Finset α := Finset.univ.filter fun w => D.Adj w v let outs : α → Finset α := fun w => (Finset.univ.filter fun z => D.Adj w z).erase v have hcover : (digraph_common_predecessor_graph D).neighborFinset v ⊆ ins.biUnion outs := by intro u hu have hu' := (SimpleGraph.mem_neighborFinset _ _ _).mp hu obtain ⟨hne, w, hwv, hwu⟩ := hu' apply Finset.mem_biUnion.mpr refine ⟨w, ?_, ?_⟩ · simp [ins, hwv] · simp [outs, hne.symm, hwu] have hsize : ∀ w ∈ ins, (outs w).card = 6 := by intro w hw have hwv : D.Adj w v := (Finset.mem_filter.mp hw).2 have he := Finset.card_erase_add_one (s := Finset.univ.filter fun z => D.Adj w z) (a := v) (by simp [hwv]) have hd := hreg w change (outs w).card + 1 = _ at he omega rw [← SimpleGraph.card_neighborFinset_eq_degree] calc _ ≤ (ins.biUnion outs).card := Finset.card_le_card hcover _ ≤ ∑ w ∈ ins, (outs w).card := Finset.card_biUnion_le _ = ∑ _w ∈ ins, (6 : ℕ) := by apply Finset.sum_congr rfl intro w hw exact hsize w hw _ = 6 * ins.card := by simp [Nat.mul_comm] _ ≤ 42 := by have h := hinde v; change ins.card ≤ 7 at h; omega