AFTD Auto-Formalizing Theoretical Domains

digraph_two_parent_collision_charge_card_le_one

theoremverified

In a loopless oriented digraph with a chosen common predecessor for every arc, if two vertices have exactly two common predecessors, at most one of those predecessors can assign the same chosen predecessor to both corresponding outgoing arcs.

Statement

theorem digraph_two_parent_collision_charge_card_le_one
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (choose : α → α → α)
    (hloop : ∀ v, ¬ D.Adj v v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hchoice : ∀ s t, D.Adj s t →
      D.Adj (choose s t) s ∧ D.Adj (choose s t) t)
    (a b : α)
    (hm : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card = 2) :
    (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b).card ≤ 1
Source
Graph-specific multiplicity-two charge bound for the OP-110 small-overlap route.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 5

The proof, explained

To show that at most one common predecessor p of a and b can satisfy choose p a = choose p b, we suppose for contradiction that there are two distinct such predecessors, u and v. Because the total number of common predecessors of a and b is known to be exactly 2, u and v must be all the common predecessors. But by the collision-limit theorem digraph_oriented_two_parent_collision_limit, it is impossible for both vertices in a two-element common predecessor set of an oriented loopless digraph to produce such a collision simultaneously.

  1. To show that the set has at most one element, it suffices to assume there are two distinct elements u and v in it and derive a contradiction.

    We define P to be the set of common predecessors of a and b. By Finset.card_le_one.mpr, a finite set has cardinality at most 1 if any two elements in it are equal. We introduce two elements u and v belonging to the filtered set—meaning both are common predecessors of a and b with choose u a = choose u b and choose v a = choose v b—and assume for contradiction that u ≠ v.

    lines 11–16

    uses Finset.card_le_one.mpr, Finset.mem_filter, Finset.mem_univ, true_and

      classical
      let P : Finset α := Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b
      apply Finset.card_le_one.mpr
      intro u hu v hv
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv
      by_contra hne
  2. The pair {u, v} is a subset of P.

    Any element x in {u, v} is either u or v. Because u and v were both extracted from the filtered set, each is an in-neighbor of both a and b, so in either case x is a common predecessor of a and b, placing x in P.

    lines 17–22

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter.mpr, Finset.mem_univ

      have hsub : ({u,v} : Finset α) ⊆ P := by
        intro x hx
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with rfl | rfl
        · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hu.1, hu.2.1⟩
        · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hv.1, hv.2.1⟩
  3. The cardinality of P is at most the cardinality of {u, v}.

    By hypothesis hm, |P| = 2. Since u ≠ v, the pair {u, v} has size 2. Thus |P| ≤ |{u, v}| simplifies to 2 ≤ 2, which holds.

    lines 23–26

      have hcard : P.card ≤ ({u,v} : Finset α).card := by
        change (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card ≤ _
        rw [hm]
        simp [hne]
  4. The set of all common predecessors P is precisely {u, v}.

    Since {u, v} ⊆ P and |P| ≤ |{u, v}|, Finset.eq_of_subset_of_card_le guarantees that the subset {u, v} is equal to P.

    line 27

    uses Finset.eq_of_subset_of_card_le

      have hpair : ({u,v} : Finset α) = P := Finset.eq_of_subset_of_card_le hsub hcard
  5. Every common predecessor of a and b is either u or v.

    If x is an arbitrary common predecessor of a and b, then x belongs to P. Because P = {u, v}, this means x ∈ {u, v}, so x = u or x = v.

    lines 28–32

    uses Finset.mem_filter.mpr, Finset.mem_univ

      have hparents : ∀ x, D.Adj x a → D.Adj x b → x = u ∨ x = v := by
        intro x hxa hxb
        have hxP : x ∈ P := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hxa, hxb⟩
        rw [← hpair] at hxP
        simpa using hxP
  6. A contradiction is reached, completing the proof.

    By digraph_oriented_two_parent_collision_limit, in a loopless oriented digraph where u and v are the only common predecessors of a and b, it is impossible to have both choose u a = choose u b and choose v a = choose v b. Since u and v were chosen precisely to satisfy both equalities, this directly contradicts the lemma.

    lines 33–35

    uses digraph_oriented_two_parent_collision_limit

      have hbad := digraph_oriented_two_parent_collision_limit α D choose hloop hori hchoice
        a b u v hu.1 hu.2.1 hv.1 hv.2.1 hparents
      exact hbad ⟨hu.2.2, hv.2.2⟩
Finset.card_le_one.mpr
A finite set has cardinality at most 1 if every pair of its elements is equal.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
For any proposition p, True ∧ p is equivalent to p.
Finset.mem_insert
An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Finset.mem_filter.mpr
If an element belongs to s and satisfies predicate p, then it belongs to Finset.filter p s.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets s and t, then s = t.
digraph_oriented_two_parent_collision_limit
In a loopless oriented digraph where every arc has a chosen common predecessor, if two vertices have exactly two common predecessors u and v, then u and v cannot both assign the same chosen predecessor to both outgoing arcs.

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

theorem digraph_two_parent_collision_charge_card_le_one    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (choose : α → α → α)    (hloop : ∀ v, ¬ D.Adj v v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hchoice : ∀ s t, D.Adj s t →      D.Adj (choose s t) s ∧ D.Adj (choose s t) t)    (a b : α)    (hm : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card = 2) :    (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b).card ≤ 1 := by  classical  let P : Finset α := Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b  apply Finset.card_le_one.mpr  intro u hu v hv  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv  by_contra hne  have hsub : ({u,v} : Finset α) ⊆ P := by    intro x hx    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with rfl | rfl    · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hu.1, hu.2.1⟩    · exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hv.1, hv.2.1⟩  have hcard : P.card ≤ ({u,v} : Finset α).card := by    change (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card ≤ _    rw [hm]    simp [hne]  have hpair : ({u,v} : Finset α) = P := Finset.eq_of_subset_of_card_le hsub hcard  have hparents : ∀ x, D.Adj x a → D.Adj x b → x = u ∨ x = v := by    intro x hxa hxb    have hxP : x ∈ P := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hxa, hxb⟩    rw [← hpair] at hxP    simpa using hxP  have hbad := digraph_oriented_two_parent_collision_limit α D choose hloop hori hchoice    a b u v hu.1 hu.2.1 hv.1 hv.2.1 hparents  exact hbad ⟨hu.2.2, hv.2.2⟩
See it in the graphDiscuss this resultChallenge it