AFTD Auto-Formalizing Theoretical Domains

digraph_girth_arc_map_weighted_budget

theoremverified

For 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 dirty parents plus missing arc-map images is bounded by twice g times overlap plus the displayed multiplicity correction.

Statement

theorem digraph_girth_arc_map_weighted_budget
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (choose : α → α → α) (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card)
    (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) :
    let Arc := {e : α × α // D.Adj e.1 e.2}
    let f : Arc → Arc := fun e =>
      ⟨(choose e.val.1 e.val.2, e.val.1), (hchoice e.val.1 e.val.2 e.property).1⟩
    let dirty : Finset α := Finset.univ.filter fun u =>
      ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b
    (g - 1) * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤
      2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
        (digraph_common_predecessor_graph D).edgeFinset.card) +
        digraph_common_predecessor_girth_correction α D g
Source
Girth-dependent center budget for the four-cycle campaign; experiment 13474.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 16
Used by 2

The proof, explained

The theorem is proved by charging missing arcs and dirty parents to the repeated edges of the common predecessor graph. Each collision of the arc choice endomap f identifies an edge in the common predecessor graph with multiple common parents, allowing the number of missing arcs to be bounded by the total collision charge. The directed girth lower bound g ensures that edges with fewer than g parents cannot have all their parents charged, enabling an edge-by-edge weight inequality from girth_parent_charge_weight_bound. Summing this inequality over all repeated edges and expressing the parent multiplicities in terms of vertex out-degree overlap and the girth correction term yields the result.

  1. Adjacency in the common predecessor graph is decidable. automation

    For any two vertices u and v, adjacency in the common predecessor graph is defined by u ≠ v and the existence of a common predecessor in D. Since the digraph vertex type α is finite and adjacency in D is decidable, this existential condition is decidable by typeclass synthesis.

    lines 1–5

    private instance in516_girth_weighted_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_instance
  2. The arc endomap f and a chosen section r satisfy f(r(f(x))) = f(x) for all arcs x.

    Working classically, we define the type of arcs as pairs of vertices with an adjacency witness. The map f sends each arc (u, v) to (choose(u, v), u), which is valid since choose(u, v) is a common predecessor of u and v. Using Classical.choose, r selects a preimage for every arc in the image of f and acts as the identity elsewhere, guaranteeing f(r(f(x))) = f(x).

    lines 22–34

    uses Classical.choose_spec

      classical
      let Arc := {e : α × α // D.Adj e.1 e.2}
      let f : Arc → Arc := fun e =>
        ⟨(choose e.val.1 e.val.2, e.val.1), (hchoice e.val.1 e.val.2 e.property).1⟩
      let r : Arc → Arc := fun y => if h : ∃ x, f x = y then Classical.choose h else y
      have hr : ∀ x, f (r (f x)) = f x := by
        intro x
        dsimp [r]
        split
        · rename_i h
          exact Classical.choose_spec h
        · rename_i h
          exact (h ⟨x,rfl⟩).elim
  3. The arc projections satisfy htail (f x = f y → tail x = tail y) and an arc is uniquely determined by its tail and head.

    The second component of f(x) is tail(x), so any collision f x = f y implies tail x = tail y by applying congrArg to the second component. Moreover, since an arc is a directed edge between its tail and head, the map x ↦ (tail x, head x) is injective by Subtype.ext.

    lines 35–42

    uses congrArg, Subtype.ext

      let tail : Arc → α := fun x => x.val.1
      let head : Arc → α := fun x => x.val.2
      have htail : ∀ x y, f x = f y → tail x = tail y := by
        intro x y h
        exact congrArg (fun z : Arc => z.val.2) h
      have hkey : Function.Injective (fun x => (tail x, head x)) := by
        intro x y h
        exact Subtype.ext h
  4. We define the parent sets, the edges of the common predecessor graph, repeated edges, dirty vertices, missing arcs, non-representatives, and edge charges.

    For an unordered pair e, parent(e) is the finset of common predecessors of its vertices. The edges of the common predecessor graph are pairs sharing at least one parent, and repeated is the subset of edges with at least 2 parents. Dirty vertices are those sharing two or more common out-neighbors with another vertex. Missing arcs are arcs outside the image of f. Non-representative arcs are those with r(f(x)) ≠ x; each non-representative arc x defines an unordered pair edge(x) = s(head(x), head(r(f(x)))), and charge(e) collects the tails of all non-representative arcs that map to e.

    lines 43–52

      let parent : Sym2 α → Finset α := fun e =>
        Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x
      let edges := (digraph_common_predecessor_graph D).edgeFinset
      let repeated := edges.filter fun e => 2 ≤ (parent e).card
      let dirty : Finset α := Finset.univ.filter fun u =>
        ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b
      let missing : Finset Arc := Finset.univ \ Finset.univ.image f
      let nonrep : Finset Arc := Finset.univ.filter fun x => r (f x) ≠ x
      let edge : Arc → Sym2 α := fun x => s(head x, head (r (f x)))
      let charge : Sym2 α → Finset α := fun e => (nonrep.filter fun x => edge x = e).image tail
  5. For every arc x, r(f(x)) has the same tail as x and identical predecessor choice, and if r(f(x)) ≠ x then their heads are distinct.

    Projecting the equality f(r(f(x))) = f(x) onto the two components shows that tail(r(f(x))) = tail(x) and choose(tail(x), head(r(f(x)))) = choose(tail(x), head(x)). If r(f(x)) ≠ x, their heads must be distinct, because equal tails and equal heads would make the arcs identical by Subtype.ext and Prod.ext.

    lines 53–65

    uses congrArg, Subtype.ext, Prod.ext

      have hdata (x : Arc) : tail (r (f x)) = tail x ∧
          choose (tail x) (head (r (f x))) = choose (tail x) (head x) := by
        have h := hr x
        have ht : tail (r (f x)) = tail x := htail _ _ h
        have hc : choose (tail (r (f x))) (head (r (f x))) =
            choose (tail x) (head x) := congrArg (fun z : Arc => z.val.1) h
        rw [ht] at hc
        exact ⟨ht,hc⟩
      have hheads (x : Arc) (hx : r (f x) ≠ x) : head x ≠ head (r (f x)) := by
        intro h
        apply hx
        apply Subtype.ext
        exact Prod.ext (hdata x).1 h.symm
  6. For every non-representative arc x, edge(x) belongs to repeated.

    Since head(x) ≠ head(r(f(x))) and both are out-neighbors of tail(x), and choose(tail(x), head(x)) is a common predecessor of both heads distinct from tail(x) by looplessness, digraph_arc_choice_collision_repeated_pair shows that s(head(x), head(r(f(x)))) is an edge with at least 2 common parents, so it belongs to repeated.

    lines 66–75

    uses digraph_arc_choice_collision_repeated_pair, Finset.mem_filter.mpr

      have hcharged (x : Arc) (hx : r (f x) ≠ x) : edge x ∈ repeated := by
        have hd := hdata x
        have ha : D.Adj (tail x) (head x) := x.property
        have hb : D.Adj (tail x) (head (r (f x))) := by
          have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property
          rw [hd.1] at hp
          exact hp
        have hh := digraph_arc_choice_collision_repeated_pair α D choose hloop hchoice
          (tail x) (head x) (head (r (f x))) (hheads x hx) ha hb hd.2.symm
        exact Finset.mem_filter.mpr hh
  7. The number of missing arcs is bounded by the sum of charges over all repeated edges.

    By the finite endomap collision charging identity finite_endomap_collision_charge_identity, the number of arcs outside the image of f equals the sum of the cardinalities of charge(e) over all repeated edges, which immediately implies the inequality.

    lines 76–80

    uses finite_endomap_collision_charge_identity

      have hcharge : missing.card ≤ ∑ e ∈ repeated, (charge e).card := by
        have h := finite_endomap_collision_charge_identity Arc α α f r tail head repeated
          hr htail hkey hcharged
        change missing.card = ∑ e ∈ repeated, (charge e).card at h
        exact h.le
  8. The set of dirty vertices is contained in the union of parent sets over all repeated edges.

    A dirty vertex u shares two distinct out-neighbors a ≠ b with another vertex p ≠ u. By digraph_two_common_parents_edge_multiplicity, s(a, b) has at least two common parents (u and p) and thus belongs to repeated. Since u is adjacent to both a and b, u belongs to parent(s(a, b)).

    lines 81–93

    uses digraph_two_common_parents_edge_multiplicity, Finset.mem_biUnion.mpr, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ, Sym2.mem_iff.mp

      have hdirty : dirty ⊆ repeated.biUnion parent := by
        intro u hu
        obtain ⟨_,a,b,p,hab,hpu,hua,hub,hpa,hpb⟩ := Finset.mem_filter.mp hu
        have hh := digraph_two_common_parents_edge_multiplicity α D a b u p
          hab hpu.symm hua hub hpa hpb
        apply Finset.mem_biUnion.mpr
        refine ⟨s(a,b), Finset.mem_filter.mpr hh, ?_⟩
        apply Finset.mem_filter.mpr
        refine ⟨Finset.mem_univ _, ?_⟩
        intro x hx
        rcases Sym2.mem_iff.mp hx with rfl | rfl
        · exact hua
        · exact hub
  9. For every repeated edge e, charge(e) is a subset of parent(e), and parent(e) has cardinality at least 2.

    Every vertex in charge(e) is the tail of some arc x whose head and counterpart head form e; since tail(x) = tail(r(f(x))) is adjacent to both heads, it is a common predecessor of e, so charge(e) ⊆ parent(e). The bound 2 ≤ |parent(e)| is immediate from the definition of repeated.

    lines 94–110

    uses Finset.mem_image.mp, Finset.mem_filter.mp, Finset.mem_univ, Sym2.mem_iff.mp

      have hsubset : ∀ e ∈ repeated, charge e ⊆ parent e := by
        intro e he u hu
        obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu
        have hxe : edge x = e := (Finset.mem_filter.mp hx).2
        apply Finset.mem_filter.mpr
        refine ⟨Finset.mem_univ _, ?_⟩
        intro z hz
        rw [← hxe] at hz
        change z ∈ s(head x, head (r (f x))) at hz
        rcases Sym2.mem_iff.mp hz with rfl | rfl
        · exact x.property
        · have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property
          rw [(hdata x).1] at hp
          exact hp
      have hm : ∀ e ∈ repeated, 2 ≤ (parent e).card := by
        intro e he
        exact (Finset.mem_filter.mp he).2
  10. If a repeated edge e has exactly two parents, its charge has cardinality at most 1.

    Writing e as an unordered pair s(a, b), the parents are those vertices adjacent to both a and b. Any vertex in charge(s(a, b)) must satisfy choose(p, a) = choose(p, b). In an oriented loopless digraph with exactly two common parents, digraph_two_parent_collision_charge_card_le_one implies that at most one parent can satisfy this equality, so |charge(e)| ≤ 1.

    lines 111–147

    uses Sym2.ind, true_and, Sym2.mem_mk_left, Sym2.mem_mk_right, digraph_two_parent_collision_charge_card_le_one, Finset.card_le_card

      have htwo : ∀ e ∈ repeated, (parent e).card = 2 → (charge e).card ≤ 1 := by
        intro e he hm2
        induction e using Sym2.ind with
        | h a b =>
          have hparentEq : parent s(a,b) =
              Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by
            ext p
            simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and]
            constructor
            · intro h
              exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩
            · rintro ⟨ha,hb⟩ x hx
              rcases Sym2.mem_iff.mp hx with rfl | rfl
              · exact ha
              · exact hb
          rw [hparentEq] at hm2
          have hlim := digraph_two_parent_collision_charge_card_le_one α D choose hloop hori hchoice a b hm2
          have hsub : charge s(a,b) ⊆
              Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by
            intro u hu
            obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu
            have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2
            have hd := hdata x
            have ha : D.Adj (tail x) (head x) := x.property
            have hb : D.Adj (tail x) (head (r (f x))) := by
              have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property
              rw [hd.1] at hp
              exact hp
            apply Finset.mem_filter.mpr
            refine ⟨Finset.mem_univ _, ?_⟩
            rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩
            · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb,
                by simpa [hxa,hxb] using hd.2.symm⟩
            · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha,
                by simpa [hxa,hxb] using hd.2⟩
          have hh := Finset.card_le_card hsub
          exact hh.trans hlim
  11. For any repeated edge e with strictly fewer than g parents, |charge(e)| < |parent(e)|.

    Writing e = s(a, b), any charged parent satisfies choose(p, a) = choose(p, b). If all common parents satisfied this and |parent(e)| < g, tracing backward along choice arcs would form a directed cycle of length less than g, contradicting the girth hypothesis. This is established by digraph_short_parent_set_not_all_charged, which yields |charge(e)| < |parent(e)|.

    lines 148–196

    uses Sym2.ind, true_and, Sym2.mem_mk_left, Sym2.mem_mk_right, Finset.card_pos.mp, digraph_short_parent_set_not_all_charged, Finset.card_le_card

      have hshort : ∀ e ∈ repeated, (parent e).card < g → (charge e).card < (parent e).card := by
        intro e he hs
        induction e using Sym2.ind with
        | h a b =>
          have hparentEq : parent s(a,b) =
              Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by
            ext p
            simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and]
            constructor
            · intro h
              exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩
            · rintro ⟨ha,hb⟩ x hx
              rcases Sym2.mem_iff.mp hx with rfl | rfl
              · exact ha
              · exact hb
          have hnonempty : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty := by
            apply Finset.card_pos.mp
            have h := hm s(a,b) he
            rw [hparentEq] at h
            omega
          have hlt := digraph_short_parent_set_not_all_charged α D choose g a b hloop hchoice hgirth
            hnonempty (by simpa [hparentEq] using hs)
          have hsub : charge s(a,b) ⊆
              Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by
            intro u hu
            obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu
            have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2
            have hd := hdata x
            have ha : D.Adj (tail x) (head x) := x.property
            have hb : D.Adj (tail x) (head (r (f x))) := by
              have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property
              rw [hd.1] at hp
              exact hp
            apply Finset.mem_filter.mpr
            refine ⟨Finset.mem_univ _, ?_⟩
            rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩
            · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb,
                by simpa [hxa,hxb] using hd.2.symm⟩
            · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha,
                by simpa [hxa,hxb] using hd.2⟩
          have hsub' : charge s(a,b) ⊆
              (Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b)).filter
                (fun p => choose p a = choose p b) := by
            intro p hp
            have hh := Finset.mem_filter.mp (hsub hp)
            exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hh.2.1, hh.2.2.1⟩, hh.2.2.2⟩
          have hc := Finset.card_le_card hsub'
          rw [hparentEq]
          omega
  12. The sum of |parent(e)| - 1 over repeated edges equals the total out-degree pair overlap sum ∑_v choose(out_deg(v), 2) minus the number of edges.

    Every edge in the common predecessor graph has at least one common parent (hparentPos). For edges with strictly fewer than 2 parents, |parent(e)| = 1, so |parent(e)| - 1 = 0; thus the sum over repeated edges equals the sum over all edges. By digraph_common_predecessor_overlap_incidence_identity, this sum equals the total vertex out-degree pair combinations minus the edge count.

    lines 197–224

    uses Sym2.ind, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Finset.card_pos.mpr, digraph_common_predecessor_overlap_incidence_identity, Finset.sum_filter, Finset.sum_congr

      have hparentPos : ∀ e ∈ edges, 1 ≤ (parent e).card := by
        intro e he
        induction e using Sym2.ind with
        | h a b =>
          rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he
          obtain ⟨_,p,hpa,hpb⟩ := he
          apply Finset.card_pos.mpr
          refine ⟨p, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩
          intro x hx
          rcases Sym2.mem_iff.mp hx with rfl | rfl
          · exact hpa
          · exact hpb
      have hsum : (∑ e ∈ repeated, ((parent e).card - 1)) =
          (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - edges.card := by
        have hall := digraph_common_predecessor_overlap_incidence_identity α D
        have hs : (∑ e ∈ repeated, ((parent e).card - 1)) =
            ∑ e ∈ edges, ((parent e).card - 1) := by
          dsimp [repeated]
          rw [Finset.sum_filter]
          apply Finset.sum_congr rfl
          intro e he
          by_cases h : 2 ≤ (parent e).card
          · simp [h]
          · have hp := hparentPos e he
            have hc : (parent e).card = 1 := by omega
            simp [h,hc]
        rw [hs]
        exact hall
  13. The sum of parent and charge sizes satisfies (g - 1)(∑ |parent(e)| + ∑ |charge(e)|) ≤ 2g(∑ (|parent(e)| - 1)) + girth_correction, and dirty vertices are bounded by ∑ |parent(e)|.

    By the union bound, |dirty| ≤ ∑ |parent(e)|. For each repeated edge e, girth_parent_charge_weight_bound applies using 2 ≤ |parent(e)|, |charge(e)| ≤ |parent(e)|, and |charge(e)| < |parent(e)| when |parent(e)| < g, giving (g - 1)(|parent(e)| + |charge(e)|) ≤ 2g(|parent(e)| - 1) + (g + 1 - 2|parent(e)|). Summing over repeated edges via Finset.sum_le_sum and distributing yields the aggregated budget inequality, where the second sum matches digraph_common_predecessor_girth_correction by definition.

    lines 225–247

    uses Finset.card_le_card, Finset.card_biUnion_le, girth_parent_charge_weight_bound, Finset.sum_le_sum, Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib, Finset.sum_filter, Finset.sum_congr

      have hsum_parent : dirty.card ≤ ∑ e ∈ repeated, (parent e).card := by
        exact (Finset.card_le_card hdirty).trans Finset.card_biUnion_le
      have hedge : ∀ e ∈ repeated,
          (g - 1) * ((parent e).card + (charge e).card) ≤
            2 * g * ((parent e).card - 1) + (g + 1 - 2 * (parent e).card) := by
        intro e he
        exact girth_parent_charge_weight_bound g (parent e).card (charge e).card hg (hm e he)
          (Finset.card_le_card (hsubset e he)) (hshort e he)
      have hsumineq := Finset.sum_le_sum hedge
      have hbudget : (g - 1) * ((∑ e ∈ repeated, (parent e).card) +
          (∑ e ∈ repeated, (charge e).card)) ≤
          2 * g * (∑ e ∈ repeated, ((parent e).card - 1)) +
          (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) := by
        simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq
      have hcorrection : (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) =
          digraph_common_predecessor_girth_correction α D g := by
        simp only [digraph_common_predecessor_girth_correction, repeated, Finset.sum_filter]
        apply Finset.sum_congr
        · ext e
          simp [edges]
        · intro e he
          simp [parent]
    
  14. (g - 1) * (|dirty| + |missing|) ≤ 2 * g * (overlap) + girth_correction.

    Adding |dirty| ≤ ∑ |parent(e)| and |missing| ≤ ∑ |charge(e)| and multiplying by g - 1 via Nat.mul_le_mul_left and Nat.add_le_add bounds the left-hand side by the aggregated budget. Replacing the repeated parent sum by the out-degree overlap identity and the correction sum by its definition completes the proof by transitivity.

    lines 248–251

    uses Nat.mul_le_mul_left, Nat.add_le_add

      have hscaled := Nat.mul_le_mul_left (g - 1) (Nat.add_le_add hsum_parent hcharge)
      change (g - 1) * (dirty.card + missing.card) ≤ _
      rw [← hsum, ← hcorrection]
      exact hscaled.trans hbudget
Classical.choose_spec
Given an existential proof h : ∃ x, p x, Classical.choose h satisfies the predicate p.
congrArg
If x = y, then f x = f y.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
digraph_arc_choice_collision_repeated_pair
In a loopless digraph with common predecessor choice, if two distinct out-neighbors a ≠ b of u have choose u a = choose u b, then s(a, b) is an edge of the common predecessor graph with at least 2 common parents.
Finset.mem_filter.mpr
An element belongs to a filtered finset if it belongs to the base finset and satisfies the filter predicate.
Finset.mem_filter.mp
If an element belongs to a filtered finset, it belongs to the base finset and satisfies the filter predicate.
finite_endomap_collision_charge_identity
For a finite endomap with a section on its image and tail/head coordinates, the number of missing elements equals the sum of collision charges over a covering set of edges.
digraph_two_common_parents_edge_multiplicity
In a digraph, if distinct vertices a ≠ b have two distinct common parents t ≠ p, then s(a, b) is an edge of the common predecessor graph with at least 2 common parents.
Finset.mem_biUnion.mpr
If an element belongs to the finset associated to some index, it belongs to the indexed union (biUnion).
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
Sym2.mem_iff.mp
An element x belongs to an unordered pair s(a, b) if and only if x = a or x = b.
Finset.mem_image.mp
If an element belongs to the image of a finset under a function, it is the image of some element in that finset.
Sym2.ind
A property holds for all unordered pairs if it holds for every pair of the form s(a, b).
true_and
The propositional identity (True ∧ p) = p.
Sym2.mem_mk_left
The left element belongs to the unordered pair: x ∈ s(x, y).
Sym2.mem_mk_right
The right element belongs to the unordered pair: y ∈ s(x, y).
digraph_two_parent_collision_charge_card_le_one
In an oriented loopless digraph, if an unordered pair has exactly 2 common parents, at most one of them can satisfy choose p a = choose p b.
Finset.card_le_card
If s ⊆ t for finsets, then |s| ≤ |t|.
Finset.card_pos.mp
If 0 < |s| for a finset, then s is nonempty.
Finset.card_pos.mpr
If a finset is nonempty, then 0 < |s|.
digraph_short_parent_set_not_all_charged
In a loopless digraph of directed girth at least g, if an edge has non-empty common parent set of size strictly less than g, not all parents can have identical predecessor choice on the endpoints.
SimpleGraph.mem_edgeFinset
An unordered pair belongs to the edge finset of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
digraph_common_predecessor_overlap_incidence_identity
The sum of |parent(e)| - 1 over all edges in the common predecessor graph equals the sum of choose(out_deg(v), 2) over all vertices minus the number of edges.
Finset.sum_filter
Rewrites a sum over a filtered finset as a sum over the whole finset with an indicator.
Finset.sum_congr
Two finset sums are equal if their index sets are equal and their summands agree on all elements.
Finset.card_biUnion_le
The cardinality of an indexed union of finsets is at most the sum of their individual cardinalities.
girth_parent_charge_weight_bound
If 3 ≤ g, 2 ≤ m, c ≤ m, and m < g → c < m, then (g - 1) * (m + c) ≤ 2 * g * (m - 1) + (g + 1 - 2 * m).
Finset.sum_le_sum
If f i ≤ g i for all elements i of a finset s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Nat.mul_add
Multiplication distributes over addition: n * (m + k) = n * m + n * k.
Finset.mul_sum
Multiplication by a constant distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_add_distrib
The sum of a pointwise sum of functions equals the sum of their individual sums.
Nat.mul_le_mul_left
If n ≤ m, then k * n ≤ k * m for natural numbers.
Nat.add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d for natural numbers.

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 in516_girth_weighted_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_girth_arc_map_weighted_budget    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (choose : α → α → α) (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card)    (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) :    let Arc := {e : α × α // D.Adj e.1 e.2}    let f : Arc → Arc := fun e =>      ⟨(choose e.val.1 e.val.2, e.val.1), (hchoice e.val.1 e.val.2 e.property).1⟩    let dirty : Finset α := Finset.univ.filter fun u =>      ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b    (g - 1) * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤      2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -        (digraph_common_predecessor_graph D).edgeFinset.card) +        digraph_common_predecessor_girth_correction α D g := by  classical  let Arc := {e : α × α // D.Adj e.1 e.2}  let f : Arc → Arc := fun e =>    ⟨(choose e.val.1 e.val.2, e.val.1), (hchoice e.val.1 e.val.2 e.property).1⟩  let r : Arc → Arc := fun y => if h : ∃ x, f x = y then Classical.choose h else y  have hr : ∀ x, f (r (f x)) = f x := by    intro x    dsimp [r]    split    · rename_i h      exact Classical.choose_spec h    · rename_i h      exact (h ⟨x,rfl⟩).elim  let tail : Arc → α := fun x => x.val.1  let head : Arc → α := fun x => x.val.2  have htail : ∀ x y, f x = f y → tail x = tail y := by    intro x y h    exact congrArg (fun z : Arc => z.val.2) h  have hkey : Function.Injective (fun x => (tail x, head x)) := by    intro x y h    exact Subtype.ext h  let parent : Sym2 α → Finset α := fun e =>    Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x  let edges := (digraph_common_predecessor_graph D).edgeFinset  let repeated := edges.filter fun e => 2 ≤ (parent e).card  let dirty : Finset α := Finset.univ.filter fun u =>    ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b  let missing : Finset Arc := Finset.univ \ Finset.univ.image f  let nonrep : Finset Arc := Finset.univ.filter fun x => r (f x) ≠ x  let edge : Arc → Sym2 α := fun x => s(head x, head (r (f x)))  let charge : Sym2 α → Finset α := fun e => (nonrep.filter fun x => edge x = e).image tail  have hdata (x : Arc) : tail (r (f x)) = tail x ∧      choose (tail x) (head (r (f x))) = choose (tail x) (head x) := by    have h := hr x    have ht : tail (r (f x)) = tail x := htail _ _ h    have hc : choose (tail (r (f x))) (head (r (f x))) =        choose (tail x) (head x) := congrArg (fun z : Arc => z.val.1) h    rw [ht] at hc    exact ⟨ht,hc⟩  have hheads (x : Arc) (hx : r (f x) ≠ x) : head x ≠ head (r (f x)) := by    intro h    apply hx    apply Subtype.ext    exact Prod.ext (hdata x).1 h.symm  have hcharged (x : Arc) (hx : r (f x) ≠ x) : edge x ∈ repeated := by    have hd := hdata x    have ha : D.Adj (tail x) (head x) := x.property    have hb : D.Adj (tail x) (head (r (f x))) := by      have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property      rw [hd.1] at hp      exact hp    have hh := digraph_arc_choice_collision_repeated_pair α D choose hloop hchoice      (tail x) (head x) (head (r (f x))) (hheads x hx) ha hb hd.2.symm    exact Finset.mem_filter.mpr hh  have hcharge : missing.card ≤ ∑ e ∈ repeated, (charge e).card := by    have h := finite_endomap_collision_charge_identity Arc α α f r tail head repeated      hr htail hkey hcharged    change missing.card = ∑ e ∈ repeated, (charge e).card at h    exact h.le  have hdirty : dirty ⊆ repeated.biUnion parent := by    intro u hu    obtain ⟨_,a,b,p,hab,hpu,hua,hub,hpa,hpb⟩ := Finset.mem_filter.mp hu    have hh := digraph_two_common_parents_edge_multiplicity α D a b u p      hab hpu.symm hua hub hpa hpb    apply Finset.mem_biUnion.mpr    refine ⟨s(a,b), Finset.mem_filter.mpr hh, ?_⟩    apply Finset.mem_filter.mpr    refine ⟨Finset.mem_univ _, ?_⟩    intro x hx    rcases Sym2.mem_iff.mp hx with rfl | rfl    · exact hua    · exact hub  have hsubset : ∀ e ∈ repeated, charge e ⊆ parent e := by    intro e he u hu    obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu    have hxe : edge x = e := (Finset.mem_filter.mp hx).2    apply Finset.mem_filter.mpr    refine ⟨Finset.mem_univ _, ?_⟩    intro z hz    rw [← hxe] at hz    change z ∈ s(head x, head (r (f x))) at hz    rcases Sym2.mem_iff.mp hz with rfl | rfl    · exact x.property    · have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property      rw [(hdata x).1] at hp      exact hp  have hm : ∀ e ∈ repeated, 2 ≤ (parent e).card := by    intro e he    exact (Finset.mem_filter.mp he).2  have htwo : ∀ e ∈ repeated, (parent e).card = 2 → (charge e).card ≤ 1 := by    intro e he hm2    induction e using Sym2.ind with    | h a b =>      have hparentEq : parent s(a,b) =          Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by        ext p        simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and]        constructor        · intro h          exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩        · rintro ⟨ha,hb⟩ x hx          rcases Sym2.mem_iff.mp hx with rfl | rfl          · exact ha          · exact hb      rw [hparentEq] at hm2      have hlim := digraph_two_parent_collision_charge_card_le_one α D choose hloop hori hchoice a b hm2      have hsub : charge s(a,b) ⊆          Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by        intro u hu        obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu        have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2        have hd := hdata x        have ha : D.Adj (tail x) (head x) := x.property        have hb : D.Adj (tail x) (head (r (f x))) := by          have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property          rw [hd.1] at hp          exact hp        apply Finset.mem_filter.mpr        refine ⟨Finset.mem_univ _, ?_⟩        rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩        · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb,            by simpa [hxa,hxb] using hd.2.symm⟩        · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha,            by simpa [hxa,hxb] using hd.2⟩      have hh := Finset.card_le_card hsub      exact hh.trans hlim  have hshort : ∀ e ∈ repeated, (parent e).card < g → (charge e).card < (parent e).card := by    intro e he hs    induction e using Sym2.ind with    | h a b =>      have hparentEq : parent s(a,b) =          Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by        ext p        simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and]        constructor        · intro h          exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩        · rintro ⟨ha,hb⟩ x hx          rcases Sym2.mem_iff.mp hx with rfl | rfl          · exact ha          · exact hb      have hnonempty : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty := by        apply Finset.card_pos.mp        have h := hm s(a,b) he        rw [hparentEq] at h        omega      have hlt := digraph_short_parent_set_not_all_charged α D choose g a b hloop hchoice hgirth        hnonempty (by simpa [hparentEq] using hs)      have hsub : charge s(a,b) ⊆          Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by        intro u hu        obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu        have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2        have hd := hdata x        have ha : D.Adj (tail x) (head x) := x.property        have hb : D.Adj (tail x) (head (r (f x))) := by          have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property          rw [hd.1] at hp          exact hp        apply Finset.mem_filter.mpr        refine ⟨Finset.mem_univ _, ?_⟩        rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩        · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb,            by simpa [hxa,hxb] using hd.2.symm⟩        · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha,            by simpa [hxa,hxb] using hd.2⟩      have hsub' : charge s(a,b) ⊆          (Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b)).filter            (fun p => choose p a = choose p b) := by        intro p hp        have hh := Finset.mem_filter.mp (hsub hp)        exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hh.2.1, hh.2.2.1⟩, hh.2.2.2⟩      have hc := Finset.card_le_card hsub'      rw [hparentEq]      omega  have hparentPos : ∀ e ∈ edges, 1 ≤ (parent e).card := by    intro e he    induction e using Sym2.ind with    | h a b =>      rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he      obtain ⟨_,p,hpa,hpb⟩ := he      apply Finset.card_pos.mpr      refine ⟨p, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩      intro x hx      rcases Sym2.mem_iff.mp hx with rfl | rfl      · exact hpa      · exact hpb  have hsum : (∑ e ∈ repeated, ((parent e).card - 1)) =      (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - edges.card := by    have hall := digraph_common_predecessor_overlap_incidence_identity α D    have hs : (∑ e ∈ repeated, ((parent e).card - 1)) =        ∑ e ∈ edges, ((parent e).card - 1) := by      dsimp [repeated]      rw [Finset.sum_filter]      apply Finset.sum_congr rfl      intro e he      by_cases h : 2 ≤ (parent e).card      · simp [h]      · have hp := hparentPos e he        have hc : (parent e).card = 1 := by omega        simp [h,hc]    rw [hs]    exact hall  have hsum_parent : dirty.card ≤ ∑ e ∈ repeated, (parent e).card := by    exact (Finset.card_le_card hdirty).trans Finset.card_biUnion_le  have hedge : ∀ e ∈ repeated,      (g - 1) * ((parent e).card + (charge e).card) ≤        2 * g * ((parent e).card - 1) + (g + 1 - 2 * (parent e).card) := by    intro e he    exact girth_parent_charge_weight_bound g (parent e).card (charge e).card hg (hm e he)      (Finset.card_le_card (hsubset e he)) (hshort e he)  have hsumineq := Finset.sum_le_sum hedge  have hbudget : (g - 1) * ((∑ e ∈ repeated, (parent e).card) +      (∑ e ∈ repeated, (charge e).card)) ≤      2 * g * (∑ e ∈ repeated, ((parent e).card - 1)) +      (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) := by    simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq  have hcorrection : (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) =      digraph_common_predecessor_girth_correction α D g := by    simp only [digraph_common_predecessor_girth_correction, repeated, Finset.sum_filter]    apply Finset.sum_congr    · ext e      simp [edges]    · intro e he      simp [parent]  have hscaled := Nat.mul_le_mul_left (g - 1) (Nat.add_le_add hsum_parent hcharge)  change (g - 1) * (dirty.card + missing.card) ≤ _  rw [← hsum, ← hcorrection]  exact hscaled.trans hbudget
See it in the graphDiscuss this resultChallenge it