AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_arc_map_twice_missing_budget

theoremverified

In a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting predecessor arc map is at most three times the total repeated common-predecessor incidence count.

Statement

theorem digraph_oriented_arc_map_twice_missing_budget
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (choose : α → α → α)
    (hloop : ∀ u, ¬ D.Adj u u)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (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⟩
    2 * ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤
      3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
        (digraph_common_predecessor_graph D).edgeFinset.card)
Source
Collision accounting for the four-cycle campaign; experiment 13230.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
Used by 1

The proof, explained

The proof bounds the missing arcs of the predecessor arc map f by assigning collisions to edges of the common-predecessor graph G. Using a general endomap collision identity, the number of missing arcs equals the sum of charges over edges with at least two common predecessors. Since the digraph is oriented, edges with multiplicity 2 receive at most charge 1, allowing an abstract multiplicity budget lemma to bound the sum of charges by three-halves the excess incidence count.

  1. Adjacency in the common-predecessor graph of D is decidable. automation

    Unfolding the definition of the common-predecessor graph reduces decidability of adjacency to an existential quantifier over a finite type, which Lean resolves by typeclass synthesis.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The predecessor arc map f admits a retraction r such that f(r(f(x))) = f(x) for all arcs x.

    The map f sends each arc (u, v) to (choose(u, v), u). Using classical choice, r selects a preimage for any arc in the image of f, so f(r(f(x))) = f(x) holds by definition.

    lines 19–31

    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 map preserves tails under collision, and arcs are uniquely determined by their endpoints.

    The head of f(x) is the tail of x, so f(x) = f(y) implies tail(x) = tail(y). Since an arc is a pair of vertices satisfying the adjacency relation, injectivity of (tail, head) follows by subtype extensionality.

    lines 32–39

    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 combinatorial sets: common parents, repeated edges, collision arcs, and edge charges.

    For each pair e, parent(e) is the set of common predecessors of e, and repeated edges are those with at least two common predecessors. The non-representative arcs nonrep are collision witnesses x with r(f(x)) ≠ x, which charge the pair formed by their heads.

    lines 40–49

      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 any non-representative arc x, the charged pair is a repeated edge in the common-predecessor graph.

    The arcs x and r(f(x)) share the same tail and the same chosen common predecessor, but have distinct heads. By digraph_arc_choice_collision_repeated_pair, two outgoing arcs with the same chosen predecessor create a pair of targets with at least two common predecessors.

    lines 50–72

    uses Subtype.ext, Prod.ext, digraph_arc_choice_collision_repeated_pair

      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
  6. The number of missing arcs is bounded by the total charge of all repeated edges.

    The general collision charge identity finite_endomap_collision_charge_identity equates the number of non-image elements of f with the sum of charges over the repeated edges.

    lines 73–77

    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
  7. Vertices with two outgoing arcs to a pair of targets with another common parent are contained in the parent set of a repeated edge.

    Applying digraph_two_common_parents_edge_multiplicity shows that the target pair has at least two common parents, hence belongs to the repeated edges.

    lines 78–90

    uses digraph_two_common_parents_edge_multiplicity

      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
  8. For every repeated edge e, its charge is a subset of its common parents: charge(e) ⊆ parent(e).

    Any vertex in charge(e) is the tail of an arc x whose head and collided head form e. Since both are outgoing arcs from this tail, the tail is adjacent to both vertices of e, hence is a common parent.

    lines 91–104

      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
  9. Every repeated edge has at least two common parents, and if it has exactly two, its charge is at most 1.

    Repeated edges have at least two parents by definition. When an edge s(a, b) has exactly two common parents, any charged tail u must satisfy choose(u, a) = choose(u, b); by digraph_two_parent_collision_charge_card_le_one, orientation of D prevents both parents from doing so, limiting the charge to at most 1.

    lines 105–144

    uses digraph_two_parent_collision_charge_card_le_one, Finset.card_le_card

      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
  10. Every edge in the common-predecessor graph has at least one common parent.

    By definition of the common-predecessor graph, an edge between two vertices requires the existence of at least one common predecessor.

    lines 145–156

    uses SimpleGraph.mem_edgeFinset

      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
  11. The sum of parent excesses over repeated edges equals the total repeated incidence count. automation

    Edges with fewer than two parents have exactly one parent, contributing 0 to the sum of (card - 1). The sum over all edges then equals the out-degree pair sum minus the edge count by digraph_common_predecessor_overlap_incidence_identity.

    lines 157–172

    uses digraph_common_predecessor_overlap_incidence_identity

      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
  12. The charge and parent sums satisfy the budget inequality from oriented_overlap_multiplicity_budget.

    Since each repeated edge has multiplicity at least 2, charge at most multiplicity, and charge at most 1 when multiplicity is 2, oriented_overlap_multiplicity_budget applies to bound the sum of multiplicities and charges by 3 times the excess sum. Moreover, charge(e) ⊆ parent(e) gives the sum comparison.

    lines 173–179

    uses Finset.card_le_card, oriented_overlap_multiplicity_budget, Finset.sum_le_sum

      have hc : ∀ e ∈ repeated, (charge e).card ≤ (parent e).card := by
        intro e he
        exact Finset.card_le_card (hsubset e he)
      have hbudget := oriented_overlap_multiplicity_budget (Sym2 α) repeated
        (fun e => (parent e).card) (fun e => (charge e).card) hm hc htwo
      have hcomp : (∑ e ∈ repeated, (charge e).card) ≤ ∑ e ∈ repeated, (parent e).card := by
        exact Finset.sum_le_sum (fun e he => hc e he)
  13. Twice the number of missing arcs is at most three times the repeated incidence budget. automation

    Combining the charge bound on missing arcs with the budget inequality and the sum identity, linear arithmetic closes the goal.

    lines 180–182

      change 2 * missing.card ≤ _
      rw [← hsum]
      omega
Classical.choose_spec
The witness chosen by Classical.choose satisfies the underlying predicate.
congrArg
Equality of arguments implies equality of function values.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Prod.ext
Two pairs are equal if their first and second components are equal.
digraph_arc_choice_collision_repeated_pair
If two outgoing arcs from a vertex have the same chosen common predecessor, the pair of targets forms an edge with at least two common predecessors in the common-predecessor graph.
finite_endomap_collision_charge_identity
For any finite endomap, the number of missing elements in the image equals the sum of collision charges over a partition of the collision pairs.
digraph_two_common_parents_edge_multiplicity
Two vertices with common outgoing arcs to two targets certify that the pair of targets is an edge of the common-predecessor graph with at least two common predecessors.
digraph_two_parent_collision_charge_card_le_one
In an oriented digraph, if an edge has exactly two common predecessors, at most one of them can choose the same predecessor for both endpoints.
SimpleGraph.mem_edgeFinset
Every edge in the edge set of a simple graph belongs to the edge finset.
digraph_common_predecessor_overlap_incidence_identity
The sum of (number of common predecessors - 1) over all edges of the common-predecessor graph equals the sum of binomial coefficients of out-degrees minus the number of edges.
Finset.card_le_card
A subset has cardinality at most the cardinality of the superset.
oriented_overlap_multiplicity_budget
For any edge weights m and charges c with m ≥ 2, c ≤ m, and c ≤ 1 whenever m = 2, the sum of m and c is at most 3 times the sum of (m - 1).
Finset.sum_le_sum
A sum of smaller terms is at most the sum of larger terms.

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_graph_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_oriented_arc_map_twice_missing_budget    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (choose : α → α → α)    (hloop : ∀ u, ¬ D.Adj u u)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (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⟩    2 * ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤      3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -        (digraph_common_predecessor_graph D).edgeFinset.card) := 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 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 hc : ∀ e ∈ repeated, (charge e).card ≤ (parent e).card := by    intro e he    exact Finset.card_le_card (hsubset e he)  have hbudget := oriented_overlap_multiplicity_budget (Sym2 α) repeated    (fun e => (parent e).card) (fun e => (charge e).card) hm hc htwo  have hcomp : (∑ e ∈ repeated, (charge e).card) ≤ ∑ e ∈ repeated, (parent e).card := by    exact Finset.sum_le_sum (fun e he => hc e he)  change 2 * missing.card ≤ _  rw [← hsum]  omega
See it in the graphDiscuss this resultChallenge it