graph_idle_transport_plan_main_marginals
With β = (1/2)/d_x, γ = (1/2)/d_y and d_x ≤ d_y, A.card ≤ B.card, the main plan has nonnegative entries, row sums μ_x^{1/2} and column sums μ_y^{1/2}.
Statement
theorem graph_idle_transport_plan_main_marginals {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y) (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) (hab : A.card ≤ B.card) : (∀ u v, 0 ≤ graph_idle_transport_plan_main G x y A B C u v) ∧ (∀ u, ∑ v, graph_idle_transport_plan_main G x y A B C u v = graph_idle_measure G (1/2) x u) ∧ (∀ v, ∑ u, graph_idle_transport_plan_main G x y A B C u v = graph_idle_measure G (1/2) y v)
- 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_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
- 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 theorem constructs a valid coupling (transport plan) between the lazy random walk measures μ_x^{1/2} and μ_y^{1/2} on a graph G for adjacent vertices x and y with degrees d_x ≤ d_y. The vertex set is partitioned into {x}, {y}, common neighbours C, exclusive neighbours A of x, exclusive neighbours B of y, and non-neighbours P. Using the degree formulas, an algebraic balance identity shows that the total excess mass (|C| + 1)(β - γ) from {x} ∪ C combined with the mass |A|β from A exactly matches |B|γ, allowing this mass to be uniformly redistributed across B. Nonnegativity follows from γ ≤ β ≤ 1/2, and evaluating the row and column sums across each piece of the vertex partition confirms that the marginals match μ_x^{1/2} and μ_y^{1/2} everywhere.
The degrees d_x and d_y are strictly positive, with γ = (1/2)/d_y ≤ β = (1/2)/d_x ≤ 1/2.
Since x is adjacent to y, the degree of x is at least 1, so d_x > 0. The hypothesis d_x ≤ d_y implies that dividing 1/2 by d_y is at most dividing by d_x, giving γ ≤ β. Furthermore, d_x ≥ 1 implies β = (1/2)/d_x ≤ 1/2.
uses
SimpleGraph.degree_pos_iff_exists_adj,div_le_div_of_nonneg_left,div_le_iff₀classical have hdxpos : (0:ℝ) < (G.degree x : ℝ) := by have : 0 < G.degree x := by rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨y, hxy⟩ exact_mod_cast this have hγβ : (1/2)/(G.degree y : ℝ) ≤ (1/2)/(G.degree x : ℝ) := by have hleR : (G.degree x : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hle exact div_le_div_of_nonneg_left (by norm_num) hdxpos hleR have hβle : (1/2)/(G.degree x : ℝ) ≤ 1/2 := by rw [div_le_iff₀ hdxpos] have h1 : (1:ℝ) ≤ (G.degree x : ℝ) := by have : 0 < G.degree x := by rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨y, hxy⟩ exact_mod_cast this linarith have hABcard : A.card ≤ B.card := hab
If B is empty, then β = γ; and if A is nonempty, then B is also nonempty.
If B = ∅, then |B| = 0, so |A| ≤ |B| forces |A| = 0. By the degree formulas d_x = |A| + |C| + 1 = |C| + 1 and d_y = |B| + |C| + 1 = |C| + 1, we get d_x = d_y, which implies β = γ. Conversely, if any vertex belongs to A, then |A| > 0, which combined with |A| ≤ |B| forces |B| > 0, so B is nonempty.
uses
Finset.card_pos.mpr,Finset.card_pos.mp,lt_of_lt_of_lehave hBempty_beta : B = ∅ → (1/2)/(G.degree x : ℝ) = (1/2)/(G.degree y : ℝ) := by intro hB have hB0 : B.card = 0 := by rw [hB]; simp have hA0 : A.card = 0 := by omega have hdeg : G.degree x = G.degree y := by rw [hdx, hdy, hA0, hB0] rw [hdeg] have hBne_of_memA : ∀ u : V, u ∈ A → B.Nonempty := by intro u hu have hApos : 0 < A.card := Finset.card_pos.mpr ⟨u, hu⟩ exact Finset.card_pos.mp (lt_of_lt_of_le hApos hABcard)
The vertex set is partitioned into {x}, {y}, A, B, C, and P, with x ∉ C and A disjoint from {x} ∪ C.
The hypothesis hcover states that V is the union of {x}, {y}, A, B, C, and P. Since simple graphs have no self-loops, x cannot be adjacent to itself, so x ∉ C. A vertex in A is adjacent to x but not y; hence it cannot be x (as x is adjacent to y) and cannot belong to C (as vertices in C are adjacent to y).
uses
Finset.mem_univ,Finset.mem_union,Finset.mem_singletonhave hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by intro u have h : u ∈ (Finset.univ : Finset V) := Finset.mem_univ u rw [hcover] at h simp only [Finset.mem_union, Finset.mem_singleton] at h tauto have hxnotC : x ∉ C := by rw [hCmem]; simp have hdisj : ∀ u : V, u ∈ A → ¬ (u = x ∨ u ∈ C) := by intro u huA hP have hm := (hAmem u).mp huA have huAny : ¬ G.Adj y u := hm.2.1 rcases hP with h | h · rw [h] at huAny; exact huAny hxy.symm · exact huAny ((hCmem u).mp h).2
The total mass transferred from {x} ∪ C and A equals |B| * γ.
Summing the constant β - γ over the (|C| + 1) vertices of {x} ∪ C gives (|C| + 1)(β - γ), and summing β over A gives |A|β. Substituting d_x = |A| + |C| + 1 and d_y = |B| + |C| + 1 into |A|β + (|C| + 1)(β - γ) yields d_x β - (|C| + 1)γ = 1/2 - (|C| + 1)γ = |B|γ, as verified by clearing denominators.
uses
Finset.mem_insert,Finset.sum_filter,Finset.sum_insert,Finset.sum_const,nsmul_eq_mulhave hfilter : (Finset.univ.filter (fun u : V => u = x ∨ u ∈ C)) = insert x C := by ext u simp [Finset.mem_insert] have hPsum : (∑ u : V, (if (u = x ∨ u ∈ C) then (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) else 0)) = ((C.card:ℝ)+1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) := by rw [← Finset.sum_filter] rw [hfilter] rw [Finset.sum_insert hxnotC] rw [Finset.sum_const, nsmul_eq_mul] ring have hAsum : (∑ u : V, (if u ∈ A then (1/2)/(G.degree x : ℝ) else 0)) = (A.card:ℝ) * ((1/2)/(G.degree x : ℝ)) := by rw [← Finset.sum_filter] have hf : (Finset.univ.filter (fun u : V => u ∈ A)) = A := by ext u; simp rw [hf, Finset.sum_const, nsmul_eq_mul] have hkey : (A.card : ℝ) * ((1/2)/(G.degree x : ℝ)) + ((C.card : ℝ) + 1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) = (B.card : ℝ) * ((1/2)/(G.degree y : ℝ)) := by have hdxR : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by rw [hdx]; push_cast; ring have hdyR : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by rw [hdy]; push_cast; ring rw [hdxR, hdyR] field_simp ring
The sum over all u of the mass allocated to B equals |B| * γ.
Since A is disjoint from {x} ∪ C, the integrand defining the mass transferred to B from u splits pointwise into an indicator on {x} ∪ C and an indicator on A. Distributing the sum and applying the two component sum formulas gives (|C| + 1)(β - γ) + |A|β, which equals |B|γ by the key identity.
uses
Finset.sum_congr,Finset.sum_add_distribhave hpoint : ∀ u : V, (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) = (if (u = x ∨ 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 intro u by_cases hP : u = x ∨ u ∈ C · have hAn : u ∉ A := fun hA => hdisj u hA hP simp [hP, hAn] · by_cases hA : u ∈ A · simp [hP, hA] · simp [hP, hA] have hsum : (∑ u : V, (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)) = (B.card:ℝ) * ((1/2)/(G.degree y : ℝ)) := by calc (∑ u : V, (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)) = ∑ u : V, ((if (u = x ∨ 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 apply Finset.sum_congr rfl; intro u _; exact hpoint u _ = (∑ u : V, (if (u = x ∨ u ∈ C) then (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) else 0)) + (∑ u : V, (if u ∈ A then (1/2)/(G.degree x : ℝ) else 0)) := by rw [Finset.sum_add_distrib] _ = ((C.card:ℝ)+1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) + (A.card:ℝ) * ((1/2)/(G.degree x : ℝ)) := by rw [hPsum, hAsum] _ = (B.card:ℝ) * ((1/2)/(G.degree y : ℝ)) := by linarith [hkey]
All entries of the transport plan are nonnegative.
The plan is defined as a sum of four terms: a mass at (x, x), a mass at {x, y} × {y}, diagonal terms on C, and distribution to B. Each term is nonnegative because γ ≥ 0, β ≥ 0, 1/2 - β ≥ 0 (since β ≤ 1/2), and β - γ ≥ 0 (since γ ≤ β). The quotient by |B| in the fourth term is nonnegative because |B| > 0 when v ∈ B.
uses
div_nonneg,add_nonneg,if_true,if_false,if_posrefine ⟨?_, ?_, ?_⟩ · intro u v have hγnn : (0:ℝ) ≤ (1/2)/(G.degree y : ℝ) := div_nonneg (by norm_num) (by positivity) have hβnn : (0:ℝ) ≤ (1/2)/(G.degree x : ℝ) := div_nonneg (by norm_num) (by positivity) have hβγnn : (0:ℝ) ≤ (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) := by linarith simp only [graph_idle_transport_plan_main] apply add_nonneg apply add_nonneg apply add_nonneg · by_cases h : u = x ∧ v = x · simp only [h, if_true]; exact hγnn · simp [h] · by_cases hvy : v = y · simp only [hvy, if_true] by_cases hux : u = x · simp only [hux, if_true]; linarith · simp only [hux, if_false] by_cases huy : u = y · simp only [huy, if_true]; exact hβnn · simp [huy] · simp [hvy] · by_cases h : u = v · rw [if_pos h] by_cases hC : u ∈ C · simp only [hC, if_true]; exact hγnn · simp [hC] · simp [h] · by_cases hB : v ∈ B · simp only [hB, if_true] by_cases hP : u = x ∨ u ∈ C · simp only [hP, if_true]; exact div_nonneg hβγnn (by positivity) · simp only [hP, if_false] by_cases hA : u ∈ A · simp only [hA, if_true]; exact div_nonneg hβnn (by positivity) · simp [hA] · simp [hB]
For any u, summing the transport plan over v collapses each of the four components to an explicit function of u.
Summing over v evaluates the single-column conditions: the first component is nonzero only at v = x; the second only at v = y; the third only at v = u; and the fourth sums a constant divided by |B| over all |B| elements of B, which cancels to the numerator whenever B is nonempty.
uses
Finset.sum_ite_mem,Finset.univ_inter,Finset.card_pos.mpr,Finset.nonempty_iff_ne_empty.mpr,ne_of_gt,Finset.sum_const,nsmul_eq_mul,div_eq_mul_inv,mul_comm,Finset.sum_add_distrib· intro u have e1 : (∑ v, (if u = x ∧ v = x then (1/2)/(G.degree y : ℝ) else 0)) = (if u = x then (1/2)/(G.degree y : ℝ) else 0) := by by_cases h : u = x · subst h; simp · simp [h] have e2 : (∑ 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 then 1/2 - (1/2)/(G.degree x : ℝ) else if u = y then (1/2)/(G.degree x : ℝ) else 0) := by simp have e3 : (∑ v, (if u = v then (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) else 0)) = (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) := by simp have e4 : (∑ v, (if v ∈ B then (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) / (B.card : ℝ) else 0)) = if B.Nonempty then (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) else 0 := by rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] by_cases h : B = ∅ · subst h; simp · have hc : (B.card : ℝ) ≠ 0 := by have : 0 < B.card := Finset.card_pos.mpr (Finset.nonempty_iff_ne_empty.mpr h) exact_mod_cast ne_of_gt this rw [Finset.sum_const, nsmul_eq_mul] simp [h, hc, div_eq_mul_inv, mul_comm] simp only [graph_idle_transport_plan_main, Finset.sum_add_distrib] rw [e1, e2, e3, e4] simp only [graph_idle_measure] rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]
For every u ∈ V, the row sum equals the lazy random walk measure μ_x^{1/2}(u).
We test the collapsed row sum across the six partition pieces of u: - For u = x, the sum is γ + (1/2 - β) + (β - γ) = 1/2 (with β = γ if B = ∅), matching μ_x^{1/2}(x). - For u = y, only the second term contributes β, matching μ_x^{1/2}(y) since x ~ y. - For u ∈ A, only the fourth term contributes β, matching μ_x^{1/2}(u) since x ~ u. - For u ∈ B, all four terms vanish, matching 0 since x ≁ u. - For u ∈ C, the third and fourth terms give γ + (β - γ) = β, matching μ_x^{1/2}(u) since x ~ u. - For u ∈ P, all terms vanish, matching 0 since x ≁ u.
uses
Finset.nonempty_iff_ne_empty.mprrcases hu_cases u with hux | huy | huA | huB | huC | huP · rw [hux] at * have hxC : x ∉ C := by rw [hCmem]; simp by_cases hB : B = ∅ · have hβγ := hBempty_beta hB simp [hB, hxC] linarith · have hBne : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB simp [hBne, hxC] <;> ring · rw [huy] at * have hyC : y ∉ C := by rw [hCmem]; simp have hyA : y ∉ A := by rw [hAmem]; simp by_cases hBne : B.Nonempty · simp [hBne, hxy, hxy.ne.symm, hyC, hyA] <;> ring · simp [hBne, hxy, hxy.ne.symm, hyC, hyA] <;> ring · have hBne : B.Nonempty := hBne_of_memA u huA 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 intro h; subst h; exact huAny hxy.symm have huC : u ∉ C := by rw [hCmem]; exact fun h => huAny h.2 simp [huA, hBne, huC, hux, huy, huAx] <;> ring · have huBne : B.Nonempty := ⟨u, huB⟩ 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 intro h; subst h; 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 [huBne, huBnx, huA, huC, hux, huy] <;> ring · have hCm := (hCmem u).mp huC have huCx : G.Adj x u := hCm.1 have huCy : G.Adj y u := hCm.2 have hux : u ≠ x := by intro h; subst h; exact G.irrefl huCx have huy : u ≠ y := by intro h; subst h; exact G.irrefl huCy by_cases hB : B = ∅ · have hβγ := hBempty_beta hB simp [hB, huC, hux, huy, huCx] linarith · have hBne : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB simp [hBne, huC, hux, huy, huCx] <;> ring · 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 intro h; subst h; exact huPy hxy.symm have huy : u ≠ y := by intro h; subst h; 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 by_cases hBne : B.Nonempty · simp [hBne, huPx, huA, huC, hux, huy] <;> ring · simp [hBne, huPx, huA, huC, hux, huy] <;> ring
For any v, summing the transport plan over u collapses each of the four components to an explicit function of v.
Summing over u evaluates the row conditions: the first component is nonzero only at u = x; the second (active only when v = y) sums over u ∈ {x, y} to (1/2 - β) + β = 1/2; the third is nonzero only at u = v; and the fourth sums the u-integrand over all u and divides by |B|, yielding (|B|γ)/|B| = γ when v ∈ B.
uses
Finset.sum_add_distrib,Finset.sum_congr,if_true,Finset.sum_div,Finset.card_pos.mpr,ne_of_gt· intro v have c1 : (∑ u, (if u = x ∧ v = x then (1/2)/(G.degree y : ℝ) else 0)) = if v = x then (1/2)/(G.degree y : ℝ) else 0 := by by_cases hv : v = x · rw [hv]; simp · simp [hv] have c2 : (∑ u, (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 v = y then 1/2 else 0 := by by_cases hv : v = y · rw [hv] have hne : x ≠ y := hxy.ne have step : ∑ u : V, (if u = x then 1/2 - (1/2)/(G.degree x : ℝ) else if u = y then (1/2)/(G.degree x : ℝ) else 0) = (∑ u, (if u = x then 1/2 - (1/2)/(G.degree x : ℝ) else 0)) + ∑ u, (if u = y then (1/2)/(G.degree x : ℝ) else 0) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u _ by_cases h1 : u = x · subst h1; simp [hne] · by_cases h2 : u = y · subst h2; simp [h1] · simp [h1, h2] simp only [if_true] rw [step] simp · simp [hv] have c3 : (∑ u, (if u = v then (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) else 0)) = (if v ∈ C then (1/2)/(G.degree y : ℝ) else 0) := by simp have c4 : (∑ u, (if v ∈ B then (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) / (B.card : ℝ) else 0)) = if v ∈ B then (1/2)/(G.degree y : ℝ) else 0 := by by_cases hv : v ∈ B · simp only [hv, if_true] rw [← Finset.sum_div, hsum] have hBpos : 0 < B.card := Finset.card_pos.mpr ⟨v, hv⟩ have hBc : (B.card : ℝ) ≠ 0 := by exact_mod_cast ne_of_gt hBpos field_simp · simp [hv] simp only [graph_idle_transport_plan_main, Finset.sum_add_distrib] rw [c1, c2, c3, c4] simp only [graph_idle_measure] rw [show (1:ℝ) - 1/2 = 1/2 by norm_num]
For every v ∈ V, the column sum equals the lazy random walk measure μ_y^{1/2}(v).
We test the collapsed column sum across the six partition pieces of v: - For v = x, the first component yields γ, matching μ_y^{1/2}(x) since y ~ x. - For v = y, the second component yields 1/2, matching μ_y^{1/2}(y). - For v ∈ A, all components vanish, matching 0 since y ≁ v. - For v ∈ B, the fourth component yields γ, matching μ_y^{1/2}(v) since y ~ v. - For v ∈ C, the third component yields γ, matching μ_y^{1/2}(v) since y ~ v. - For v ∈ P, all components vanish, matching 0 since y ≁ v.
rcases hu_cases v with hvx | hvy | hvA | hvB | hvC | hvP · rw [hvx] at * have hxB : x ∉ B := by rw [hBmem]; simp simp [hxnotC, hxB, hxy.ne, hxy.symm] · rw [hvy] at * have hyC : y ∉ C := by rw [hCmem]; simp have hyB : y ∉ B := by rw [hBmem]; simp simp [hyC, hyB, hxy.ne.symm] · have hm := (hAmem v).mp hvA have hvAny : ¬G.Adj y v := hm.2.1 have hvy : v ≠ y := hm.2.2 have hvx : v ≠ x := by intro h; rw [h] at hm; 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 [hvAny, hvx, hvy, hvB, hvC] · 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 intro h; rw [h] at hvBy; exact G.irrefl hvBy have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvBnx h.1 simp [hvB, hvBy, hvx, hvy, hvC] · 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 intro h; rw [h] at hvCx; exact G.irrefl hvCx have hvy : v ≠ y := by intro h; rw [h] at hvCy; exact G.irrefl hvCy have hvB : v ∉ B := by rw [hBmem]; exact fun h => h.2.1 hvCx simp [hvC, hvB, hvCy, hvx, hvy] · 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 intro h; rw [h] at hvPy; exact hvPy hxy.symm have hvy : v ≠ y := by intro h; rw [h] at hvPx; 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 [hvPy, hvx, hvy, hvB, hvC]
add_nonneg- The sum a + b of two nonnegative elements is nonnegative.
div_eq_mul_inv- Division a / b is definitionally multiplication by the inverse a * b⁻¹.
div_le_div_of_nonneg_left- If 0 ≤ a and 0 < c ≤ b, then dividing a by b reverses the inequality: a / b ≤ a / c.
div_le_iff₀- For c > 0, b / c ≤ a if and only if b ≤ a * c.
div_nonneg- The quotient a / b of nonnegative elements is nonnegative.
Finset.card_pos.mp- A finite set is nonempty if and only if its cardinality is strictly positive (card > 0 implies nonempty).
Finset.card_pos.mpr- A finite set is nonempty if and only if its cardinality is strictly positive (nonempty implies card > 0).
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
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 belongs to s or to t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
Finset.nonempty_iff_ne_empty.mpr- A finset is nonempty if and only if it is not equal to the empty set.
Finset.sum_add_distrib- The sum of f(x) + g(x) over a finset equals the sum of f plus the sum of g.
Finset.sum_congr- Two sums over equal finsets are equal if their summands agree on all elements.
Finset.sum_const- The sum of a constant value b over a finset s equals |s| • b.
Finset.sum_div- Summing f(i) / a over a finset equals (∑ i, f(i)) / a.
Finset.sum_filter- Summing a function over elements satisfying a predicate equals summing the if-then-else expression over the whole finset.
Finset.sum_insert- Inserting an element a ∉ s into a finset adds f(a) to the sum of f over s.
Finset.sum_ite_mem- Summing an indicator for membership in t over s equals the sum over s ∩ t.
Finset.univ_inter- The intersection of the universal finset univ with any finset s is s.
if_false- An if-then-else expression with a false condition simplifies to the else branch.
if_pos- An if-then-else expression whose condition is proved simplifies to the then branch.
if_true- An if-then-else expression with condition True simplifies to the then branch.
lt_of_lt_of_le- Strict inequality is transitive with non-strict inequality: a < b and b ≤ c imply a < c.
mul_comm- Multiplication in a commutative magma is commutative: a * b = b * a.
ne_of_gt- If b < a, then a ≠ b.
nsmul_eq_mul- Natural-number scalar multiplication n • a equals the cast product (n : α) * a in a semiring.
SimpleGraph.degree_pos_iff_exists_adj- A vertex in a simple graph has degree > 0 if and only if it has at least one adjacent neighbour.
- The proof relies on automated tactics: `ring` and `field_simp` verify the algebraic mass-conservation identity from the graph degree formulas, `linarith` and `omega` handle degree and cardinality inequalities, and `tauto` verifies the vertex partition disjunction.
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.
/-- The main plan is nonnegative and has the prescribed marginals. -/theorem graph_idle_transport_plan_main_marginals {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y) (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) (hab : A.card ≤ B.card) : (∀ u v, 0 ≤ graph_idle_transport_plan_main G x y A B C u v) ∧ (∀ u, ∑ v, graph_idle_transport_plan_main G x y A B C u v = graph_idle_measure G (1/2) x u) ∧ (∀ v, ∑ u, graph_idle_transport_plan_main G x y A B C u v = graph_idle_measure G (1/2) y v) := by classical have hdxpos : (0:ℝ) < (G.degree x : ℝ) := by have : 0 < G.degree x := by rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨y, hxy⟩ exact_mod_cast this have hγβ : (1/2)/(G.degree y : ℝ) ≤ (1/2)/(G.degree x : ℝ) := by have hleR : (G.degree x : ℝ) ≤ (G.degree y : ℝ) := by exact_mod_cast hle exact div_le_div_of_nonneg_left (by norm_num) hdxpos hleR have hβle : (1/2)/(G.degree x : ℝ) ≤ 1/2 := by rw [div_le_iff₀ hdxpos] have h1 : (1:ℝ) ≤ (G.degree x : ℝ) := by have : 0 < G.degree x := by rw [SimpleGraph.degree_pos_iff_exists_adj]; exact ⟨y, hxy⟩ exact_mod_cast this linarith have hABcard : A.card ≤ B.card := hab have hBempty_beta : B = ∅ → (1/2)/(G.degree x : ℝ) = (1/2)/(G.degree y : ℝ) := by intro hB have hB0 : B.card = 0 := by rw [hB]; simp have hA0 : A.card = 0 := by omega have hdeg : G.degree x = G.degree y := by rw [hdx, hdy, hA0, hB0] rw [hdeg] have hBne_of_memA : ∀ u : V, u ∈ A → B.Nonempty := by intro u hu have hApos : 0 < A.card := Finset.card_pos.mpr ⟨u, hu⟩ exact Finset.card_pos.mp (lt_of_lt_of_le hApos hABcard) have hu_cases : ∀ u : V, u = x ∨ u = y ∨ u ∈ A ∨ u ∈ B ∨ u ∈ C ∨ u ∈ P := by intro u have h : u ∈ (Finset.univ : Finset V) := Finset.mem_univ u rw [hcover] at h simp only [Finset.mem_union, Finset.mem_singleton] at h tauto have hxnotC : x ∉ C := by rw [hCmem]; simp have hdisj : ∀ u : V, u ∈ A → ¬ (u = x ∨ u ∈ C) := by intro u huA hP have hm := (hAmem u).mp huA have huAny : ¬ G.Adj y u := hm.2.1 rcases hP with h | h · rw [h] at huAny; exact huAny hxy.symm · exact huAny ((hCmem u).mp h).2 have hfilter : (Finset.univ.filter (fun u : V => u = x ∨ u ∈ C)) = insert x C := by ext u simp [Finset.mem_insert] have hPsum : (∑ u : V, (if (u = x ∨ u ∈ C) then (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) else 0)) = ((C.card:ℝ)+1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) := by rw [← Finset.sum_filter] rw [hfilter] rw [Finset.sum_insert hxnotC] rw [Finset.sum_const, nsmul_eq_mul] ring have hAsum : (∑ u : V, (if u ∈ A then (1/2)/(G.degree x : ℝ) else 0)) = (A.card:ℝ) * ((1/2)/(G.degree x : ℝ)) := by rw [← Finset.sum_filter] have hf : (Finset.univ.filter (fun u : V => u ∈ A)) = A := by ext u; simp rw [hf, Finset.sum_const, nsmul_eq_mul] have hkey : (A.card : ℝ) * ((1/2)/(G.degree x : ℝ)) + ((C.card : ℝ) + 1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) = (B.card : ℝ) * ((1/2)/(G.degree y : ℝ)) := by have hdxR : (G.degree x : ℝ) = (A.card : ℝ) + (C.card : ℝ) + 1 := by rw [hdx]; push_cast; ring have hdyR : (G.degree y : ℝ) = (B.card : ℝ) + (C.card : ℝ) + 1 := by rw [hdy]; push_cast; ring rw [hdxR, hdyR] field_simp ring have hpoint : ∀ u : V, (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) = (if (u = x ∨ 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 intro u by_cases hP : u = x ∨ u ∈ C · have hAn : u ∉ A := fun hA => hdisj u hA hP simp [hP, hAn] · by_cases hA : u ∈ A · simp [hP, hA] · simp [hP, hA] have hsum : (∑ u : V, (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)) = (B.card:ℝ) * ((1/2)/(G.degree y : ℝ)) := by calc (∑ u : V, (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)) = ∑ u : V, ((if (u = x ∨ 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 apply Finset.sum_congr rfl; intro u _; exact hpoint u _ = (∑ u : V, (if (u = x ∨ u ∈ C) then (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) else 0)) + (∑ u : V, (if u ∈ A then (1/2)/(G.degree x : ℝ) else 0)) := by rw [Finset.sum_add_distrib] _ = ((C.card:ℝ)+1) * ((1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ)) + (A.card:ℝ) * ((1/2)/(G.degree x : ℝ)) := by rw [hPsum, hAsum] _ = (B.card:ℝ) * ((1/2)/(G.degree y : ℝ)) := by linarith [hkey] refine ⟨?_, ?_, ?_⟩ · intro u v have hγnn : (0:ℝ) ≤ (1/2)/(G.degree y : ℝ) := div_nonneg (by norm_num) (by positivity) have hβnn : (0:ℝ) ≤ (1/2)/(G.degree x : ℝ) := div_nonneg (by norm_num) (by positivity) have hβγnn : (0:ℝ) ≤ (1/2)/(G.degree x : ℝ) - (1/2)/(G.degree y : ℝ) := by linarith simp only [graph_idle_transport_plan_main] apply add_nonneg apply add_nonneg apply add_nonneg · by_cases h : u = x ∧ v = x · simp only [h, if_true]; exact hγnn · simp [h] · by_cases hvy : v = y · simp only [hvy, if_true] by_cases hux : u = x · simp only [hux, if_true]; linarith · simp only [hux, if_false] by_cases huy : u = y · simp only [huy, if_true]; exact hβnn · simp [huy] · simp [hvy] · by_cases h : u = v · rw [if_pos h] by_cases hC : u ∈ C · simp only [hC, if_true]; exact hγnn · simp [hC] · simp [h] · by_cases hB : v ∈ B · simp only [hB, if_true] by_cases hP : u = x ∨ u ∈ C · simp only [hP, if_true]; exact div_nonneg hβγnn (by positivity) · simp only [hP, if_false] by_cases hA : u ∈ A · simp only [hA, if_true]; exact div_nonneg hβnn (by positivity) · simp [hA] · simp [hB] · intro u have e1 : (∑ v, (if u = x ∧ v = x then (1/2)/(G.degree y : ℝ) else 0)) = (if u = x then (1/2)/(G.degree y : ℝ) else 0) := by by_cases h : u = x · subst h; simp · simp [h] have e2 : (∑ 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 then 1/2 - (1/2)/(G.degree x : ℝ) else if u = y then (1/2)/(G.degree x : ℝ) else 0) := by simp have e3 : (∑ v, (if u = v then (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) else 0)) = (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) := by simp have e4 : (∑ v, (if v ∈ B then (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) / (B.card : ℝ) else 0)) = if B.Nonempty then (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) else 0 := by rw [Finset.sum_ite_mem] simp only [Finset.univ_inter] by_cases h : B = ∅ · subst h; simp · have hc : (B.card : ℝ) ≠ 0 := by have : 0 < B.card := Finset.card_pos.mpr (Finset.nonempty_iff_ne_empty.mpr h) exact_mod_cast ne_of_gt this rw [Finset.sum_const, nsmul_eq_mul] simp [h, hc, div_eq_mul_inv, mul_comm] simp only [graph_idle_transport_plan_main, Finset.sum_add_distrib] rw [e1, e2, e3, e4] simp only [graph_idle_measure] rw [show (1:ℝ) - 1/2 = 1/2 by norm_num] rcases hu_cases u with hux | huy | huA | huB | huC | huP · rw [hux] at * have hxC : x ∉ C := by rw [hCmem]; simp by_cases hB : B = ∅ · have hβγ := hBempty_beta hB simp [hB, hxC] linarith · have hBne : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB simp [hBne, hxC] <;> ring · rw [huy] at * have hyC : y ∉ C := by rw [hCmem]; simp have hyA : y ∉ A := by rw [hAmem]; simp by_cases hBne : B.Nonempty · simp [hBne, hxy, hxy.ne.symm, hyC, hyA] <;> ring · simp [hBne, hxy, hxy.ne.symm, hyC, hyA] <;> ring · have hBne : B.Nonempty := hBne_of_memA u huA 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 intro h; subst h; exact huAny hxy.symm have huC : u ∉ C := by rw [hCmem]; exact fun h => huAny h.2 simp [huA, hBne, huC, hux, huy, huAx] <;> ring · have huBne : B.Nonempty := ⟨u, huB⟩ 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 intro h; subst h; 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 [huBne, huBnx, huA, huC, hux, huy] <;> ring · have hCm := (hCmem u).mp huC have huCx : G.Adj x u := hCm.1 have huCy : G.Adj y u := hCm.2 have hux : u ≠ x := by intro h; subst h; exact G.irrefl huCx have huy : u ≠ y := by intro h; subst h; exact G.irrefl huCy by_cases hB : B = ∅ · have hβγ := hBempty_beta hB simp [hB, huC, hux, huy, huCx] linarith · have hBne : B.Nonempty := Finset.nonempty_iff_ne_empty.mpr hB simp [hBne, huC, hux, huy, huCx] <;> ring · 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 intro h; subst h; exact huPy hxy.symm have huy : u ≠ y := by intro h; subst h; 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 by_cases hBne : B.Nonempty · simp [hBne, huPx, huA, huC, hux, huy] <;> ring · simp [hBne, huPx, huA, huC, hux, huy] <;> ring · intro v have c1 : (∑ u, (if u = x ∧ v = x then (1/2)/(G.degree y : ℝ) else 0)) = if v = x then (1/2)/(G.degree y : ℝ) else 0 := by by_cases hv : v = x · rw [hv]; simp · simp [hv] have c2 : (∑ u, (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 v = y then 1/2 else 0 := by by_cases hv : v = y · rw [hv] have hne : x ≠ y := hxy.ne have step : ∑ u : V, (if u = x then 1/2 - (1/2)/(G.degree x : ℝ) else if u = y then (1/2)/(G.degree x : ℝ) else 0) = (∑ u, (if u = x then 1/2 - (1/2)/(G.degree x : ℝ) else 0)) + ∑ u, (if u = y then (1/2)/(G.degree x : ℝ) else 0) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u _ by_cases h1 : u = x · subst h1; simp [hne] · by_cases h2 : u = y · subst h2; simp [h1] · simp [h1, h2] simp only [if_true] rw [step] simp · simp [hv] have c3 : (∑ u, (if u = v then (if u ∈ C then (1/2)/(G.degree y : ℝ) else 0) else 0)) = (if v ∈ C then (1/2)/(G.degree y : ℝ) else 0) := by simp have c4 : (∑ u, (if v ∈ B then (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) / (B.card : ℝ) else 0)) = if v ∈ B then (1/2)/(G.degree y : ℝ) else 0 := by by_cases hv : v ∈ B · simp only [hv, if_true] rw [← Finset.sum_div, hsum] have hBpos : 0 < B.card := Finset.card_pos.mpr ⟨v, hv⟩ have hBc : (B.card : ℝ) ≠ 0 := by exact_mod_cast ne_of_gt hBpos field_simp · simp [hv] simp only [graph_idle_transport_plan_main, Finset.sum_add_distrib] rw [c1, c2, c3, c4] simp only [graph_idle_measure] rw [show (1:ℝ) - 1/2 = 1/2 by norm_num] rcases hu_cases v with hvx | hvy | hvA | hvB | hvC | hvP · rw [hvx] at * have hxB : x ∉ B := by rw [hBmem]; simp simp [hxnotC, hxB, hxy.ne, hxy.symm] · rw [hvy] at * have hyC : y ∉ C := by rw [hCmem]; simp have hyB : y ∉ B := by rw [hBmem]; simp simp [hyC, hyB, hxy.ne.symm] · have hm := (hAmem v).mp hvA have hvAny : ¬G.Adj y v := hm.2.1 have hvy : v ≠ y := hm.2.2 have hvx : v ≠ x := by intro h; rw [h] at hm; 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 [hvAny, hvx, hvy, hvB, hvC] · 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 intro h; rw [h] at hvBy; exact G.irrefl hvBy have hvC : v ∉ C := by rw [hCmem]; exact fun h => hvBnx h.1 simp [hvB, hvBy, hvx, hvy, hvC] · 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 intro h; rw [h] at hvCx; exact G.irrefl hvCx have hvy : v ≠ y := by intro h; rw [h] at hvCy; exact G.irrefl hvCy have hvB : v ∉ B := by rw [hBmem]; exact fun h => h.2.1 hvCx simp [hvC, hvB, hvCy, hvx, hvy] · 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 intro h; rw [h] at hvPy; exact hvPy hxy.symm have hvy : v ≠ y := by intro h; rw [h] at hvPx; 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 [hvPy, hvx, hvy, hvB, hvC]