digraph_trianglefree_arc_map_weighted_budget
For a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of dirty parents plus missing arc-map images is at most eight times repeated common-predecessor incidences plus the number of pairs with exactly two common predecessors.
Statement
theorem digraph_trianglefree_arc_map_weighted_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (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 → 4 ≤ 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 3 * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤ 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_double_edges α D
- Source
- Triangle-free center budget for the four-cycle campaign; experiments 13471 and 13473.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- 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_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_double_edgesThe number of edges in the common-predecessor graph whose endpoints have exactly two common predecessors.
- trianglefree_parent_charge_weight_boundIf a charged subset of m parents is proper whenever m is less than four, then three times parents plus charges is bounded by eight times…
- digraph_short_parent_set_not_all_chargedIn a loopless digraph of directed girth at least g, a nonempty common-predecessor set with fewer than g members cannot have every parent…
- 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_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
- finite_endomap_missing_image_eq_nonrepresentativesFor a finite endomap with a chosen representative from each nonempty fiber, the number of elements outside its image equals the number of…
- finite_function_collision_head_pair_injectiveGiven an injective tail-head encoding and a map whose fibers have a fixed tail, encoding each nonrepresentative by its tail and the…
- finite_endomap_collision_charge_identityFor a finite endomap whose fibers share a tail and whose elements are determined by tail and head, the number of missing image elements is…
- digraph_oriented_two_parent_collision_limitIn an oriented loopless digraph, if two vertices are dominated by both members of a displayed pair and have no common predecessor outside…
- 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.
- digraph_arc_choice_collision_repeated_pairWhen two outgoing arcs of a loopless digraph receive the same chosen common predecessor, their distinct heads form an auxiliary edge with…
- digraph_two_parent_collision_charge_card_le_oneIn a loopless oriented digraph with a chosen common predecessor for every arc, if two vertices have exactly two common predecessors, at…
- finite_parent_collision_budget_with_coverUnder the same repeated-pair parent and charge assumptions, any dirty set covered by the parent sets and any missing set no larger than…
- oriented_overlap_multiplicity_budgetSummed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.
- Used by 2
- digraph_trianglefree_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- digraph_trianglefree_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
The proof, explained
The proof charges missing arcs under f to repeated common-predecessor pairs and bounds dirty parents and collision charges edge by edge.
Decidability of adjacency in the common predecessor graph
Unfolding the definition of the common predecessor graph, adjacency between two vertices is a decidable proposition by typeclass inference.
intro u v unfold digraph_common_predecessor_graph infer_instance
Final budget inequality
Combine all inequalities.
classical let g : ℕ := 4 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, 3 * ((parent e).card + (charge e).card) ≤ 8 * ((parent e).card - 1) + (if (parent e).card = 2 then 1 else 0) := by intro e he exact trianglefree_parent_charge_weight_bound (parent e).card (charge e).card (hm e he) (Finset.card_le_card (hsubset e he)) (hshort e he) have hsumineq := Finset.sum_le_sum hedge have hbudget : 3 * ((∑ e ∈ repeated, (parent e).card) + (∑ e ∈ repeated, (charge e).card)) ≤ 8 * (∑ e ∈ repeated, ((parent e).card - 1)) + (∑ e ∈ repeated, if (parent e).card = 2 then 1 else 0) := by simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq have hdoubles : (∑ e ∈ repeated, if (parent e).card = 2 then 1 else 0) = digraph_common_predecessor_double_edges α D := by rw [Finset.sum_boole] have heq : repeated.filter (fun e => (parent e).card = 2) = edges.filter (fun e => (parent e).card = 2) := by ext e simp only [repeated, Finset.mem_filter] constructor · rintro ⟨⟨he, _⟩, hm2⟩ exact ⟨he, hm2⟩ · rintro ⟨he, hm2⟩ exact ⟨⟨he, by omega⟩, hm2⟩ rw [heq] unfold digraph_common_predecessor_double_edges apply congrArg Finset.card ext e simp [edges, parent] change 3 * (dirty.card + missing.card) ≤ _ rw [← hsum, ← hdoubles] omega
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 in516_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_trianglefree_arc_map_weighted_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (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 → 4 ≤ 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 3 * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤ 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_double_edges α D := by classical let g : ℕ := 4 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, 3 * ((parent e).card + (charge e).card) ≤ 8 * ((parent e).card - 1) + (if (parent e).card = 2 then 1 else 0) := by intro e he exact trianglefree_parent_charge_weight_bound (parent e).card (charge e).card (hm e he) (Finset.card_le_card (hsubset e he)) (hshort e he) have hsumineq := Finset.sum_le_sum hedge have hbudget : 3 * ((∑ e ∈ repeated, (parent e).card) + (∑ e ∈ repeated, (charge e).card)) ≤ 8 * (∑ e ∈ repeated, ((parent e).card - 1)) + (∑ e ∈ repeated, if (parent e).card = 2 then 1 else 0) := by simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq have hdoubles : (∑ e ∈ repeated, if (parent e).card = 2 then 1 else 0) = digraph_common_predecessor_double_edges α D := by rw [Finset.sum_boole] have heq : repeated.filter (fun e => (parent e).card = 2) = edges.filter (fun e => (parent e).card = 2) := by ext e simp only [repeated, Finset.mem_filter] constructor · rintro ⟨⟨he, _⟩, hm2⟩ exact ⟨he, hm2⟩ · rintro ⟨he, hm2⟩ exact ⟨⟨he, by omega⟩, hm2⟩ rw [heq] unfold digraph_common_predecessor_double_edges apply congrArg Finset.card ext e simp [edges, parent] change 3 * (dirty.card + missing.card) ≤ _ rw [← hsum, ← hdoubles] omega