AFTD Auto-Formalizing Theoretical Domains

digraph_arc_choice_collision_repeated_pair

theoremverified

When two outgoing arcs of a loopless digraph receive the same chosen common predecessor, their distinct heads form an auxiliary edge with at least two common predecessors.

Statement

theorem digraph_arc_choice_collision_repeated_pair
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (choose : α → α → α)
    (hloop : ∀ u, ¬ D.Adj u u)
    (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v)
    (u a b : α) (hab : a ≠ b) (hua : D.Adj u a) (hub : D.Adj u b)
    (heq : choose u a = choose u b) :
    s(a,b) ∈ (digraph_common_predecessor_graph D).edgeFinset ∧
      2 ≤ (Finset.univ.filter fun p => ∀ x, x ∈ s(a,b) → D.Adj p x).card
Source
Graph-specific collision-to-repeated-pair step for the OP-110 small-overlap route.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 5

The proof, explained

The proof identifies two distinct common predecessors for the distinct vertices a and b. First, the hypothesis gives u as a common predecessor of a and b. Second, the arc-choice function yields a common predecessor choose u a = choose u b that points to both a and b; this predecessor cannot equal u without creating a self-loop at u. The result then follows from digraph_two_common_parents_edge_multiplicity.

  1. Decidability of adjacency in the common predecessor graph.

    Establish that adjacency in the auxiliary common predecessor graph is decidable, which Lean infers automatically once the definition is unfolded into a bounded existential over the finite vertex type.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The chosen predecessor of (u, a) is an in-neighbor of both u and b.

    Applying the hypothesis hchoice to the arcs (u, a) and (u, b) shows that choose u a is an in-neighbor of both u and a, and choose u b is an in-neighbor of both u and b. Since choose u a = choose u b by assumption, choose u a is also an in-neighbor of b.

    lines 16–18

      have hp := hchoice u a hua
      have hp' := hchoice u b hub
      have hpb : D.Adj (choose u a) b := by rw [heq]; exact hp'.2
  3. u is distinct from choose u a.

    If u were equal to choose u a, then because choose u a has an arc to u, u would have a self-loop (an arc to itself), contradicting the hypothesis that D has no self-loops.

    lines 19–21

      have hne : u ≠ choose u a := by
        intro h
        exact hloop u (by simpa [← h] using hp.1)
  4. The pair {a, b} forms an edge in the common predecessor graph with at least two common predecessors.

    Since u and choose u a are distinct vertices that are both common in-neighbors of the distinct vertices a and b, the theorem digraph_two_common_parents_edge_multiplicity concludes that s(a, b) is an edge of the common predecessor graph and has at least two common predecessors.

    lines 22–23

    uses digraph_two_common_parents_edge_multiplicity

      exact digraph_two_common_parents_edge_multiplicity α D a b u (choose u a)
        hab hne hua hub hp.2 hpb
digraph_two_common_parents_edge_multiplicity
If a loopless digraph has two distinct vertices with two distinct common predecessors, the pair forms an edge in the common predecessor graph and has at least two common predecessors.

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

private instance in504_collision_pair_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_arc_choice_collision_repeated_pair    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (choose : α → α → α)    (hloop : ∀ u, ¬ D.Adj u u)    (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v)    (u a b : α) (hab : a ≠ b) (hua : D.Adj u a) (hub : D.Adj u b)    (heq : choose u a = choose u b) :    s(a,b) ∈ (digraph_common_predecessor_graph D).edgeFinset ∧      2 ≤ (Finset.univ.filter fun p => ∀ x, x ∈ s(a,b) → D.Adj p x).card := by  have hp := hchoice u a hua  have hp' := hchoice u b hub  have hpb : D.Adj (choose u a) b := by rw [heq]; exact hp'.2  have hne : u ≠ choose u a := by    intro h    exact hloop u (by simpa [← h] using hp.1)  exact digraph_two_common_parents_edge_multiplicity α D a b u (choose u a)    hab hne hua hub hp.2 hpb
See it in the graphDiscuss this resultChallenge it