digraph_two_common_parents_edge_multiplicity
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
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 6
- 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_arc_choice_collision_repeated_pairWhen two outgoing arcs of a loopless digraph receive the same chosen common predecessor, their distinct heads form an auxiliary edge with…
- 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
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
uses
SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSetclassical constructor · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact ⟨hab,t,hta,htb⟩
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.
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
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.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Sym2.mem_iff.mphave 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
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.
uses
Finset.mem_insert,Finset.mem_singletonhave 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
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.
uses
Finset.card_le_cardhave 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.
- The private instance in504_common_parents_decAdj (lines 1–5) proves decidability of adjacency in the common-predecessor graph, a formal prerequisite for Lean to construct the finite set of edges edgeFinset.
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.
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