AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_vertex_incidence_bound

theoremverified

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

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.

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

    lines 1–4

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

    lines 12–17

    uses Finset.card_filter_add_card_filter_not, SimpleGraph.incidenceFinset_eq_filter, SimpleGraph.card_incidenceFinset_eq_degree

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

    lines 18–40

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Finset.mem_biUnion.mpr, Finset.card_le_card, Finset.card_biUnion_le

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

    lines 41–81

    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_iff

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

    lines 82–92

    uses Finset.sum_congr, Finset.sum_ite, Nat.mul_comm

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

    lines 93–98

    uses Sym2.card_image_offDiag

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

    lines 99–113

    uses Finset.sum_add_distrib, Finset.sum_congr, Finset.card_filter_add_card_filter_not

      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
  8. (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).

    line 114

      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.

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