digraph_arc_choice_collision_repeated_pair
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
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_two_common_parents_edge_multiplicityTwo distinct vertices with two distinct common predecessors form an edge in the common-predecessor graph with multiplicity at least two.
- 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
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
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
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.
have hne : u ≠ choose u a := by intro h exact hloop u (by simpa [← h] using hp.1)
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.
uses
digraph_two_common_parents_edge_multiplicityexact 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
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_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