AFTD Auto-Formalizing Theoretical Domains

graph_idle_transport_plan_special

theoremverified

If the edge partition has |A| = |B| ≥ 1, deg x = deg y, |B| = |C|+2 and an A–B edge, then μ_x^{1/2} and μ_y^{1/2} admit a plan of cost at most 1/2 + 2(|A|−1)(1/2)/d_y.

Statement

theorem graph_idle_transport_plan_special {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)
    (hdiam : G.ediam ≤ 2) (A B C P : Finset V)
    (hAmem : ∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y))
    (hBmem : ∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x))
    (hCmem : ∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v))
    (hPmem : ∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v))
    (hcover : (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P)
    (hdx : G.degree x = A.card + C.card + 1)
    (hdy : G.degree y = B.card + C.card + 1)
    (hAB : A.card = B.card) (hne : 1 ≤ A.card)
    (hadj : ∃ v ∈ A, ∃ u ∈ B, G.Adj v u) :
    ∃ π : V → V → ℝ, (∀ u v, 0 ≤ π u v) ∧
      (∀ u, ∑ v, π u v = graph_idle_measure G (1/2) x u) ∧
      (∀ v, ∑ u, π u v = graph_idle_measure G (1/2) y v) ∧
      (∑ u, ∑ v, (G.dist u v : ℝ) * π u v) ≤
        1/2 + 2*((A.card : ℝ) - 1)*((1/2)/(G.degree y : ℝ))
Source
step towards exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • graph_dist_le_two_of_ediam_le_twoIf the extended diameter of a graph is at most 2, then every (natural-valued) distance is at most 2.
  • graph_edge_partition_cardWith the four-part partition of V induced by an edge xy: deg x = |A| + |C| + 1, deg y = |B| + |C| + 1, and |V| = 2 + |A| + |B| + |C| + |P|.
  • graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
Used by 2

The proof, explained

The proof constructs an explicit transport plan π between the lazy random walk distributions μ_x^{1/2} and μ_y^{1/2}. Using an assumed edge (v0, u0) with v0 ∈ A and u0 ∈ B, π places mass γ = (1/2)/d_y on diagonal points (x, x), (y, y), and (c, c) for c ∈ C; mass 1/2 - γ on (x, y); mass γ on the edge (v0, u0); and couples the rest of A and B uniformly with total mass γ. The marginals match because |A| = |B| and deg x = deg y, and the total cost is at most 1/2 + 2(|A|-1)γ because diagonal points have distance 0, adjacent pairs have distance 1, and all other coupled pairs have distance at most 2 by the diameter bound.

  1. Choose an edge (v0, u0) between A and B and define the transport plan π.

    By assumption, there exists an edge connecting A and B; let v0 ∈ A and u0 ∈ B be such an adjacent pair. Setting γ = (1/2) / d_y, define π by assigning mass γ to (x, x), (y, y), each (u, u) for u ∈ C, and the edge (v0, u0); mass 1/2 - γ to (x, y); and distributing γ uniformly across (A \ {v0}) × (B \ {u0}) with density γ / (|A| - 1). All other pairs are assigned mass 0.

    lines 19–28

      rcases hadj with ⟨v0, hv0, u0, hu0, hadj0⟩
      let γ := (1/2)/(G.degree y : ℝ)
      let π : V → V → ℝ := fun u v =>
        (if u = x ∧ v = x then γ else 0) +
        (if u = x ∧ v = y then 1/2 - γ else 0) +
        (if u = y ∧ v = y then γ else 0) +
        (if u = v ∧ u ∈ C then γ else 0) +
        (if u = v0 ∧ v = u0 then γ else 0) +
        (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0)
      refine ⟨π, ?_, ?_, ?_, ?_⟩
  2. The transport plan π is non-negative everywhere: π(u, v) ≥ 0 for all u, v.

    Because x and y are adjacent, d_y ≥ 1, which implies γ = (1/2)/d_y is positive and at most 1/2. Hence 1/2 - γ ≥ 0. Since |A| ≥ 1, the denominator |A| - 1 is non-negative. Each of the six additive terms defining π(u, v) is non-negative, so their sum is non-negative.

    lines 29–55

    uses SimpleGraph.degree_pos_iff_exists_adj, div_nonneg, div_le_iff₀, add_nonneg

      · intro u v
        have hdypos : (0:ℝ) < (G.degree y : ℝ) := by
          have : 0 < G.degree y := by
            rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨x, hxy.symm⟩
          exact_mod_cast this
        have hγnn : (0:ℝ) ≤ γ := div_nonneg (by norm_num) (by positivity)
        have hγle : γ ≤ 1/2 := by
          dsimp [γ]
          rw [div_le_iff₀ hdypos]
          have h1 : (1:ℝ) ≤ (G.degree y : ℝ) := by
            have : 0 < G.degree y := by
              rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨x, hxy.symm⟩
            exact_mod_cast this
          linarith
        have hAdenom : (0:ℝ) ≤ (A.card : ℝ) - 1 := by
          have : (1:ℝ) ≤ (A.card : ℝ) := by exact_mod_cast hne
          linarith
        dsimp [π]
        repeat' apply add_nonneg
        · split_ifs; exact hγnn; rfl
        · split_ifs; linarith; rfl
        · split_ifs; exact hγnn; rfl
        · split_ifs; exact hγnn; rfl
        · split_ifs; exact hγnn; rfl
        · split_ifs
          · exact div_nonneg hγnn hAdenom
          · rfl
  3. The first marginal of π matches the idle random walk measure μ_x^{1/2}.

    Summing π(u, v) over v, the terms evaluate to: γ at u = x (from v = x); 1/2 - γ at u = x (from v = y); γ at u = y (from v = y); γ for u ∈ C (from v = u); γ at u = v0 (from v = u0); and (|B| - 1) * (γ / (|A| - 1)) = γ for u ∈ A \ {v0} because |A| = |B|. At u = x, γ + (1/2 - γ) = 1/2. For any neighbor of x (namely y, A, and C), the sum is γ = (1/2) / d_y = (1/2) / d_x, since d_x = d_y. For all other vertices, the sum is 0. This matches μ_x^{1/2}(u) across the partition {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P.

    lines 56–170

    uses Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, Finset.sum_congr, Finset.mem_sdiff, Finset.card_le_card, Finset.card_pair, Nat.one_lt_cast.mpr, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem, mul_div_cancel₀, Finset.sum_add_distrib, add_assoc

      · intro u
        have hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by
          intro w
          have h : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w
          rw [hcover] at h
          simp only [Finset.mem_union, Finset.mem_singleton] at h
          tauto
        have e1 : (∑ v, if u = x ∧ v = x then γ else (0:ℝ)) = if u = x then γ else 0 := by
          by_cases h : u = x <;> simp [h]
        have e2 : (∑ v, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = if u = x then 1/2 - γ else 0 := by
          by_cases h : u = x <;> simp [h]
        have e3 : (∑ v, if u = y ∧ v = y then γ else (0:ℝ)) = if u = y then γ else 0 := by
          by_cases h : u = y <;> simp [h]
        have e4 : (∑ v, if u = v ∧ u ∈ C then γ else (0:ℝ)) = if u ∈ C then γ else 0 := by
          have : (∑ v, if u = v ∧ u ∈ C then γ else (0:ℝ)) = ∑ v, if v = u then (if u ∈ C then γ else 0) else 0 := by
            apply Finset.sum_congr rfl; intro v _; by_cases h : u = v <;> simp [h, eq_comm]
          rw [this]; simp
        have e5 : (∑ v, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = if u = v0 then γ else 0 := by
          by_cases h : u = v0 <;> simp [h]
        have e6 : (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =
            if u ∈ A \ {v0} then γ else 0 := by
          by_cases hu : u ∈ A \ {v0}
          · simp only [hu, true_and, if_true]
            have huA : u ∈ A := Finset.mem_sdiff.mp hu |>.1
            have hne' : u ≠ v0 := by
              have := Finset.mem_sdiff.mp hu |>.2
              simp only [Finset.mem_singleton] at this
              exact this
            have hA2 : 2 ≤ A.card := by
              have : {u, v0} ⊆ A := by
                intro w hw
                simp only [Finset.mem_insert, Finset.mem_singleton] at hw
                rcases hw with rfl | rfl <;> assumption
              have hle := Finset.card_le_card this
              rw [Finset.card_pair hne'] at hle
              exact hle
            have hdenom : (A.card : ℝ) - 1 ≠ 0 := by
              have : 1 < A.card := hA2
              have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this
              linarith
            have hsum : (∑ v, (if v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =
                ∑ v ∈ B \ {u0}, (γ / ((A.card : ℝ) - 1)) := by
              rw [← Finset.sum_filter]; congr 1; ext v; simp
            rw [hsum]
            simp only [Finset.sum_const, nsmul_eq_mul]
            rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hu0, ← hAB]
            exact mul_div_cancel₀ γ hdenom
          · simp [hu]
        have e56 : (if u = v0 then γ else 0) + (if u ∈ A \ {v0} then γ else 0) =
            if u ∈ A then γ else 0 := by
          by_cases huA : u ∈ A
          · by_cases huv0 : u = v0
            · subst huv0; simp [Finset.mem_sdiff, huA]
            · have : u ∈ A \ {v0} := by
                rw [Finset.mem_sdiff, Finset.mem_singleton]
                exact ⟨huA, huv0⟩
              simp [huv0, this, huA]
          · have h1 : u ≠ v0 := by rintro rfl; exact huA hv0
            have h2 : u ∉ A \ {v0} := fun h => huA (Finset.mem_sdiff.mp h |>.1)
            simp [huA, h1, h2]
        dsimp [π]
        simp only [Finset.sum_add_distrib]
        change (∑ v, if u = x ∧ v = x then γ else 0) +
          (∑ v, if u = x ∧ v = y then 1/2 - γ else 0) +
          (∑ v, if u = y ∧ v = y then γ else 0) +
          (∑ v, if u = v ∧ u ∈ C then γ else 0) +
          (∑ v, if u = v0 ∧ v = u0 then γ else 0) +
          (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) = _
        rw [e1, e2, e3, e4, e5, e6]
        rw [add_assoc ((((if u = x then γ else 0) + if u = x then 1 / 2 - γ else 0) +
              if u = y then γ else 0) + if u ∈ C then γ else 0)]
        rw [e56]
        have hdeg : G.degree x = G.degree y := by rw [hdx, hdy, hAB]
        simp only [graph_idle_measure]
        rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]
        dsimp [γ]
        rw [hdeg]
        have hxC : x ∉ C := by rw [hCmem]; simp
        have hxA : x ∉ A := by rw [hAmem]; simp
        have hyC : y ∉ C := by rw [hCmem]; simp
        have hyA : y ∉ A := by rw [hAmem]; simp
        rcases hu_cases u with hux | huy | huA | huB | huC | huP
        · rw [hux]; simp [hxy.ne, hxC, hxA]
        · rw [huy]; simp [hxy.ne.symm, hyC, hyA, hxy]
        · have hm := (hAmem u).mp huA
          have huAx : G.Adj x u := hm.1
          have huAny : ¬ G.Adj y u := hm.2.1
          have huy : u ≠ y := hm.2.2
          have hux : u ≠ x := by rintro rfl; exact G.irrefl hm.1
          have huC : u ∉ C := by rw [hCmem]; exact fun h => huAny h.2
          simp [hux, huy, huC, huA, huAx]
        · have hm := (hBmem u).mp huB
          have huBy : G.Adj y u := hm.1
          have huBnx : ¬ G.Adj x u := hm.2.1
          have hux : u ≠ x := hm.2.2
          have huy : u ≠ y := by rintro rfl; exact G.irrefl huBy
          have huA : u ∉ A := by rw [hAmem]; exact fun h => huBnx h.1
          have huC : u ∉ C := by rw [hCmem]; exact fun h => huBnx h.1
          simp [hux, huy, huC, huA, huBnx]
        · have hm := (hCmem u).mp huC
          have huCx : G.Adj x u := hm.1
          have huCy : G.Adj y u := hm.2
          have hux : u ≠ x := by rintro rfl; exact G.irrefl huCx
          have huy : u ≠ y := by rintro rfl; exact G.irrefl huCy
          have huA : u ∉ A := by rw [hAmem]; exact fun h => h.2.1 huCy
          simp [hux, huy, huC, huA, huCx]
        · have hm := (hPmem u).mp huP
          have huPx : ¬ G.Adj x u := hm.1
          have huPy : ¬ G.Adj y u := hm.2
          have hux : u ≠ x := by rintro rfl; exact huPy hxy.symm
          have huy : u ≠ y := by rintro rfl; exact huPx hxy
          have huA : u ∉ A := by rw [hAmem]; exact fun h => huPx h.1
          have huC : u ∉ C := by rw [hCmem]; exact fun h => huPx h.1
          simp [hux, huy, huC, huA, huPx]
      · intro v
  4. The second marginal of π matches the idle random walk measure μ_y^{1/2}.

    Symmetrically, summing π(u, v) over u for fixed v: at v = y, the pair (x, y) gives 1/2 - γ and (y, y) gives γ, summing to 1/2. At v = x, the pair (x, x) gives γ. For v ∈ C, the diagonal gives γ. For v = u0, (v0, u0) gives γ, and summing over u ∈ A \ {v0} gives (|A| - 1) * (γ / (|A| - 1)) = γ for every v ∈ B \ {u0}. Thus every neighbor of y (namely x, B, and C) receives total mass γ = (1/2)/d_y, while vertices outside N[y] receive 0, matching μ_y^{1/2}(v).

    lines 171–285

    uses Finset.mem_univ, Finset.mem_union, Finset.mem_singleton, Finset.sum_congr, Finset.card_le_card, Finset.card_pair, Nat.one_lt_cast.mpr, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem, mul_div_cancel₀, Finset.mem_sdiff, Finset.sum_add_distrib, add_assoc

        have hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by
          intro w
          have h : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w
          rw [hcover] at h
          simp only [Finset.mem_union, Finset.mem_singleton] at h
          tauto
        have c1 : (∑ u, if u = x ∧ v = x then γ else (0:ℝ)) = if v = x then γ else 0 := by
          by_cases h : v = x <;> simp [h]
        have c2 : (∑ u, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = if v = y then 1/2 - γ else 0 := by
          by_cases h : v = y <;> simp [h]
        have c3 : (∑ u, if u = y ∧ v = y then γ else (0:ℝ)) = if v = y then γ else 0 := by
          by_cases h : v = y <;> simp [h]
        have c4 : (∑ u, if u = v ∧ u ∈ C then γ else (0:ℝ)) = if v ∈ C then γ else 0 := by
          have : (∑ u, if u = v ∧ u ∈ C then γ else (0:ℝ)) = ∑ u, if u = v then (if v ∈ C then γ else 0) else 0 := by
            apply Finset.sum_congr rfl; intro u _; by_cases h : u = v <;> simp [h]
          rw [this]; simp
        have c5 : (∑ u, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = if v = u0 then γ else 0 := by
          by_cases h : v = u0 <;> simp [h]
        have c6 : (∑ u, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =
            if v ∈ B \ {u0} then γ else 0 := by
          by_cases hv : v ∈ B \ {u0}
          · simp only [hv, and_true, if_true]
            have huB : v ∈ B := Finset.mem_sdiff.mp hv |>.1
            have hne' : v ≠ u0 := by
              have := Finset.mem_sdiff.mp hv |>.2
              simp only [Finset.mem_singleton] at this
              exact this
            have hB2 : 2 ≤ B.card := by
              have : {v, u0} ⊆ B := by
                intro w hw
                simp only [Finset.mem_insert, Finset.mem_singleton] at hw
                rcases hw with rfl | rfl <;> assumption
              have hle := Finset.card_le_card this
              rw [Finset.card_pair hne'] at hle
              exact hle
            have hdenom : (A.card : ℝ) - 1 ≠ 0 := by
              have : 1 < A.card := by rw [hAB]; exact hB2
              have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this
              linarith
            have hsum : (∑ u, (if u ∈ A \ {v0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =
                ∑ u ∈ A \ {v0}, (γ / ((A.card : ℝ) - 1)) := by
              rw [← Finset.sum_filter]; congr 1; ext u; simp
            rw [hsum]
            simp only [Finset.sum_const, nsmul_eq_mul]
            rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hv0]
            exact mul_div_cancel₀ γ hdenom
          · simp [hv]
        have c23 : (if v = y then 1/2 - γ else 0) + (if v = y then γ else 0) =
            if v = y then 1/2 else 0 := by
          by_cases h : v = y <;> simp [h]
        have c56 : (if v = u0 then γ else 0) + (if v ∈ B \ {u0} then γ else 0) =
            if v ∈ B then γ else 0 := by
          by_cases hvB : v ∈ B
          · by_cases hvu0 : v = u0
            · subst hvu0; simp [Finset.mem_sdiff, hvB]
            · have : v ∈ B \ {u0} := by
                rw [Finset.mem_sdiff, Finset.mem_singleton]
                exact ⟨hvB, hvu0⟩
              simp [hvu0, this, hvB]
          · have h1 : v ≠ u0 := by rintro rfl; exact hvB hu0
            have h2 : v ∉ B \ {u0} := fun h => hvB (Finset.mem_sdiff.mp h |>.1)
            simp [hvB, h1, h2]
        dsimp [π]
        simp only [Finset.sum_add_distrib]
        change (∑ u, if u = x ∧ v = x then γ else 0) +
          (∑ u, if u = x ∧ v = y then 1/2 - γ else 0) +
          (∑ u, if u = y ∧ v = y then γ else 0) +
          (∑ u, if u = v ∧ u ∈ C then γ else 0) +
          (∑ u, if u = v0 ∧ v = u0 then γ else 0) +
          (∑ u, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) = _
        rw [c1, c2, c3, c4, c5, c6]
        rw [add_assoc (if v = x then γ else 0)]
        rw [c23]
        rw [add_assoc ((if v = x then γ else 0) + (if v = y then 1 / 2 else 0) + (if v ∈ C then γ else 0))]
        rw [c56]
        simp only [graph_idle_measure]
        rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]
        dsimp [γ]
        have hxB : x ∉ B := by rw [hBmem]; simp
        have hxC : x ∉ C := by rw [hCmem]; simp
        have hyB : y ∉ B := by rw [hBmem]; simp
        have hyC : y ∉ C := by rw [hCmem]; simp
        rcases hu_cases v with hvx | hvy | hvA | hvB | hvC | hvP
        · rw [hvx]; simp [hxy.ne, hxy.symm, hxB, hxC]
        · rw [hvy]; simp [hxy.ne.symm, hyB, hyC]
        · have hm := (hAmem v).mp hvA
          have hvAx : G.Adj x v := hm.1
          have hvAny : ¬ G.Adj y v := hm.2.1
          have hvy : v ≠ y := hm.2.2
          have hvx : v ≠ x := by rintro rfl; exact G.irrefl hm.1
          have hvB : v ∉ B := by rw [hBmem]; exact fun h => hvAny h.1
          have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvAny h.2
          simp [hvx, hvy, hvB, hvC, hvAny]
        · have hm := (hBmem v).mp hvB
          have hvBy : G.Adj y v := hm.1
          have hvBnx : ¬ G.Adj x v := hm.2.1
          have hvx : v ≠ x := hm.2.2
          have hvy : v ≠ y := by rintro rfl; exact G.irrefl hvBy
          have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvBnx h.1
          simp [hvx, hvy, hvC, hvB, hvBy]
        · have hm := (hCmem v).mp hvC
          have hvCx : G.Adj x v := hm.1
          have hvCy : G.Adj y v := hm.2
          have hvx : v ≠ x := by rintro rfl; exact G.irrefl hvCx
          have hvy : v ≠ y := by rintro rfl; exact G.irrefl hvCy
          have hvB : v ∉ B := by rw [hBmem]; exact fun h => h.2.1 hvCx
          simp [hvx, hvy, hvC, hvB, hvCy]
        · have hm := (hPmem v).mp hvP
          have hvPx : ¬ G.Adj x v := hm.1
          have hvPy : ¬ G.Adj y v := hm.2
          have hvx : v ≠ x := by rintro rfl; exact hvPy hxy.symm
          have hvy : v ≠ y := by rintro rfl; exact hvPx hxy
          have hvB : v ∉ B := by rw [hBmem]; exact fun h => hvPy h.1
          have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvPx h.1
          simp [hvx, hvy, hvC, hvB, hvPy]
  5. The pointwise transport cost dist(u, v) * π(u, v) is bounded by (1/2 - γ) 1_{u=x, v=y} + γ 1_{u=v0, v=u0} + 2 * (γ / (|A| - 1)) 1_{u ∈ A\{v0}, v ∈ B\{u0}}.

    For pairs with u = v (the pairs (x, x), (y, y), and (c, c) for c ∈ C), dist(u, v) = 0 so the cost is 0. For (x, y) and (v0, u0), the vertices are adjacent, so dist(u, v) = 1, contributing 1/2 - γ and γ respectively. For any remaining pair in (A \ {v0}) × (B \ {u0}), the diameter bound ediam ≤ 2 guarantees dist(u, v) ≤ 2, so the cost is bounded by 2 times the allocated mass.

    lines 286–331

    uses graph_dist_le_two_of_ediam_le_two, div_nonneg, SimpleGraph.dist_eq_one_iff_adj.mpr, mul_le_mul_of_nonneg_right

      · have hdist2 (u v : V) : (G.dist u v : ℝ) ≤ 2 := by
          exact_mod_cast graph_dist_le_two_of_ediam_le_two G hdiam u v
        have hAdenom : (0:ℝ) ≤ (A.card : ℝ) - 1 := by
          have : (1:ℝ) ≤ (A.card : ℝ) := by exact_mod_cast hne
          linarith
        have hγnn : (0:ℝ) ≤ γ := div_nonneg (by norm_num) (by positivity)
        have hT6nn (u v : V) : (0:ℝ) ≤ (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) := by
          split_ifs; exact div_nonneg hγnn hAdenom; rfl
    
        have hle_pointwise (u v : V) :
            (G.dist u v : ℝ) * π u v ≤
              (if u = x ∧ v = y then 1/2 - γ else 0) +
              (if u = v0 ∧ v = u0 then γ else 0) +
              2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) := by
          have hd1 : (G.dist u v : ℝ) * (if u = x ∧ v = x then γ else 0) = 0 := by
            by_cases h : u = x ∧ v = x
            · rw [h.1, h.2]; simp
            · simp [h]
          have hd2 : (G.dist u v : ℝ) * (if u = x ∧ v = y then 1/2 - γ else 0) =
              (if u = x ∧ v = y then 1/2 - γ else 0) := by
            by_cases h : u = x ∧ v = y
            · rw [h.1, h.2]
              have hd : (G.dist x y : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hxy]
              simp [hd]
            · simp [h]
          have hd3 : (G.dist u v : ℝ) * (if u = y ∧ v = y then γ else 0) = 0 := by
            by_cases h : u = y ∧ v = y
            · rw [h.1, h.2]; simp
            · simp [h]
          have hd4 : (G.dist u v : ℝ) * (if u = v ∧ u ∈ C then γ else 0) = 0 := by
            by_cases h : u = v ∧ u ∈ C
            · rw [h.1]; simp
            · simp [h]
          have hd5 : (G.dist u v : ℝ) * (if u = v0 ∧ v = u0 then γ else 0) =
              (if u = v0 ∧ v = u0 then γ else 0) := by
            by_cases h : u = v0 ∧ v = u0
            · rw [h.1, h.2]
              have hd : (G.dist v0 u0 : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hadj0]
              simp [hd]
            · simp [h]
          have hd6 : (G.dist u v : ℝ) * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) ≤
              2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) :=
            mul_le_mul_of_nonneg_right (hdist2 u v) (hT6nn u v)
          dsimp [π]
          linarith
    
  6. The total transport cost is at most 1/2 + 2(|A| - 1) * ((1/2)/d_y).

    Summing the pointwise upper bounds over all u and v, the term for (x, y) contributes 1/2 - γ, and the term for (v0, u0) contributes γ. The remaining coupling over (A \ {v0}) × (B \ {u0}) contains (|A| - 1) * (|B| - 1) pairs, each weighted by 2 * γ / (|A| - 1); since |A| = |B|, this sums to 2(|A| - 1)γ. The total cost is (1/2 - γ) + γ + 2(|A| - 1)γ = 1/2 + 2(|A| - 1)γ, as claimed.

    lines 332–390

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.mul_sum, Finset.mem_singleton, Finset.mem_insert, Finset.card_le_card, Finset.card_pair, Nat.one_lt_cast.mpr, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem, mul_div_cancel₀

        have hsum_le : (∑ u, ∑ v, (G.dist u v : ℝ) * π u v) ≤
            ∑ u, ∑ v, ((if u = x ∧ v = y then 1/2 - γ else 0) +
              (if u = v0 ∧ v = u0 then γ else 0) +
              2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0)) :=
          Finset.sum_le_sum fun u _ => Finset.sum_le_sum fun v _ => hle_pointwise u v
        apply hsum_le.trans
        simp_rw [Finset.sum_add_distrib]
        have hsum1 : (∑ u, ∑ v, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = 1/2 - γ := by
          have h (u v : V) : (if u = x ∧ v = y then 1/2 - γ else (0 : ℝ)) =
              (if u = x then if v = y then 1/2 - γ else 0 else 0) := by
            split_ifs <;> tauto
          simp_rw [h]; simp
        have hsum2 : (∑ u, ∑ v, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = γ := by
          have h (u v : V) : (if u = v0 ∧ v = u0 then γ else (0 : ℝ)) =
              (if u = v0 then if v = u0 then γ else 0 else 0) := by
            split_ifs <;> tauto
          simp_rw [h]; simp
        have hsum3 : (∑ u, ∑ v, 2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ))) =
            2 * ((A.card : ℝ) - 1) * γ := by
          simp_rw [← Finset.mul_sum]
          have hstep (u : V) : (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =
              if u ∈ A \ {v0} then γ else 0 := by
            by_cases hu : u ∈ A \ {v0}
            · simp only [hu, true_and, if_true]
              have huA : u ∈ A := Finset.mem_sdiff.mp hu |>.1
              have hne' : u ≠ v0 := by
                have := Finset.mem_sdiff.mp hu |>.2
                simp only [Finset.mem_singleton] at this
                exact this
              have hA2 : 2 ≤ A.card := by
                have : {u, v0} ⊆ A := by
                  intro w hw
                  simp only [Finset.mem_insert, Finset.mem_singleton] at hw
                  rcases hw with rfl | rfl <;> assumption
                have hle := Finset.card_le_card this
                rw [Finset.card_pair hne'] at hle
                exact hle
              have hdenom : (A.card : ℝ) - 1 ≠ 0 := by
                have : 1 < A.card := hA2
                have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this
                linarith
              have hsum : (∑ v, (if v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =
                  ∑ v ∈ B \ {u0}, (γ / ((A.card : ℝ) - 1)) := by
                rw [← Finset.sum_filter]; congr 1; ext v; simp
              rw [hsum]
              simp only [Finset.sum_const, nsmul_eq_mul]
              rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hu0, ← hAB]
              exact mul_div_cancel₀ γ hdenom
            · simp [hu]
          simp_rw [hstep]
          have hsum : (∑ u, if u ∈ A \ {v0} then γ else (0 : ℝ)) = ∑ u ∈ A \ {v0}, γ := by
            rw [← Finset.sum_filter]; congr 1; ext u; simp
          rw [hsum]
          simp only [Finset.sum_const, nsmul_eq_mul]
          rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hv0]
          ring
        rw [hsum1, hsum2, hsum3]
        dsimp [γ]
        linarith
add_nonneg
The sum of two non-negative elements is non-negative.
add_assoc
Addition is associative: (a + b) + c = a + (b + c).
div_le_iff₀
For a positive denominator c > 0, b / c ≤ a if and only if b ≤ a * c.
div_nonneg
The quotient of two non-negative numbers is non-negative.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.card_pair
If a ≠ b, the cardinality of the pair {a, b} is 2.
Finset.cast_card_erase_of_mem
Erasing an element from a finite set decreases its cardinality by 1.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or is in s.
Finset.mem_sdiff
An element belongs to s \ t if and only if it is in s and not in t.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.mem_union
An element belongs to s ∪ t if and only if it is in s or in t.
Finset.mem_univ
Every element belongs to the universal finite set univ.
Finset.mul_sum
Factoring out a constant from a finite sum: a * ∑ i, f i = ∑ i, a * f i.
Finset.sdiff_singleton_eq_erase
Removing a singleton set {a} from s is equal to erasing a from s.
Finset.sum_add_distrib
Distributivity of sum over addition: ∑ (f + g) = ∑ f + ∑ g.
Finset.sum_congr
Two finite sums are equal if their domains and summands agree.
Finset.sum_const
The sum of a constant b over a finite set s equals |s| • b.
Finset.sum_filter
Summing over a filtered set equals summing the conditional indicator over the whole set.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements of a finite set, then ∑ f(i) ≤ ∑ g(i).
graph_dist_le_two_of_ediam_le_two
If the extended diameter of G is at most 2, the distance between any two vertices is at most 2.
mul_div_cancel₀
For b ≠ 0, b * (a / b) = a.
mul_le_mul_of_nonneg_right
Multiplying an inequality b ≤ c by a non-negative number on the right preserves the inequality.
Nat.one_lt_cast.mpr
If 1 < n for natural numbers, then 1 < (n : ℝ).
nsmul_eq_mul
Natural number scalar multiplication n • a equals (n : ℝ) * a.
SimpleGraph.degree_pos_iff_exists_adj
A vertex has positive degree if and only if it has an adjacent neighbour.
SimpleGraph.dist_eq_one_iff_adj.mpr
If two vertices are adjacent in a graph, their graph distance is 1.

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

Lean’s trace was cut to the first 400 of 506 tactics.

/-- In the boundary configuration there is a transport plan of cost at most 1/2 + 2(|A|-1)·(1/2)/d_y, which is strictly below 1. -/theorem graph_idle_transport_plan_special {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)    (hdiam : G.ediam ≤ 2) (A B C P : Finset V)    (hAmem : ∀ v, v ∈ A ↔ (G.Adj x v ∧ ¬ G.Adj y v ∧ v ≠ y))    (hBmem : ∀ v, v ∈ B ↔ (G.Adj y v ∧ ¬ G.Adj x v ∧ v ≠ x))    (hCmem : ∀ v, v ∈ C ↔ (G.Adj x v ∧ G.Adj y v))    (hPmem : ∀ v, v ∈ P ↔ (¬ G.Adj x v ∧ ¬ G.Adj y v))    (hcover : (Finset.univ : Finset V) = {x} ∪ {y} ∪ A ∪ B ∪ C ∪ P)    (hdx : G.degree x = A.card + C.card + 1)    (hdy : G.degree y = B.card + C.card + 1)    (hAB : A.card = B.card) (hne : 1 ≤ A.card)    (hadj : ∃ v ∈ A, ∃ u ∈ B, G.Adj v u) :    ∃ π : V → V → ℝ, (∀ u v, 0 ≤ π u v) ∧      (∀ u, ∑ v, π u v = graph_idle_measure G (1/2) x u) ∧      (∀ v, ∑ u, π u v = graph_idle_measure G (1/2) y v) ∧      (∑ u, ∑ v, (G.dist u v : ℝ) * π u v) ≤        1/2 + 2*((A.card : ℝ) - 1)*((1/2)/(G.degree y : ℝ)) := by  rcases hadj with ⟨v0, hv0, u0, hu0, hadj0⟩  let γ := (1/2)/(G.degree y : ℝ)  let π : V → V → ℝ := fun u v =>    (if u = x ∧ v = x then γ else 0) +    (if u = x ∧ v = y then 1/2 - γ else 0) +    (if u = y ∧ v = y then γ else 0) +    (if u = v ∧ u ∈ C then γ else 0) +    (if u = v0 ∧ v = u0 then γ else 0) +    (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0)  refine ⟨π, ?_, ?_, ?_, ?_⟩  · intro u v    have hdypos : (0:ℝ) < (G.degree y : ℝ) := by      have : 0 < G.degree y := by        rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨x, hxy.symm⟩      exact_mod_cast this    have hγnn : (0:ℝ) ≤ γ := div_nonneg (by norm_num) (by positivity)    have hγle : γ ≤ 1/2 := by      dsimp [γ]      rw [div_le_iff₀ hdypos]      have h1 : (1:ℝ) ≤ (G.degree y : ℝ) := by        have : 0 < G.degree y := by          rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨x, hxy.symm⟩        exact_mod_cast this      linarith    have hAdenom : (0:ℝ) ≤ (A.card : ℝ) - 1 := by      have : (1:ℝ) ≤ (A.card : ℝ) := by exact_mod_cast hne      linarith    dsimp [π]    repeat' apply add_nonneg    · split_ifs; exact hγnn; rfl    · split_ifs; linarith; rfl    · split_ifs; exact hγnn; rfl    · split_ifs; exact hγnn; rfl    · split_ifs; exact hγnn; rfl    · split_ifs      · exact div_nonneg hγnn hAdenom      · rfl  · intro u    have hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by      intro w      have h : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w      rw [hcover] at h      simp only [Finset.mem_union, Finset.mem_singleton] at h      tauto    have e1 : (∑ v, if u = x ∧ v = x then γ else (0:ℝ)) = if u = x then γ else 0 := by      by_cases h : u = x <;> simp [h]    have e2 : (∑ v, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = if u = x then 1/2 - γ else 0 := by      by_cases h : u = x <;> simp [h]    have e3 : (∑ v, if u = y ∧ v = y then γ else (0:ℝ)) = if u = y then γ else 0 := by      by_cases h : u = y <;> simp [h]    have e4 : (∑ v, if u = v ∧ u ∈ C then γ else (0:ℝ)) = if u ∈ C then γ else 0 := by      have : (∑ v, if u = v ∧ u ∈ C then γ else (0:ℝ)) = ∑ v, if v = u then (if u ∈ C then γ else 0) else 0 := by        apply Finset.sum_congr rfl; intro v _; by_cases h : u = v <;> simp [h, eq_comm]      rw [this]; simp    have e5 : (∑ v, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = if u = v0 then γ else 0 := by      by_cases h : u = v0 <;> simp [h]    have e6 : (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =        if u ∈ A \ {v0} then γ else 0 := by      by_cases hu : u ∈ A \ {v0}      · simp only [hu, true_and, if_true]        have huA : u ∈ A := Finset.mem_sdiff.mp hu |>.1        have hne' : u ≠ v0 := by          have := Finset.mem_sdiff.mp hu |>.2          simp only [Finset.mem_singleton] at this          exact this        have hA2 : 2 ≤ A.card := by          have : {u, v0} ⊆ A := by            intro w hw            simp only [Finset.mem_insert, Finset.mem_singleton] at hw            rcases hw with rfl | rfl <;> assumption          have hle := Finset.card_le_card this          rw [Finset.card_pair hne'] at hle          exact hle        have hdenom : (A.card : ℝ) - 1 ≠ 0 := by          have : 1 < A.card := hA2          have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this          linarith        have hsum : (∑ v, (if v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =            ∑ v ∈ B \ {u0}, (γ / ((A.card : ℝ) - 1)) := by          rw [← Finset.sum_filter]; congr 1; ext v; simp        rw [hsum]        simp only [Finset.sum_const, nsmul_eq_mul]        rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hu0, ← hAB]        exact mul_div_cancel₀ γ hdenom      · simp [hu]    have e56 : (if u = v0 then γ else 0) + (if u ∈ A \ {v0} then γ else 0) =        if u ∈ A then γ else 0 := by      by_cases huA : u ∈ A      · by_cases huv0 : u = v0        · subst huv0; simp [Finset.mem_sdiff, huA]        · have : u ∈ A \ {v0} := by            rw [Finset.mem_sdiff, Finset.mem_singleton]            exact ⟨huA, huv0⟩          simp [huv0, this, huA]      · have h1 : u ≠ v0 := by rintro rfl; exact huA hv0        have h2 : u ∉ A \ {v0} := fun h => huA (Finset.mem_sdiff.mp h |>.1)        simp [huA, h1, h2]    dsimp [π]    simp only [Finset.sum_add_distrib]    change (∑ v, if u = x ∧ v = x then γ else 0) +      (∑ v, if u = x ∧ v = y then 1/2 - γ else 0) +      (∑ v, if u = y ∧ v = y then γ else 0) +      (∑ v, if u = v ∧ u ∈ C then γ else 0) +      (∑ v, if u = v0 ∧ v = u0 then γ else 0) +      (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) = _    rw [e1, e2, e3, e4, e5, e6]    rw [add_assoc ((((if u = x then γ else 0) + if u = x then 1 / 2 - γ else 0) +          if u = y then γ else 0) + if u ∈ C then γ else 0)]    rw [e56]    have hdeg : G.degree x = G.degree y := by rw [hdx, hdy, hAB]    simp only [graph_idle_measure]    rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]    dsimp [γ]    rw [hdeg]    have hxC : x ∉ C := by rw [hCmem]; simp    have hxA : x ∉ A := by rw [hAmem]; simp    have hyC : y ∉ C := by rw [hCmem]; simp    have hyA : y ∉ A := by rw [hAmem]; simp    rcases hu_cases u with hux | huy | huA | huB | huC | huP    · rw [hux]; simp [hxy.ne, hxC, hxA]    · rw [huy]; simp [hxy.ne.symm, hyC, hyA, hxy]    · have hm := (hAmem u).mp huA      have huAx : G.Adj x u := hm.1      have huAny : ¬ G.Adj y u := hm.2.1      have huy : u ≠ y := hm.2.2      have hux : u ≠ x := by rintro rfl; exact G.irrefl hm.1      have huC : u ∉ C := by rw [hCmem]; exact fun h => huAny h.2      simp [hux, huy, huC, huA, huAx]    · have hm := (hBmem u).mp huB      have huBy : G.Adj y u := hm.1      have huBnx : ¬ G.Adj x u := hm.2.1      have hux : u ≠ x := hm.2.2      have huy : u ≠ y := by rintro rfl; exact G.irrefl huBy      have huA : u ∉ A := by rw [hAmem]; exact fun h => huBnx h.1      have huC : u ∉ C := by rw [hCmem]; exact fun h => huBnx h.1      simp [hux, huy, huC, huA, huBnx]    · have hm := (hCmem u).mp huC      have huCx : G.Adj x u := hm.1      have huCy : G.Adj y u := hm.2      have hux : u ≠ x := by rintro rfl; exact G.irrefl huCx      have huy : u ≠ y := by rintro rfl; exact G.irrefl huCy      have huA : u ∉ A := by rw [hAmem]; exact fun h => h.2.1 huCy      simp [hux, huy, huC, huA, huCx]    · have hm := (hPmem u).mp huP      have huPx : ¬ G.Adj x u := hm.1      have huPy : ¬ G.Adj y u := hm.2      have hux : u ≠ x := by rintro rfl; exact huPy hxy.symm      have huy : u ≠ y := by rintro rfl; exact huPx hxy      have huA : u ∉ A := by rw [hAmem]; exact fun h => huPx h.1      have huC : u ∉ C := by rw [hCmem]; exact fun h => huPx h.1      simp [hux, huy, huC, huA, huPx]  · intro v    have hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by      intro w      have h : w ∈ (Finset.univ : Finset V) := Finset.mem_univ w      rw [hcover] at h      simp only [Finset.mem_union, Finset.mem_singleton] at h      tauto    have c1 : (∑ u, if u = x ∧ v = x then γ else (0:ℝ)) = if v = x then γ else 0 := by      by_cases h : v = x <;> simp [h]    have c2 : (∑ u, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = if v = y then 1/2 - γ else 0 := by      by_cases h : v = y <;> simp [h]    have c3 : (∑ u, if u = y ∧ v = y then γ else (0:ℝ)) = if v = y then γ else 0 := by      by_cases h : v = y <;> simp [h]    have c4 : (∑ u, if u = v ∧ u ∈ C then γ else (0:ℝ)) = if v ∈ C then γ else 0 := by      have : (∑ u, if u = v ∧ u ∈ C then γ else (0:ℝ)) = ∑ u, if u = v then (if v ∈ C then γ else 0) else 0 := by        apply Finset.sum_congr rfl; intro u _; by_cases h : u = v <;> simp [h]      rw [this]; simp    have c5 : (∑ u, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = if v = u0 then γ else 0 := by      by_cases h : v = u0 <;> simp [h]    have c6 : (∑ u, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =        if v ∈ B \ {u0} then γ else 0 := by      by_cases hv : v ∈ B \ {u0}      · simp only [hv, and_true, if_true]        have huB : v ∈ B := Finset.mem_sdiff.mp hv |>.1        have hne' : v ≠ u0 := by          have := Finset.mem_sdiff.mp hv |>.2          simp only [Finset.mem_singleton] at this          exact this        have hB2 : 2 ≤ B.card := by          have : {v, u0} ⊆ B := by            intro w hw            simp only [Finset.mem_insert, Finset.mem_singleton] at hw            rcases hw with rfl | rfl <;> assumption          have hle := Finset.card_le_card this          rw [Finset.card_pair hne'] at hle          exact hle        have hdenom : (A.card : ℝ) - 1 ≠ 0 := by          have : 1 < A.card := by rw [hAB]; exact hB2          have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this          linarith        have hsum : (∑ u, (if u ∈ A \ {v0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =            ∑ u ∈ A \ {v0}, (γ / ((A.card : ℝ) - 1)) := by          rw [← Finset.sum_filter]; congr 1; ext u; simp        rw [hsum]        simp only [Finset.sum_const, nsmul_eq_mul]        rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hv0]        exact mul_div_cancel₀ γ hdenom      · simp [hv]    have c23 : (if v = y then 1/2 - γ else 0) + (if v = y then γ else 0) =        if v = y then 1/2 else 0 := by      by_cases h : v = y <;> simp [h]    have c56 : (if v = u0 then γ else 0) + (if v ∈ B \ {u0} then γ else 0) =        if v ∈ B then γ else 0 := by      by_cases hvB : v ∈ B      · by_cases hvu0 : v = u0        · subst hvu0; simp [Finset.mem_sdiff, hvB]        · have : v ∈ B \ {u0} := by            rw [Finset.mem_sdiff, Finset.mem_singleton]            exact ⟨hvB, hvu0⟩          simp [hvu0, this, hvB]      · have h1 : v ≠ u0 := by rintro rfl; exact hvB hu0        have h2 : v ∉ B \ {u0} := fun h => hvB (Finset.mem_sdiff.mp h |>.1)        simp [hvB, h1, h2]    dsimp [π]    simp only [Finset.sum_add_distrib]    change (∑ u, if u = x ∧ v = x then γ else 0) +      (∑ u, if u = x ∧ v = y then 1/2 - γ else 0) +      (∑ u, if u = y ∧ v = y then γ else 0) +      (∑ u, if u = v ∧ u ∈ C then γ else 0) +      (∑ u, if u = v0 ∧ v = u0 then γ else 0) +      (∑ u, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) = _    rw [c1, c2, c3, c4, c5, c6]    rw [add_assoc (if v = x then γ else 0)]    rw [c23]    rw [add_assoc ((if v = x then γ else 0) + (if v = y then 1 / 2 else 0) + (if v ∈ C then γ else 0))]    rw [c56]    simp only [graph_idle_measure]    rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]    dsimp [γ]    have hxB : x ∉ B := by rw [hBmem]; simp    have hxC : x ∉ C := by rw [hCmem]; simp    have hyB : y ∉ B := by rw [hBmem]; simp    have hyC : y ∉ C := by rw [hCmem]; simp    rcases hu_cases v with hvx | hvy | hvA | hvB | hvC | hvP    · rw [hvx]; simp [hxy.ne, hxy.symm, hxB, hxC]    · rw [hvy]; simp [hxy.ne.symm, hyB, hyC]    · have hm := (hAmem v).mp hvA      have hvAx : G.Adj x v := hm.1      have hvAny : ¬ G.Adj y v := hm.2.1      have hvy : v ≠ y := hm.2.2      have hvx : v ≠ x := by rintro rfl; exact G.irrefl hm.1      have hvB : v ∉ B := by rw [hBmem]; exact fun h => hvAny h.1      have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvAny h.2      simp [hvx, hvy, hvB, hvC, hvAny]    · have hm := (hBmem v).mp hvB      have hvBy : G.Adj y v := hm.1      have hvBnx : ¬ G.Adj x v := hm.2.1      have hvx : v ≠ x := hm.2.2      have hvy : v ≠ y := by rintro rfl; exact G.irrefl hvBy      have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvBnx h.1      simp [hvx, hvy, hvC, hvB, hvBy]    · have hm := (hCmem v).mp hvC      have hvCx : G.Adj x v := hm.1      have hvCy : G.Adj y v := hm.2      have hvx : v ≠ x := by rintro rfl; exact G.irrefl hvCx      have hvy : v ≠ y := by rintro rfl; exact G.irrefl hvCy      have hvB : v ∉ B := by rw [hBmem]; exact fun h => h.2.1 hvCx      simp [hvx, hvy, hvC, hvB, hvCy]    · have hm := (hPmem v).mp hvP      have hvPx : ¬ G.Adj x v := hm.1      have hvPy : ¬ G.Adj y v := hm.2      have hvx : v ≠ x := by rintro rfl; exact hvPy hxy.symm      have hvy : v ≠ y := by rintro rfl; exact hvPx hxy      have hvB : v ∉ B := by rw [hBmem]; exact fun h => hvPy h.1      have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvPx h.1      simp [hvx, hvy, hvC, hvB, hvPy]  · have hdist2 (u v : V) : (G.dist u v : ℝ) ≤ 2 := by      exact_mod_cast graph_dist_le_two_of_ediam_le_two G hdiam u v    have hAdenom : (0:ℝ) ≤ (A.card : ℝ) - 1 := by      have : (1:ℝ) ≤ (A.card : ℝ) := by exact_mod_cast hne      linarith    have hγnn : (0:ℝ) ≤ γ := div_nonneg (by norm_num) (by positivity)    have hT6nn (u v : V) : (0:ℝ) ≤ (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) := by      split_ifs; exact div_nonneg hγnn hAdenom; rfl    have hle_pointwise (u v : V) :        (G.dist u v : ℝ) * π u v ≤          (if u = x ∧ v = y then 1/2 - γ else 0) +          (if u = v0 ∧ v = u0 then γ else 0) +          2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) := by      have hd1 : (G.dist u v : ℝ) * (if u = x ∧ v = x then γ else 0) = 0 := by        by_cases h : u = x ∧ v = x        · rw [h.1, h.2]; simp        · simp [h]      have hd2 : (G.dist u v : ℝ) * (if u = x ∧ v = y then 1/2 - γ else 0) =          (if u = x ∧ v = y then 1/2 - γ else 0) := by        by_cases h : u = x ∧ v = y        · rw [h.1, h.2]          have hd : (G.dist x y : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hxy]          simp [hd]        · simp [h]      have hd3 : (G.dist u v : ℝ) * (if u = y ∧ v = y then γ else 0) = 0 := by        by_cases h : u = y ∧ v = y        · rw [h.1, h.2]; simp        · simp [h]      have hd4 : (G.dist u v : ℝ) * (if u = v ∧ u ∈ C then γ else 0) = 0 := by        by_cases h : u = v ∧ u ∈ C        · rw [h.1]; simp        · simp [h]      have hd5 : (G.dist u v : ℝ) * (if u = v0 ∧ v = u0 then γ else 0) =          (if u = v0 ∧ v = u0 then γ else 0) := by        by_cases h : u = v0 ∧ v = u0        · rw [h.1, h.2]          have hd : (G.dist v0 u0 : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hadj0]          simp [hd]        · simp [h]      have hd6 : (G.dist u v : ℝ) * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) ≤          2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0) :=        mul_le_mul_of_nonneg_right (hdist2 u v) (hT6nn u v)      dsimp [π]      linarith    have hsum_le : (∑ u, ∑ v, (G.dist u v : ℝ) * π u v) ≤        ∑ u, ∑ v, ((if u = x ∧ v = y then 1/2 - γ else 0) +          (if u = v0 ∧ v = u0 then γ else 0) +          2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else 0)) :=      Finset.sum_le_sum fun u _ => Finset.sum_le_sum fun v _ => hle_pointwise u v    apply hsum_le.trans    simp_rw [Finset.sum_add_distrib]    have hsum1 : (∑ u, ∑ v, if u = x ∧ v = y then 1/2 - γ else (0:ℝ)) = 1/2 - γ := by      have h (u v : V) : (if u = x ∧ v = y then 1/2 - γ else (0 : ℝ)) =          (if u = x then if v = y then 1/2 - γ else 0 else 0) := by        split_ifs <;> tauto      simp_rw [h]; simp    have hsum2 : (∑ u, ∑ v, if u = v0 ∧ v = u0 then γ else (0:ℝ)) = γ := by      have h (u v : V) : (if u = v0 ∧ v = u0 then γ else (0 : ℝ)) =          (if u = v0 then if v = u0 then γ else 0 else 0) := by        split_ifs <;> tauto      simp_rw [h]; simp    have hsum3 : (∑ u, ∑ v, 2 * (if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ))) =        2 * ((A.card : ℝ) - 1) * γ := by      simp_rw [← Finset.mul_sum]      have hstep (u : V) : (∑ v, if u ∈ A \ {v0} ∧ v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0:ℝ)) =          if u ∈ A \ {v0} then γ else 0 := by        by_cases hu : u ∈ A \ {v0}        · simp only [hu, true_and, if_true]          have huA : u ∈ A := Finset.mem_sdiff.mp hu |>.1          have hne' : u ≠ v0 := by            have := Finset.mem_sdiff.mp hu |>.2            simp only [Finset.mem_singleton] at this            exact this          have hA2 : 2 ≤ A.card := by            have : {u, v0} ⊆ A := by              intro w hw              simp only [Finset.mem_insert, Finset.mem_singleton] at hw              rcases hw with rfl | rfl <;> assumption            have hle := Finset.card_le_card this            rw [Finset.card_pair hne'] at hle            exact hle          have hdenom : (A.card : ℝ) - 1 ≠ 0 := by            have : 1 < A.card := hA2            have : (1 : ℝ) < (A.card : ℝ) := Nat.one_lt_cast.mpr this            linarith          have hsum : (∑ v, (if v ∈ B \ {u0} then γ / ((A.card : ℝ) - 1) else (0 : ℝ))) =              ∑ v ∈ B \ {u0}, (γ / ((A.card : ℝ) - 1)) := by            rw [← Finset.sum_filter]; congr 1; ext v; simp          rw [hsum]          simp only [Finset.sum_const, nsmul_eq_mul]          rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hu0, ← hAB]          exact mul_div_cancel₀ γ hdenom        · simp [hu]      simp_rw [hstep]      have hsum : (∑ u, if u ∈ A \ {v0} then γ else (0 : ℝ)) = ∑ u ∈ A \ {v0}, γ := by        rw [← Finset.sum_filter]; congr 1; ext u; simp      rw [hsum]      simp only [Finset.sum_const, nsmul_eq_mul]      rw [Finset.sdiff_singleton_eq_erase, Finset.cast_card_erase_of_mem hv0]      ring    rw [hsum1, hsum2, hsum3]    dsimp [γ]    linarith
See it in the graphDiscuss this resultChallenge it