AFTD Auto-Formalizing Theoretical Domains

digraph_two_common_parents_edge_multiplicity

theoremverified

Two distinct vertices with two distinct common predecessors form an edge in the common-predecessor graph with multiplicity at least two.

Statement

theorem digraph_two_common_parents_edge_multiplicity
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (a b t p : α) (hab : a ≠ b) (htp : t ≠ p)
    (hta : D.Adj t a) (htb : D.Adj t b)
    (hpa : D.Adj p a) (hpb : D.Adj p b) :
    s(a,b) ∈ (digraph_common_predecessor_graph D).edgeFinset ∧
      2 ≤ (Finset.univ.filter fun q => ∀ x, x ∈ s(a,b) → D.Adj q x).card
Source
Collision-charge construction for the small-overlap route to OP-110.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 6

The proof, explained

The proof splits the theorem into two parts. First, the pair {a, b} is shown to form an edge in the common-predecessor graph by providing t as a witness of a common predecessor. Second, the set P of common predecessors of a and b is shown to contain both distinct vertices t and p. Since t ≠ p, the subset {t, p} ⊆ P has cardinality 2, and monotonicity of cardinality under inclusion establishes that P has at least two elements.

  1. Adjacency in the common-predecessor graph is decidable.

    For any vertices u and v, the definition of adjacency in the common-predecessor graph is unfolded to the condition that u ≠ v and there exists a common predecessor w adjacent to both u and v. Since α is a finite type with decidable equality and D's adjacency relation is decidable, typeclass inference synthesizes decidability of this relation.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The unordered pair {a, b} is an edge in the common-predecessor graph.

    We enable classical logic and split the goal into its two conjuncts. For the first conjunct, membership of s(a, b) in edgeFinset is rewritten via SimpleGraph.mem_edgeFinset and SimpleGraph.mem_edgeSet to adjacency in the common-predecessor graph. Adjacency requires a ≠ b and a common predecessor; we satisfy this with the hypothesis hab (a ≠ b), the predecessor witness t, and the adjacency assumptions hta and htb.

    lines 14–17

    uses SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet

      classical
      constructor
      · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]
        exact ⟨hab,t,hta,htb⟩
  3. The vertex t is a common predecessor of a and b, so t ∈ P.

    We define P to be the finset of all vertices adjacent to every vertex in s(a, b). By Finset.mem_filter.mpr and Finset.mem_univ, to show t ∈ P it suffices to prove that t is adjacent to every x ∈ s(a, b). By Sym2.mem_iff.mp, any such x is either a or b; the adjacencies hold by hypotheses hta and htb.

    lines 18–25

    uses Finset.mem_filter.mpr, Finset.mem_univ, Sym2.mem_iff.mp

      · let P : Finset α := Finset.univ.filter fun q => ∀ x, x ∈ s(a,b) → D.Adj q x
        have ht : t ∈ P := by
          apply Finset.mem_filter.mpr
          refine ⟨Finset.mem_univ _, ?_⟩
          intro x hx
          rcases Sym2.mem_iff.mp hx with rfl | rfl
          · exact hta
          · exact htb
  4. The vertex p is a common predecessor of a and b, so p ∈ P.

    Similarly, by Finset.mem_filter.mpr and Finset.mem_univ, showing p ∈ P reduces to showing that p is adjacent to every x ∈ s(a, b). By Sym2.mem_iff.mp, x is either a or b, and the required adjacencies hold by hypotheses hpa and hpb.

    lines 26–32

    uses Finset.mem_filter.mpr, Finset.mem_univ, Sym2.mem_iff.mp

        have hp : p ∈ P := by
          apply Finset.mem_filter.mpr
          refine ⟨Finset.mem_univ _, ?_⟩
          intro x hx
          rcases Sym2.mem_iff.mp hx with rfl | rfl
          · exact hpa
          · exact hpb
  5. The two-element set {t, p} is a subset of P.

    For any x ∈ {t, p}, rewriting membership with Finset.mem_insert and Finset.mem_singleton shows that x = t or x = p. Since both t ∈ P and p ∈ P were established in previous steps, x ∈ P in either case.

    lines 33–38

    uses Finset.mem_insert, Finset.mem_singleton

        have hs : ({t,p} : Finset α) ⊆ P := by
          intro x hx
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          rcases hx with rfl | rfl
          · exact ht
          · exact hp
  6. The number of common predecessors |P| is at least 2.

    By Finset.card_le_card, the inclusion {t, p} ⊆ P implies |{t, p}| ≤ |P|. Since t ≠ p (hypothesis htp), the cardinality of {t, p} simplifies to 2. Substituting this into the inequality yields 2 ≤ |P|, completing the proof.

    lines 39–43

    uses Finset.card_le_card

        have hc := Finset.card_le_card hs
        change 2 ≤ P.card
        have hcard : ({t,p} : Finset α).card = 2 := by simp [htp]
        rw [hcard] at hc
        exact hc
SimpleGraph.mem_edgeFinset
An unordered pair belongs to the finite edge set of a simple graph if and only if it belongs to the graph's edge set.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
Finset.mem_filter.mpr
An element belongs to a filtered finset if it belongs to the ambient finset and satisfies the condition.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Sym2.mem_iff.mp
An element belongs to the unordered pair s(a, b) if and only if it equals a or it equals b.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Finset.card_le_card
If s is a subset of t, then the cardinality of s is at most the cardinality of t.

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 in504_common_parents_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_two_common_parents_edge_multiplicity    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (a b t p : α) (hab : a ≠ b) (htp : t ≠ p)    (hta : D.Adj t a) (htb : D.Adj t b)    (hpa : D.Adj p a) (hpb : D.Adj p b) :    s(a,b) ∈ (digraph_common_predecessor_graph D).edgeFinset ∧      2 ≤ (Finset.univ.filter fun q => ∀ x, x ∈ s(a,b) → D.Adj q x).card := by  classical  constructor  · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]    exact ⟨hab,t,hta,htb⟩  · let P : Finset α := Finset.univ.filter fun q => ∀ x, x ∈ s(a,b) → D.Adj q x    have ht : t ∈ P := by      apply Finset.mem_filter.mpr      refine ⟨Finset.mem_univ _, ?_⟩      intro x hx      rcases Sym2.mem_iff.mp hx with rfl | rfl      · exact hta      · exact htb    have hp : p ∈ P := by      apply Finset.mem_filter.mpr      refine ⟨Finset.mem_univ _, ?_⟩      intro x hx      rcases Sym2.mem_iff.mp hx with rfl | rfl      · exact hpa      · exact hpb    have hs : ({t,p} : Finset α) ⊆ P := by      intro x hx      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      rcases hx with rfl | rfl      · exact ht      · exact hp    have hc := Finset.card_le_card hs    change 2 ≤ P.card    have hcard : ({t,p} : Finset α).card = 2 := by simp [htp]    rw [hcard] at hc    exact hc
See it in the graphDiscuss this resultChallenge it