graph_idle_transport_plan_main_cost
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
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_idle_wasserstein_lt_one_of_edge_partitionGiven the edge partition of a graph of diameter at most 2 whose minimum degree is at least 2n/3 − 1, the idleness-1/2 measures at the…
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.
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$.
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_lefthave 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
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.
uses
div_nonneg,Nat.cast_nonneg,mul_le_mul_of_nonneg_right,graph_idle_transport_plan_main,SimpleGraph.dist_eq_one_iff_adj.mprhave 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
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.
uses
Finset.sum_le_sumhave 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
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`.
uses
Finset.disjoint_lefthave 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
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.
uses
Finset.disjoint_left.mphave 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]
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}$.
uses
Finset.sum_add_distrib,Finset.sum_filter,Finset.sum_const,nsmul_eq_mulhave 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
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.
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$.
- Line 15 defines an unused trivial placeholder `open_finset : True := trivial`.
- The algebraic identity in Step 6 (showing that the sum of weights $\sum_u F(u)$ simplifies to $|B| \cdot (1/2)/d_y$) is carried out by automated rational expression simplification via `field_simp` and `ring`.
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.
/-- 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