digraph_short_parent_set_not_all_charged
In a loopless digraph of directed girth at least g, a nonempty common-predecessor set with fewer than g members cannot have every parent choose the same predecessor for both outgoing arcs.
Statement
theorem digraph_short_parent_set_not_all_charged (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (g : ℕ) (a b : α) (hloop : ∀ v, ¬ D.Adj v v) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hne : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty) (hsmall : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card < g) : ((Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).filter fun p => choose p a = choose p b).card < (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card
- Source
- Girth-dependent collision accounting for the four-cycle campaign; experiment 13463.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
- digraph_finite_predecessor_closed_set_cycleA nonempty finite predecessor-closed subset of a loopless digraph contains a directed cycle.
- Used by 4
- digraph_oriented_girth_degree_deficit_overlap_budgetIn a finite loopless oriented arc-dominated digraph whose directed cycles have at least g vertices, with g at least three, g−1 times the…
- 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 proceeds by contradiction. If all common predecessors of a and b were to choose the same predecessor for both vertices, the subset C of such common predecessors would equal the entire set P of common predecessors. In that case, each vertex u ∈ P would have an in-neighbor v = choose u a = choose u b that also belongs to P, making P predecessor-closed. Since P is finite, nonempty, and the graph is loopless, P would contain a directed cycle; but by the girth assumption this cycle must have size at least g, contradicting the hypothesis |P| < g.
Define the set P of common predecessors and its subset C of doubly charged predecessors, reformulating the goal as |C| < |P|.
We work classically (line 12). Let P be the set of common predecessors of a and b, and let C ⊆ P be the subset of vertices p that choose the same predecessor for both a and b (lines 13–14). By Finset.filter_subset, C is a subset of P, which implies |C| ≤ |P| by Finset.card_le_card (lines 15–16). The goal is to show the strict inequality |C| < |P| (line 17).
uses
Finset.filter_subset,Finset.card_le_cardclassical let P : Finset α := Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b let C : Finset α := P.filter fun p => choose p a = choose p b have hsub : C ⊆ P := Finset.filter_subset _ _ have hcard := Finset.card_le_card hsub change C.card < P.card
Assume for contradiction that the inequality fails, which forces C = P.
We suppose for contradiction that ¬(|C| < |P|), meaning |P| ≤ |C| (line 18). Because C ⊆ P and |P| ≤ |C|, Finset.eq_of_subset_of_card_le together with linear arithmetic (omega) establishes that C = P (line 19).
uses
Finset.eq_of_subset_of_card_leby_contra hn have heq : C = P := Finset.eq_of_subset_of_card_le hsub (by omega)
Every vertex in P has an in-neighbor that also belongs to P.
Let u ∈ P (line 21). Since C = P, we have u ∈ C (line 22). By Finset.mem_filter.mp, this means choose u a = choose u b (line 23) and u is an in-neighbor of both a and b (line 24). Hypothesis hchoice gives that v = choose u a has directed arcs v → u and v → a (line 25), while choose u b has an arc to b (line 26). Because choose u a = choose u b, v also has an arc v → b. Hence v is a common predecessor of a and b, so v ∈ P by Finset.mem_filter.mpr and Finset.mem_univ (lines 27–29). Since v → u, u has an in-neighbor in P.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univhave hpred : ∀ u ∈ P, ∃ v ∈ P, D.Adj v u := by intro u hu have huC : u ∈ C := by rw [heq]; exact hu have hsame : choose u a = choose u b := (Finset.mem_filter.mp huC).2 have huab : D.Adj u a ∧ D.Adj u b := (Finset.mem_filter.mp hu).2 have ha := hchoice u a huab.1 have hb := hchoice u b huab.2 refine ⟨choose u a, ?_, ha.1⟩ apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, ha.2, by simpa [hsame] using hb.2⟩
The existence of in-neighbors in P forces a directed cycle in P, contradicting the girth lower bound.
Applying digraph_finite_predecessor_closed_set_cycle to P—which is finite, nonempty, loopless, and predecessor-closed—yields a directed cycle K ⊆ P (line 30). By the girth assumption hgirth, g ≤ |K| (line 31). By Finset.card_le_card, |K| ≤ |P| (line 32). However, hypothesis hsmall states |P| < g (line 33). The chain of inequalities g ≤ |K| ≤ |P| < g is impossible, and omega closes the goal by deriving a contradiction (line 34).
uses
digraph_finite_predecessor_closed_set_cycle,Finset.card_le_cardobtain ⟨K,hK,hKP⟩ := digraph_finite_predecessor_closed_set_cycle α D P hne hloop hpred have hc := hgirth K hK have hle := Finset.card_le_card hKP change P.card < g at hsmall omega
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original finite set.
Finset.card_le_card- A subset of a finite set has cardinality at most that of the ambient set.
Finset.eq_of_subset_of_card_le- If s is a subset of a finite set t and |t| ≤ |s|, then s = t.
Finset.mem_filter.mp- If an element belongs to the filtered set {x ∈ s | p x}, then it belongs to s and satisfies p.
Finset.mem_filter.mpr- If an element belongs to s and satisfies p, then it belongs to the filtered set {x ∈ s | p x}.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set of that type.
digraph_finite_predecessor_closed_set_cycle- In a loopless finite directed graph, any nonempty set of vertices in which every vertex has an in-neighbor inside the set contains a directed cycle.
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_short_parent_set_not_all_charged (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (g : ℕ) (a b : α) (hloop : ∀ v, ¬ D.Adj v v) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hne : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty) (hsmall : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card < g) : ((Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).filter fun p => choose p a = choose p b).card < (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).card := by classical let P : Finset α := Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b let C : Finset α := P.filter fun p => choose p a = choose p b have hsub : C ⊆ P := Finset.filter_subset _ _ have hcard := Finset.card_le_card hsub change C.card < P.card by_contra hn have heq : C = P := Finset.eq_of_subset_of_card_le hsub (by omega) have hpred : ∀ u ∈ P, ∃ v ∈ P, D.Adj v u := by intro u hu have huC : u ∈ C := by rw [heq]; exact hu have hsame : choose u a = choose u b := (Finset.mem_filter.mp huC).2 have huab : D.Adj u a ∧ D.Adj u b := (Finset.mem_filter.mp hu).2 have ha := hchoice u a huab.1 have hb := hchoice u b huab.2 refine ⟨choose u a, ?_, ha.1⟩ apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, ha.2, by simpa [hsame] using hb.2⟩ obtain ⟨K,hK,hKP⟩ := digraph_finite_predecessor_closed_set_cycle α D P hne hloop hpred have hc := hgirth K hK have hle := Finset.card_le_card hKP change P.card < g at hsmall omega