AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_two_parent_collision_limit

theoremverified

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

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.

  1. 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).

    line 12

      rintro ⟨hu, hv⟩
  2. 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).

    lines 13–20

    uses False.elim

      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
  3. 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).

    lines 21–28

    uses False.elim

      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
  4. 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.

    line 29

      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

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
See it in the graphDiscuss this resultChallenge it