digraph_two_parent_collision_charge_card_le_one
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
- digraph_oriented_two_parent_collision_limitIn an oriented loopless digraph, if two vertices are dominated by both members of a displayed pair and have no common predecessor outside…
- Used by 5
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
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.
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.
uses
Finset.card_le_one.mpr,Finset.mem_filter,Finset.mem_univ,true_andclassical 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
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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_filter.mpr,Finset.mem_univhave 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⟩
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.
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]
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.
uses
Finset.eq_of_subset_of_card_lehave hpair : ({u,v} : Finset α) = P := Finset.eq_of_subset_of_card_le hsub hcardEvery 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.
uses
Finset.mem_filter.mpr,Finset.mem_univhave 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
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.
uses
digraph_oriented_two_parent_collision_limithave 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
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.
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⟩