AFTD Auto-Formalizing Theoretical Domains

graph_idle_transport_plan_main_marginals

theoremverified

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

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.

  1. 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.

    lines 18–33

    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
  2. 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.

    lines 34–43

    uses Finset.card_pos.mpr, Finset.card_pos.mp, lt_of_lt_of_le

      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)
  3. 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).

    lines 44–57

    uses Finset.mem_univ, Finset.mem_union, Finset.mem_singleton

      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
  4. 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.

    lines 58–82

    uses Finset.mem_insert, Finset.sum_filter, Finset.sum_insert, Finset.sum_const, nsmul_eq_mul

      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
  5. 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.

    lines 83–107

    uses Finset.sum_congr, Finset.sum_add_distrib

      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]
  6. 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.

    lines 108–143

    uses div_nonneg, add_nonneg, if_true, if_false, if_pos

      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]
  7. 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.

    lines 144–174

    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]
  8. 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.

    lines 175–227

    uses Finset.nonempty_iff_ne_empty.mpr

        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
  9. 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.

    lines 228–272

    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]
  10. 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.

    lines 273–309

        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.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it