digraph_oriented_two_parent_collision_limit
In an oriented loopless digraph, if two vertices are dominated by both members of a displayed pair and have no common predecessor outside that pair, the two outgoing arcs from each member cannot both receive the same chosen common predecessor.
Statement
theorem digraph_oriented_two_parent_collision_limit (α : Type) (D : Digraph α) (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 u v : α) (hua : D.Adj u a) (hub : D.Adj u b) (hva : D.Adj v a) (hvb : D.Adj v b) (hparents : ∀ x, D.Adj x a → D.Adj x b → x = u ∨ x = v) : ¬ (choose u a = choose u b ∧ choose v a = choose v b)
- Source
- Multiplicity-two collision bound in the small-overlap route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- 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_two_parent_collision_charge_card_le_oneIn a loopless oriented digraph with a chosen common predecessor for every arc, if two vertices have exactly two common predecessors, at…
- 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 proceeds by contradiction. Assuming both chosen predecessors coincide, the vertex choose(u, a) is a common predecessor of both a and b as well as u; since the only common predecessors of a and b are u and v, and looplessness forbids u, this vertex must be v, giving an arc from v to u. Symmetrically, choose(v, a) must be u, giving an arc from u to v. The existence of arcs in both directions between u and v contradicts the assumption that the digraph is oriented.
Assume for contradiction that the chosen predecessors coincide for both u and v.
We assume the negation of the theorem's conclusion, obtaining the hypotheses that choose(u, a) = choose(u, b) (labeled hu) and choose(v, a) = choose(v, b) (labeled hv), and aim to derive a contradiction (False).
rintro ⟨hu, hv⟩
The chosen predecessor for u must be v, which implies an arc from v to u.
By the choice property (hchoice), p = choose(u, a) is adjacent to both u and a. Because choose(u, a) = choose(u, b) by assumption (hu), p is also adjacent to b. Thus p is a common predecessor of both a and b. By the uniqueness of common predecessors (hparents), p must be either u or v. If p = u, then u would have a self-loop (D.Adj u u), which contradicts the loopless hypothesis (hloop); hence p must be v. Since p is adjacent to u, this establishes that v is adjacent to u (D.Adj v u).
uses
False.elimhave hpu := hchoice u a hua have hpu' := hchoice u b hub have hpb : D.Adj (choose u a) b := by rw [hu]; exact hpu'.2 have hp : choose u a = v := by rcases hparents (choose u a) hpu.2 hpb with h | h · exact False.elim (hloop u (by simpa [h] using hpu.1)) · exact h have hvu : D.Adj v u := hp ▸ hpu.1
Symmetrically, the chosen predecessor for v must be u, which implies an arc from u to v.
Similarly, q = choose(v, a) is adjacent to both v and a, and because choose(v, a) = choose(v, b) by assumption (hv), q is also adjacent to b. By hparents, q must be u or v. If q = v, then v would have a self-loop, contradicting hloop; hence q = u. Since q is adjacent to v, substituting q = u gives an arc from u to v (D.Adj u v).
uses
False.elimhave hpv := hchoice v a hva have hpv' := hchoice v b hvb have hqb : D.Adj (choose v a) b := by rw [hv]; exact hpv'.2 have hq : choose v a = u := by rcases hparents (choose v a) hpv.2 hqb with h | h · exact h · exact False.elim (hloop v (by simpa [h] using hpv.1)) have huv : D.Adj u v := hq ▸ hpv.1
A contradiction is reached with the orientation of the digraph.
Having established both an arc from v to u and an arc from u to v, we directly contradict the orientation hypothesis (hori), which states that the digraph contains no mutual adjacency.
exact hori u v huv hvu
False.elim- The principle of explosion: from a proof of False (a contradiction), any proposition follows.
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_oriented_two_parent_collision_limit (α : Type) (D : Digraph α) (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 u v : α) (hua : D.Adj u a) (hub : D.Adj u b) (hva : D.Adj v a) (hvb : D.Adj v b) (hparents : ∀ x, D.Adj x a → D.Adj x b → x = u ∨ x = v) : ¬ (choose u a = choose u b ∧ choose v a = choose v b) := by rintro ⟨hu, hv⟩ have hpu := hchoice u a hua have hpu' := hchoice u b hub have hpb : D.Adj (choose u a) b := by rw [hu]; exact hpu'.2 have hp : choose u a = v := by rcases hparents (choose u a) hpu.2 hpb with h | h · exact False.elim (hloop u (by simpa [h] using hpu.1)) · exact h have hvu : D.Adj v u := hp ▸ hpu.1 have hpv := hchoice v a hva have hpv' := hchoice v b hvb have hqb : D.Adj (choose v a) b := by rw [hv]; exact hpv'.2 have hq : choose v a = u := by rcases hparents (choose v a) hpv.2 hqb with h | h · exact h · exact False.elim (hloop v (by simpa [h] using hpv.1)) have huv : D.Adj u v := hq ▸ hpv.1 exact hori u v huv hvu