AFTD Auto-Formalizing Theoretical Domains

graph_idle_transport_plan_main_cost

theoremverified

For an edge xy in a graph of diameter at most 2, the main plan from μ_x^{1/2} to μ_y^{1/2} costs at most 1/2 − (1/2)/d_x + 2|B|·(1/2)/d_y.

Statement

theorem graph_idle_transport_plan_main_cost {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)
    (hle : G.degree x ≤ G.degree y) :
    (∑ u, ∑ v, (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v) ≤
      1/2 - (1/2)/(G.degree x : ℝ) + 2*((B.card : ℝ))*((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_idle_transport_plan_mainThe main transport plan at idleness 1/2: with β = (1/2)/d_x, γ = (1/2)/d_y, π(u,v) = γ·[u=x][v=x] + ψ(u)[v=y] + γ[u=v][u∈C] +…
  • 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|.
Used by 2

The proof, explained

The cost of the main transport plan $\pi$ is bounded by estimating the contribution $\text{dist}(u, v) \cdot \pi(u, v)$ for each pair of vertices $(u, v)$. Every pair with nonzero mass has distance 0 (for diagonal pairs), distance 1 (for the edge $(x, y)$), or distance at most 2 (by the graph diameter bound $\text{ediam}(G) \le 2$). Summing these pointwise bounds yields $1/2 - (1/2)/d_x$ from the pair $(x, y)$ plus $2 \sum_u F(u)$ from the mass transported to $B$. Partitioning the neighborhood into $A, B, C$ and $\{x, y\}$ allows an exact evaluation $\sum_u F(u) = |B| \cdot (1/2)/d_y$, establishing the upper bound.

  1. Distances are bounded by 2, the degrees $d_x, d_y$ are strictly positive with $d_x \le d_y$, and the weight difference $1/(2d_x) - 1/(2d_y)$ is non-negative.

    We define the auxiliary vertex weight function $F(u)$, which assigns $1/(2d_x) - 1/(2d_y)$ to $x$ and vertices in $C$, $1/(2d_x)$ to vertices in $A$, and 0 otherwise. Since $G$ has diameter at most 2, every pair of vertices satisfies $\text{dist}(u, v) \le 2$ by `graph_dist_le_two_of_ediam_le_two`. Because $x$ and $y$ are adjacent, $d_x > 0$, and using $d_x \le d_y$ we find $0 < d_x \le d_y$ in $\mathbb{R}$. Monotonicity of division via `div_le_div_of_nonneg_left` then yields $1/(2d_x) - 1/(2d_y) \ge 0$.

    lines 15–31

    uses graph_dist_le_two_of_ediam_le_two, SimpleGraph.mem_neighborFinset, Finset.card_pos.mpr, Nat.cast_pos.mpr, Nat.cast_le.mpr, sub_nonneg, div_le_div_of_nonneg_left

      have open_finset : True := trivial
      let F : V → ℝ := fun u =>
        if u = x ∨ u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)
        else if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0
    
      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 hpos_dx : 0 < G.degree x := by
        have : y ∈ G.neighborFinset x := by simp [SimpleGraph.mem_neighborFinset, hxy]
        exact Finset.card_pos.mpr ⟨y, this⟩
      have hpos_dx_R : 0 < (G.degree x : ℝ) := Nat.cast_pos.mpr hpos_dx
      have hle_R : (G.degree x : ℝ) ≤ (G.degree y : ℝ) := Nat.cast_le.mpr hle
      have hpos_dy_R : 0 < (G.degree y : ℝ) := hpos_dx_R.trans_le hle_R
      have hsub_nonneg : 0 ≤ 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) := by
        rw [sub_nonneg]
        exact div_le_div_of_nonneg_left (by norm_num) hpos_dx_R hle_R
    
  2. Pointwise, $\text{dist}(u, v) \cdot \pi(u, v) \le \mathbf{1}_{u=x, v=y}(1/2 - 1/(2d_x)) + 2 \cdot \mathbf{1}_{v \in B} \frac{F(u)}{|B|}$ for all $u, v \in V$.

    Unfolding $\pi = \text{graph\_idle\_transport\_plan\_main}$, it is the sum of four parts. The fourth component (mass moved into $B$) is non-negative and multiplied by $\text{dist}(u, v) \le 2$, bounding its contribution by $2 \cdot \mathbf{1}_{v \in B} \frac{F(u)}{|B|}$. For the remaining three parts: the diagonal masses at $(x, x)$ and $(u, u)$ for $u \in C$ have distance 0, giving zero cost; the mass at $v = y$ has distance $\text{dist}(x, y) = 1$ when $u = x$ (using `SimpleGraph.dist_eq_one_iff_adj.mpr`) and distance 0 when $u = y$. Adding these contributions bounds the product pointwise.

    lines 32–74

    uses div_nonneg, Nat.cast_nonneg, mul_le_mul_of_nonneg_right, graph_idle_transport_plan_main, SimpleGraph.dist_eq_one_iff_adj.mpr

      have hle_pointwise (u v : V) :
          (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v ≤
            (if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) +
            2 * (if v ∈ B then F u / (B.card : ℝ) else 0) := by
        have hpos_p4 : 0 ≤ if v ∈ B then F u / (B.card : ℝ) else 0 := by
          dsimp [F]
          split_ifs with hv hu1 hu2
          · exact div_nonneg hsub_nonneg (Nat.cast_nonneg _)
          · exact div_nonneg (div_nonneg (by norm_num) (by linarith)) (Nat.cast_nonneg _)
          · simp
          · simp
        have hd4 : (G.dist u v : ℝ) * (if v ∈ B then F u / (B.card : ℝ) else 0) ≤
            2 * (if v ∈ B then F u / (B.card : ℝ) else 0) :=
          mul_le_mul_of_nonneg_right (hdist2 u v) hpos_p4
        unfold graph_idle_transport_plan_main
        have hd1 : (G.dist u v : ℝ) * (if u = x ∧ v = x then 1 / 2 / (G.degree y : ℝ) else 0) = 0 := by
          split_ifs with h
          · rcases h with ⟨rfl, rfl⟩; simp
          · ring
        have hd2 : (G.dist u v : ℝ) * (if v = y then if u = x then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else if u = y then 1 / 2 / (G.degree x : ℝ) else 0 else 0) =
            if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0 := by
          by_cases hv : v = y
          · subst v
            by_cases hu : u = x
            · subst u
              have : (G.dist x y : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hxy]
              simp [this]
            · simp [hu]
              by_cases huy : u = y
              · subst u; simp
              · simp [huy]
          · simp [hv]
        have hd3 : (G.dist u v : ℝ) * (if u = v then if u ∈ C then 1 / 2 / (G.degree y : ℝ) else 0 else 0) = 0 := by
          split_ifs with h1 h2
          · subst h1; simp
          · ring
          · ring
        change (G.dist u v : ℝ) * (((if u = x ∧ v = x then 1 / 2 / (G.degree y : ℝ) else 0) +
            (if v = y then if u = x then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else if u = y then 1 / 2 / (G.degree x : ℝ) else 0 else 0) +
            (if u = v then if u ∈ C then 1 / 2 / (G.degree y : ℝ) else 0 else 0)) +
            (if v ∈ B then F u / (B.card : ℝ) else 0)) ≤ _
        linarith
    
  3. The total transport cost is bounded by the double sum of the pointwise upper bounds.

    Summing the pointwise inequality over all $u, v \in V$ using `Finset.sum_le_sum` bounds the double sum on the left by the double sum of the upper bounds, reducing the goal to evaluating the latter.

    lines 75–80

    uses Finset.sum_le_sum

      have hsum_le : (∑ u, ∑ v, (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v) ≤
          ∑ u, ∑ v, ((if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) +
            2 * (if v ∈ B then F u / (B.card : ℝ) else 0)) :=
        Finset.sum_le_sum fun u _ => Finset.sum_le_sum fun v _ => hle_pointwise u v
    
      apply hsum_le.trans
  4. The vertex $x$ is not in $A$ or $C$, and $A$ and $C$ are disjoint.

    Vertices in $A$ and $C$ are adjacent to $x$, so by irreflexivity of simple graphs, $x \notin A$ and $x \notin C$. Vertices in $A$ are non-adjacent to $y$ while vertices in $C$ are adjacent to $y$, so $A$ and $C$ are disjoint by `Finset.disjoint_left`.

    lines 81–95

    uses Finset.disjoint_left

      have hx_not_C : x ∉ C := by
        intro hc
        have h := (hCmem x).mp hc
        exact G.irrefl h.1
      have hx_not_A : x ∉ A := by
        intro ha
        have h := (hAmem x).mp ha
        exact G.irrefl h.1
      have hdisj_AC : Disjoint A C := by
        rw [Finset.disjoint_left]
        intro v hvA hvC
        have h1 := ((hAmem v).mp hvA).2.1
        have h2 := ((hCmem v).mp hvC).2
        exact h1 h2
    
  5. The weight function $F(u)$ decomposes into three separate indicator terms on $\{x\}$, $C$, and $A$.

    Because the sets $\{x\}$, $C$, and $A$ are pairwise disjoint, case analysis on membership of $u$ in these sets simplifies the nested if-then-else definition of $F(u)$ into the sum of the three disjoint indicator functions.

    lines 96–109

    uses Finset.disjoint_left.mp

      have hF (u : V) : F u =
          (if u = x then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) +
          (if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) +
          (if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) := by
        dsimp [F]
        by_cases hux : u = x
        · subst u
          simp [hx_not_C, hx_not_A]
        · simp [hux]
          by_cases huC : u ∈ C
          · have : u ∉ A := fun huA => (Finset.disjoint_left.mp hdisj_AC huA) huC
            simp [huC, this]
          · simp [huC]
    
  6. The total weight sums to $\sum_u F(u) = |B| \cdot \frac{1/2}{d_y}$.

    Distributing the sum over the indicator decomposition of $F$ via `Finset.sum_add_distrib`, the contributions of $\{x\}$, $C$, and $A$ evaluate respectively to $1/(2d_x) - 1/(2d_y)$, $|C|(1/(2d_x) - 1/(2d_y))$, and $|A|(1/(2d_x))$. Substituting the degree formulas $d_x = |A| + |C| + 1$ and $d_y = |B| + |C| + 1$, clearing denominators with `field_simp`, and simplifying with `ring` proves that the sum reduces exactly to $|B| \cdot \frac{1/2}{d_y}$.

    lines 110–140

    uses Finset.sum_add_distrib, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul

      have hsum_F : (∑ u, F u) = (B.card : ℝ) * (1 / 2 / (G.degree y : ℝ)) := by
        simp_rw [hF]
        rw [Finset.sum_add_distrib, Finset.sum_add_distrib]
        have h1 : (∑ u, if u = x then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =
            1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) := by simp
        have h2 : (∑ u, if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =
            (C.card : ℝ) * (1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)) := by
          have : (∑ u, if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =
              ∑ u ∈ C, (1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)) := by
            rw [← Finset.sum_filter]; congr 1; ext v; simp
          rw [this]
          simp only [Finset.sum_const, nsmul_eq_mul]
        have h3 : (∑ u, if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) =
            (A.card : ℝ) * (1 / 2 / (G.degree x : ℝ)) := by
          have : (∑ u, if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) =
              ∑ u ∈ A, (1 / 2 / (G.degree x : ℝ)) := by
            rw [← Finset.sum_filter]; congr 1; ext v; simp
          rw [this]
          simp only [Finset.sum_const, nsmul_eq_mul]
        rw [h1, h2, h3]
        have hdx_R : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by
          exact_mod_cast hdx
        have hdy_R : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by
          exact_mod_cast hdy
        have hd1 : 1 / 2 / (G.degree x : ℝ) = 1 / (2 * (G.degree x : ℝ)) := by ring
        have hd2 : 1 / 2 / (G.degree y : ℝ) = 1 / (2 * (G.degree y : ℝ)) := by ring
        rw [hd1, hd2]
        field_simp
        rw [hdx_R, hdy_R]
        ring
    
  7. The double sum of the pointwise upper bound equals $1/2 - 1/(2d_x) + 2|B| \cdot \frac{1/2}{d_y}$, completing the proof.

    Distributing the double sum splits it into two parts. The single nonzero term $\mathbf{1}_{u=x, v=y}(1/2 - 1/(2d_x))$ sums to $1/2 - 1/(2d_x)$. The second term factors out 2 by `Finset.mul_sum`; summing $\mathbf{1}_{v \in B} \frac{F(u)}{|B|}$ over $v \in V$ leaves $F(u)$ when $B \neq \emptyset$ (cancelling $|B|$ with `mul_div_cancel₀`) and 0 when $B = \emptyset$. Summing over $u$ and substituting $\sum_u F(u) = |B| \frac{1/2}{d_y}$ yields $2|B| \cdot \frac{1/2}{d_y}$, matching the required expression.

    lines 141–172

    uses Finset.sum_add_distrib, Finset.mul_sum, Finset.nonempty_iff_ne_empty.mpr, Finset.Nonempty.card_pos, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, mul_div_cancel₀

      simp_rw [Finset.sum_add_distrib]
      have hsum_xy : (∑ u, ∑ v, if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) =
          1 / 2 - 1 / 2 / (G.degree x : ℝ) := by
        have h (u v : V) : (if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else (0 : ℝ)) =
            (if u = x then if v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0 else 0) := by
          split_ifs <;> tauto
        simp_rw [h]
        simp
      rw [hsum_xy]
      simp_rw [← Finset.mul_sum]
      have hsum_v (u : V) : (∑ v, if v ∈ B then F u / (B.card : ℝ) else (0 : ℝ)) =
          if B = ∅ then 0 else F u := by
        by_cases hB : B = ∅
        · simp [hB]
        · have hB_card : (B.card : ℝ) ≠ 0 := by
            have : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB
            have : 0 < B.card := Finset.Nonempty.card_pos this
            positivity
          have hsum : (∑ v, if v ∈ B then F u / (B.card : ℝ) else 0) = ∑ v ∈ B, (F u / (B.card : ℝ)) := by
            rw [← Finset.sum_filter]; congr 1; ext v; simp
          rw [hsum]
          simp only [Finset.sum_const, nsmul_eq_mul]
          rw [mul_div_cancel₀ _ hB_card]
          simp [hB]
      simp_rw [hsum_v]
      have hB_sum : (∑ x, if B = ∅ then 0 else F x) = (B.card : ℝ) * (1 / 2 / (G.degree y : ℝ)) := by
        by_cases hB : B = ∅
        · subst hB; simp
        · simp [hB, hsum_F]
      rw [hB_sum]
      ring_nf
      rfl
graph_dist_le_two_of_ediam_le_two
In a graph with extended diameter at most 2, the shortest path distance between any two vertices is at most 2.
SimpleGraph.mem_neighborFinset
A vertex $w$ is in the neighbor finset of $v$ if and only if $v$ and $w$ are adjacent.
Finset.card_pos.mpr
A finset has strictly positive cardinality if and only if it is nonempty.
Nat.cast_pos.mpr
A natural number is strictly positive in $\mathbb{R}$ if it is strictly positive in $\mathbb{N}$.
Nat.cast_le.mpr
Inequality between natural numbers is preserved when cast into $\mathbb{R}$.
sub_nonneg
In an ordered additive group, $0 \le a - b$ if and only if $b \le a$.
div_le_div_of_nonneg_left
For positive $c \le b$ and non-negative $a$, $a / b \le a / c$.
div_nonneg
The quotient of two non-negative numbers is non-negative.
Nat.cast_nonneg
The cast of a natural number into an ordered semiring is non-negative.
mul_le_mul_of_nonneg_right
Multiplying an inequality $b \le c$ by a non-negative number $a$ on the right preserves the inequality: $b \cdot a \le c \cdot a$.
graph_idle_transport_plan_main
The definition of the main transport plan $\pi(u, v)$ between the neighborhood distributions of $x$ and $y$.
SimpleGraph.dist_eq_one_iff_adj.mpr
Adjacent vertices in a simple graph have distance 1.
Finset.sum_le_sum
If $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
Finset.disjoint_left
Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_left.mp
If two finsets are disjoint, an element of the first cannot belong to the second.
Finset.sum_add_distrib
The sum of a sum of functions over a finset equals the sum of the individual sums.
Finset.sum_filter
The sum of $f(a)$ over elements satisfying predicate $p$ equals the sum over the entire set of `if p a then f a else 0`.
Finset.sum_const
The sum of a constant $b$ over a finset $s$ equals $|s| \cdot b$.
nsmul_eq_mul
Scalar multiplication by a natural number $n$ equals ordinary multiplication by $n$.
Finset.mul_sum
Multiplication distributes over a finite sum: $a \cdot \sum_i f(i) = \sum_i a \cdot f(i)$.
Finset.nonempty_iff_ne_empty.mpr
A finset is nonempty if and only if it is not equal to the empty set.
Finset.Nonempty.card_pos
A nonempty finset has strictly positive cardinality.
mul_div_cancel₀
For a nonzero element $b$, $b \cdot (a / b) = a$.

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

/-- Cost of the main plan: at most 1/2 − (1/2)/d_x + 2|B|·(1/2)/d_y. -/theorem graph_idle_transport_plan_main_cost {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)    (hle : G.degree x ≤ G.degree y) :    (∑ u, ∑ v, (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v) ≤      1/2 - (1/2)/(G.degree x : ℝ) + 2*((B.card : ℝ))*((1/2)/(G.degree y : ℝ)) := by  have open_finset : True := trivial  let F : V → ℝ := fun u =>    if u = x ∨ u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)    else if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0  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 hpos_dx : 0 < G.degree x := by    have : y ∈ G.neighborFinset x := by simp [SimpleGraph.mem_neighborFinset, hxy]    exact Finset.card_pos.mpr ⟨y, this⟩  have hpos_dx_R : 0 < (G.degree x : ℝ) := Nat.cast_pos.mpr hpos_dx  have hle_R : (G.degree x : ℝ) ≤ (G.degree y : ℝ) := Nat.cast_le.mpr hle  have hpos_dy_R : 0 < (G.degree y : ℝ) := hpos_dx_R.trans_le hle_R  have hsub_nonneg : 0 ≤ 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) := by    rw [sub_nonneg]    exact div_le_div_of_nonneg_left (by norm_num) hpos_dx_R hle_R  have hle_pointwise (u v : V) :      (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v ≤        (if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) +        2 * (if v ∈ B then F u / (B.card : ℝ) else 0) := by    have hpos_p4 : 0 ≤ if v ∈ B then F u / (B.card : ℝ) else 0 := by      dsimp [F]      split_ifs with hv hu1 hu2      · exact div_nonneg hsub_nonneg (Nat.cast_nonneg _)      · exact div_nonneg (div_nonneg (by norm_num) (by linarith)) (Nat.cast_nonneg _)      · simp      · simp    have hd4 : (G.dist u v : ℝ) * (if v ∈ B then F u / (B.card : ℝ) else 0) ≤        2 * (if v ∈ B then F u / (B.card : ℝ) else 0) :=      mul_le_mul_of_nonneg_right (hdist2 u v) hpos_p4    unfold graph_idle_transport_plan_main    have hd1 : (G.dist u v : ℝ) * (if u = x ∧ v = x then 1 / 2 / (G.degree y : ℝ) else 0) = 0 := by      split_ifs with h      · rcases h with ⟨rfl, rfl⟩; simp      · ring    have hd2 : (G.dist u v : ℝ) * (if v = y then if u = x then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else if u = y then 1 / 2 / (G.degree x : ℝ) else 0 else 0) =        if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0 := by      by_cases hv : v = y      · subst v        by_cases hu : u = x        · subst u          have : (G.dist x y : ℝ) = 1 := by simp [SimpleGraph.dist_eq_one_iff_adj.mpr hxy]          simp [this]        · simp [hu]          by_cases huy : u = y          · subst u; simp          · simp [huy]      · simp [hv]    have hd3 : (G.dist u v : ℝ) * (if u = v then if u ∈ C then 1 / 2 / (G.degree y : ℝ) else 0 else 0) = 0 := by      split_ifs with h1 h2      · subst h1; simp      · ring      · ring    change (G.dist u v : ℝ) * (((if u = x ∧ v = x then 1 / 2 / (G.degree y : ℝ) else 0) +        (if v = y then if u = x then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else if u = y then 1 / 2 / (G.degree x : ℝ) else 0 else 0) +        (if u = v then if u ∈ C then 1 / 2 / (G.degree y : ℝ) else 0 else 0)) +        (if v ∈ B then F u / (B.card : ℝ) else 0)) ≤ _    linarith  have hsum_le : (∑ u, ∑ v, (G.dist u v : ℝ) * graph_idle_transport_plan_main G x y A B C u v) ≤      ∑ u, ∑ v, ((if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) +        2 * (if v ∈ B then F u / (B.card : ℝ) else 0)) :=    Finset.sum_le_sum fun u _ => Finset.sum_le_sum fun v _ => hle_pointwise u v  apply hsum_le.trans  have hx_not_C : x ∉ C := by    intro hc    have h := (hCmem x).mp hc    exact G.irrefl h.1  have hx_not_A : x ∉ A := by    intro ha    have h := (hAmem x).mp ha    exact G.irrefl h.1  have hdisj_AC : Disjoint A C := by    rw [Finset.disjoint_left]    intro v hvA hvC    have h1 := ((hAmem v).mp hvA).2.1    have h2 := ((hCmem v).mp hvC).2    exact h1 h2  have hF (u : V) : F u =      (if u = x then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) +      (if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) +      (if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) := by    dsimp [F]    by_cases hux : u = x    · subst u      simp [hx_not_C, hx_not_A]    · simp [hux]      by_cases huC : u ∈ C      · have : u ∉ A := fun huA => (Finset.disjoint_left.mp hdisj_AC huA) huC        simp [huC, this]      · simp [huC]  have hsum_F : (∑ u, F u) = (B.card : ℝ) * (1 / 2 / (G.degree y : ℝ)) := by    simp_rw [hF]    rw [Finset.sum_add_distrib, Finset.sum_add_distrib]    have h1 : (∑ u, if u = x then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =        1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) := by simp    have h2 : (∑ u, if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =        (C.card : ℝ) * (1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)) := by      have : (∑ u, if u ∈ C then 1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ) else 0) =          ∑ u ∈ C, (1 / 2 / (G.degree x : ℝ) - 1 / 2 / (G.degree y : ℝ)) := by        rw [← Finset.sum_filter]; congr 1; ext v; simp      rw [this]      simp only [Finset.sum_const, nsmul_eq_mul]    have h3 : (∑ u, if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) =        (A.card : ℝ) * (1 / 2 / (G.degree x : ℝ)) := by      have : (∑ u, if u ∈ A then 1 / 2 / (G.degree x : ℝ) else 0) =          ∑ u ∈ A, (1 / 2 / (G.degree x : ℝ)) := by        rw [← Finset.sum_filter]; congr 1; ext v; simp      rw [this]      simp only [Finset.sum_const, nsmul_eq_mul]    rw [h1, h2, h3]    have hdx_R : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by      exact_mod_cast hdx    have hdy_R : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by      exact_mod_cast hdy    have hd1 : 1 / 2 / (G.degree x : ℝ) = 1 / (2 * (G.degree x : ℝ)) := by ring    have hd2 : 1 / 2 / (G.degree y : ℝ) = 1 / (2 * (G.degree y : ℝ)) := by ring    rw [hd1, hd2]    field_simp    rw [hdx_R, hdy_R]    ring  simp_rw [Finset.sum_add_distrib]  have hsum_xy : (∑ u, ∑ v, if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0) =      1 / 2 - 1 / 2 / (G.degree x : ℝ) := by    have h (u v : V) : (if u = x ∧ v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else (0 : ℝ)) =        (if u = x then if v = y then 1 / 2 - 1 / 2 / (G.degree x : ℝ) else 0 else 0) := by      split_ifs <;> tauto    simp_rw [h]    simp  rw [hsum_xy]  simp_rw [← Finset.mul_sum]  have hsum_v (u : V) : (∑ v, if v ∈ B then F u / (B.card : ℝ) else (0 : ℝ)) =      if B = ∅ then 0 else F u := by    by_cases hB : B = ∅    · simp [hB]    · have hB_card : (B.card : ℝ) ≠ 0 := by        have : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB        have : 0 < B.card := Finset.Nonempty.card_pos this        positivity      have hsum : (∑ v, if v ∈ B then F u / (B.card : ℝ) else 0) = ∑ v ∈ B, (F u / (B.card : ℝ)) := by        rw [← Finset.sum_filter]; congr 1; ext v; simp      rw [hsum]      simp only [Finset.sum_const, nsmul_eq_mul]      rw [mul_div_cancel₀ _ hB_card]      simp [hB]  simp_rw [hsum_v]  have hB_sum : (∑ x, if B = ∅ then 0 else F x) = (B.card : ℝ) * (1 / 2 / (G.degree y : ℝ)) := by    by_cases hB : B = ∅    · subst hB; simp    · simp [hB, hsum_F]  rw [hB_sum]  ring_nf  rfl
See it in the graphDiscuss this resultChallenge it