AFTD Auto-Formalizing Theoretical Domains

digraph_short_parent_set_not_all_charged

theoremverified

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
Used by 4

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.

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

    lines 12–17

    uses Finset.filter_subset, Finset.card_le_card

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

    lines 18–19

    uses Finset.eq_of_subset_of_card_le

      by_contra hn
      have heq : C = P := Finset.eq_of_subset_of_card_le hsub (by omega)
  3. 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.

    lines 20–29

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ

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

    lines 30–34

    uses digraph_finite_predecessor_closed_set_cycle, Finset.card_le_card

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

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