AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_seven_bounded_indegree_degree_bound

theoremverified

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
Used by 1

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.

  1. 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.

    lines 1–4

    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
  2. 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.

    lines 11–14

      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
  3. 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).

    lines 15–22

    uses SimpleGraph.mem_neighborFinset, Finset.mem_biUnion.mpr

      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]
  4. 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.

    lines 23–29

    uses Finset.mem_filter.mp, Finset.card_erase_add_one

      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
  5. 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.

    lines 30–39

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_congr, Nat.mul_comm

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it