AFTD Auto-Formalizing Theoretical Domains

graph_idle_wasserstein_lt_one_of_edge_partition

theoremverified

Given 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 endpoints of the edge are at Wasserstein distance less than 1.

Statement

theorem graph_idle_wasserstein_lt_one_of_edge_partition {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)
    (hdiam : G.ediam ≤ 2)
    (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ))
    (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)
    (hn : Fintype.card V = 2 + A.card + B.card + C.card + P.card) :
    graph_wasserstein_dist G (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y) < 1
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 14
Used by 1

The proof, explained

The theorem proves that on a graph of diameter at most 2 with minimum degree at least 2n/3 - 1, the Wasserstein distance between the idleness-1/2 measures at the endpoints of an edge xy is strictly less than 1, implying positive Ollivier-Ricci curvature. By symmetry, it suffices to consider the case d(x) ≤ d(y), where the minimum degree condition constrains the edge partition to |B| ≤ |C| + 2. In the interior case |B| ≤ |C| + 1 and the boundary subcase |B| = |C| + 2 with d(x) < d(y), a canonical transport plan is shown to achieve transportation cost strictly below 1. In the extremal subcase |B| = |C| + 2 with d(x) = d(y), the graph possesses an edge between A and B, which allows a specialized transport plan that also achieves cost strictly less than 1.

  1. Under the degree assumption d(x) ≤ d(y), the degree of x is positive, |A| ≤ |B|, and |B| ≤ |C| + 2.

    Since d(x) = |A| + |C| + 1, linear arithmetic gives d(x) ≥ 1. Comparing d(x) = |A| + |C| + 1 with d(y) = |B| + |C| + 1 given d(x) ≤ d(y) immediately implies |A| ≤ |B|. The key structural bound |B| ≤ |C| + 2 is supplied by `graph_min_degree_edge_partition_b_card_le` using the minimum degree condition δ(G) ≥ 2n/3 - 1.

    lines 16–19

    uses graph_min_degree_edge_partition_b_card_le

      have hpos_dx : 1 ≤ G.degree x := by omega
      have hab : A.card ≤ B.card := by omega
      have hb_le : B.card ≤ C.card + 2 :=
        graph_min_degree_edge_partition_b_card_le G hδ x y A B C P hdx hdy hn
  2. In the boundary case |B| = |C| + 2 with equal degrees d(x) = d(y), the Wasserstein distance between the idle measures is strictly less than 1.

    We split on whether |B| = |C| + 2 or |B| < |C| + 2, and further subcase on d(x) = d(y) versus d(x) < d(y). When |B| = |C| + 2 and d(x) = d(y), `graph_edge_partition_special_structure` reveals a rigid graph configuration: P = ∅, |A| = |B|, and there is an edge between A and B, which also implies |A| ≥ 1. This configuration allows `graph_idle_transport_plan_special` to construct a specialized transport plan π whose total cost is at most 1/2 + 2(|A| - 1)(1/2 / d(y)). By `graph_wasserstein_dist_le_of_plan`, the Wasserstein distance is bounded by the cost of π, and `graph_idle_special_cost_lt_one` verifies that this upper bound is strictly less than 1.

    lines 20–34

    uses eq_or_lt_of_le, graph_edge_partition_special_structure, graph_idle_transport_plan_special, graph_wasserstein_dist_le_of_plan, graph_idle_special_cost_lt_one, lt_of_le_of_lt

      rcases eq_or_lt_of_le hb_le with hb_eq | hb_lt
      · -- Case B.card = C.card + 2
        rcases eq_or_lt_of_le hle with heq | hlt
        · -- Subcase G.degree x = G.degree y
          have hspec := graph_edge_partition_special_structure G hδ x y A B C P
            hAmem hBmem hCmem hPmem hcover hdx hdy hn heq hb_eq
          rcases hspec with ⟨-, hAB, hadj⟩
          have hne : 1 ≤ A.card := by omega
          obtain ⟨π, hπ_nonneg, hπ_row, hπ_col, hπ_cost⟩ :=
            graph_idle_transport_plan_special G x y hxy hdiam A B C P
              hAmem hBmem hCmem hPmem hcover hdx hdy hAB hne hadj
          have hdist_le := graph_wasserstein_dist_le_of_plan G
            (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y) π hπ_nonneg hπ_row hπ_col
          have hcost_lt := graph_idle_special_cost_lt_one A.card B.card C.card (G.degree y) hAB hb_eq hdy
          exact lt_of_le_of_lt (hdist_le.trans hπ_cost) hcost_lt
  3. In the boundary case |B| = |C| + 2 with strict inequality d(x) < d(y), the Wasserstein distance is strictly less than 1.

    When d(x) < d(y), we employ the standard idle transport plan `graph_idle_transport_plan_main`. Lemma `graph_idle_transport_plan_main_marginals` proves it is non-negative and has the correct marginal measures, while `graph_idle_transport_plan_main_cost` bounds its cost by 1/2 - 1/(2 d(x)) + |B| / d(y). Since d(x) < d(y) and |B| = |C| + 2, the arithmetic lemma `graph_idle_plan_cost_lt_one_boundary` shows this cost bound is strictly less than 1, yielding W < 1 via `graph_wasserstein_dist_le_of_plan`.

    lines 35–46

    uses graph_idle_transport_plan_main_marginals, graph_idle_transport_plan_main_cost, graph_wasserstein_dist_le_of_plan, graph_idle_plan_cost_lt_one_boundary, lt_of_le_of_lt

        · -- Subcase G.degree x < G.degree y
          obtain ⟨hπ_nonneg, hπ_row, hπ_col⟩ :=
            graph_idle_transport_plan_main_marginals G x y hxy A B C P
              hAmem hBmem hCmem hPmem hcover hdx hdy hle hab
          have hcost_le := graph_idle_transport_plan_main_cost G x y hxy hdiam A B C P
            hAmem hBmem hCmem hPmem hcover hdx hdy hle
          have hdist_le := graph_wasserstein_dist_le_of_plan G
            (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y)
            (graph_idle_transport_plan_main G x y A B C) hπ_nonneg hπ_row hπ_col
          have hcost_lt := graph_idle_plan_cost_lt_one_boundary
            (G.degree x) (G.degree y) A.card B.card C.card hpos_dx hlt hdx hdy hb_eq
          exact lt_of_le_of_lt (hdist_le.trans hcost_le) hcost_lt
  4. In the non-boundary case |B| ≤ |C| + 1, the Wasserstein distance is strictly less than 1.

    If |B| < |C| + 2, then |B| ≤ |C| + 1. The standard transport plan again provides valid marginals and has cost bounded by 1/2 - 1/(2 d(x)) + |B| / d(y). Because d(x) ≤ d(y) and |B| ≤ |C| + 1, `graph_idle_plan_cost_lt_one` proves the cost is strictly less than 1, completing the proof of the auxiliary lemma.

    lines 47–59

    uses graph_idle_transport_plan_main_marginals, graph_idle_transport_plan_main_cost, graph_wasserstein_dist_le_of_plan, graph_idle_plan_cost_lt_one, lt_of_le_of_lt

      · -- Case B.card ≤ C.card + 1
        have hb_le' : B.card ≤ C.card + 1 := by omega
        obtain ⟨hπ_nonneg, hπ_row, hπ_col⟩ :=
          graph_idle_transport_plan_main_marginals G x y hxy A B C P
            hAmem hBmem hCmem hPmem hcover hdx hdy hle hab
        have hcost_le := graph_idle_transport_plan_main_cost G x y hxy hdiam A B C P
          hAmem hBmem hCmem hPmem hcover hdx hdy hle
        have hdist_le := graph_wasserstein_dist_le_of_plan G
          (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y)
          (graph_idle_transport_plan_main G x y A B C) hπ_nonneg hπ_row hπ_col
        have hcost_lt := graph_idle_plan_cost_lt_one
          (G.degree x) (G.degree y) A.card B.card C.card hpos_dx hle hdx hdy hb_le'
        exact lt_of_le_of_lt (hdist_le.trans hcost_le) hcost_lt
  5. When d(x) ≤ d(y), the main theorem follows directly from the auxiliary lemma.

    By totality of the ordering on natural numbers (`le_total`), either d(x) ≤ d(y) or d(y) ≤ d(x). If d(x) ≤ d(y), the auxiliary lemma `graph_idle_wasserstein_lt_one_of_edge_partition_aux` applies immediately.

    lines 76–78

    uses le_total, graph_idle_wasserstein_lt_one_of_edge_partition_aux

      rcases le_total (G.degree x) (G.degree y) with hle | hle
      · exact graph_idle_wasserstein_lt_one_of_edge_partition_aux G x y hxy hdiam hδ
          A B C P hAmem hBmem hCmem hPmem hcover hdx hdy hn hle
  6. When d(y) ≤ d(x), the main theorem follows by swapping the roles of x and y.

    By symmetry of the Wasserstein distance (`graph_wasserstein_dist_comm`), W(μ_x^{1/2}, μ_y^{1/2}) = W(μ_y^{1/2}, μ_x^{1/2}). Swapping x and y exchanges the partition sets A and B, while C and P are symmetric by commutativity of conjunction (`and_comm`). After reordering the partition union using set membership rules (`Finset.mem_union`, `Finset.mem_singleton`), the auxiliary lemma `graph_idle_wasserstein_lt_one_of_edge_partition_aux` applies to the edge (y, x).

    lines 79–94

    uses graph_wasserstein_dist_comm, Finset.mem_union, Finset.mem_singleton, and_comm, graph_idle_wasserstein_lt_one_of_edge_partition_aux

      · rw [graph_wasserstein_dist_comm]
        have hcover_swap : (Finset.univ : Finset V) = {y} ∪ {x} ∪ B ∪ A ∪ C ∪ P := by
          rw [hcover]
          ext v
          simp only [Finset.mem_union, Finset.mem_singleton]
          tauto
        have hCmem_swap : ∀ v, v ∈ C ↔ (G.Adj y v ∧ G.Adj x v) := by
          intro v
          rw [hCmem, and_comm]
        have hPmem_swap : ∀ v, v ∈ P ↔ (¬ G.Adj y v ∧ ¬ G.Adj x v) := by
          intro v
          rw [hPmem, and_comm]
        have hn_swap : Fintype.card V = 2 + B.card + A.card + C.card + P.card := by
          omega
        exact graph_idle_wasserstein_lt_one_of_edge_partition_aux G y x hxy.symm hdiam hδ
          B A C P hBmem hAmem hCmem_swap hPmem_swap hcover_swap hdy hdx hn_swap hle
graph_min_degree_edge_partition_b_card_le
In an edge partition of a graph with minimum degree at least 2n/3 - 1, the number of neighbors exclusive to y is at most the number of common neighbors plus 2 (|B| ≤ |C| + 2).
eq_or_lt_of_le
If a ≤ b in a partial order, then either a = b or a < b.
graph_edge_partition_special_structure
When min-degree is at least 2n/3 - 1, d(x) = d(y), and |B| = |C| + 2, the graph has no non-neighbors (P = ∅), |A| = |B|, and there is an edge between A and B.
graph_idle_transport_plan_special
In a diameter at most 2 graph with |A| = |B| ≥ 1 and an edge between A and B, there is a transport plan between idleness-1/2 measures at x and y with cost at most 1/2 + 2(|A| - 1)(1/2 / d(y)).
graph_wasserstein_dist_le_of_plan
The Wasserstein distance between two probability measures on a graph is bounded above by the total cost of any valid transport plan between them.
graph_idle_special_cost_lt_one
If a = b = c + 2 and dy = b + c + 1, then 1/2 + 2(a - 1)(1/2 / dy) < 1.
lt_of_le_of_lt
If a ≤ b and b < c in a preorder, then a < c.
graph_idle_transport_plan_main_marginals
When d(x) ≤ d(y) and |A| ≤ |B|, the standard idle transport plan is non-negative and has row and column sums matching the idleness-1/2 measures at x and y.
graph_idle_transport_plan_main_cost
In a graph of diameter at most 2 with d(x) ≤ d(y), the standard idle transport plan has cost at most 1/2 - 1/(2 d(x)) + |B| / d(y).
graph_idle_plan_cost_lt_one_boundary
If 1 ≤ dx < dy with dx = a + c + 1, dy = b + c + 1, and b = c + 2, then 1/2 - 1/(2 dx) + b / dy < 1.
graph_idle_plan_cost_lt_one
If 1 ≤ dx ≤ dy with dx = a + c + 1, dy = b + c + 1, and b ≤ c + 1, then 1/2 - 1/(2 dx) + b / dy < 1.
le_total
In a linear order, any two elements are comparable: a ≤ b or b ≤ a.
graph_idle_wasserstein_lt_one_of_edge_partition_aux
Under the edge partition assumptions with diameter at most 2 and min-degree at least 2n/3 - 1, if d(x) ≤ d(y) then W(μ_x^{1/2}, μ_y^{1/2}) < 1.
graph_wasserstein_dist_comm
The graph Wasserstein distance is symmetric in its two argument measures.
Finset.mem_union
An element belongs to a union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_singleton
An element belongs to a singleton set {a} if and only if it is equal to a.
and_comm
Logical conjunction is commutative: a ∧ b is equivalent to b ∧ a.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma graph_idle_wasserstein_lt_one_of_edge_partition_aux {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)    (hdiam : G.ediam ≤ 2)    (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ))    (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)    (hn : Fintype.card V = 2 + A.card + B.card + C.card + P.card)    (hle : G.degree x ≤ G.degree y) :    graph_wasserstein_dist G (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y) < 1 := by  have hpos_dx : 1 ≤ G.degree x := by omega  have hab : A.card ≤ B.card := by omega  have hb_le : B.card ≤ C.card + 2 :=    graph_min_degree_edge_partition_b_card_le G hδ x y A B C P hdx hdy hn  rcases eq_or_lt_of_le hb_le with hb_eq | hb_lt  · -- Case B.card = C.card + 2    rcases eq_or_lt_of_le hle with heq | hlt    · -- Subcase G.degree x = G.degree y      have hspec := graph_edge_partition_special_structure G hδ x y A B C P        hAmem hBmem hCmem hPmem hcover hdx hdy hn heq hb_eq      rcases hspec with ⟨-, hAB, hadj⟩      have hne : 1 ≤ A.card := by omega      obtain ⟨π, hπ_nonneg, hπ_row, hπ_col, hπ_cost⟩ :=        graph_idle_transport_plan_special G x y hxy hdiam A B C P          hAmem hBmem hCmem hPmem hcover hdx hdy hAB hne hadj      have hdist_le := graph_wasserstein_dist_le_of_plan G        (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y) π hπ_nonneg hπ_row hπ_col      have hcost_lt := graph_idle_special_cost_lt_one A.card B.card C.card (G.degree y) hAB hb_eq hdy      exact lt_of_le_of_lt (hdist_le.trans hπ_cost) hcost_lt    · -- Subcase G.degree x < G.degree y      obtain ⟨hπ_nonneg, hπ_row, hπ_col⟩ :=        graph_idle_transport_plan_main_marginals G x y hxy A B C P          hAmem hBmem hCmem hPmem hcover hdx hdy hle hab      have hcost_le := graph_idle_transport_plan_main_cost G x y hxy hdiam A B C P        hAmem hBmem hCmem hPmem hcover hdx hdy hle      have hdist_le := graph_wasserstein_dist_le_of_plan G        (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y)        (graph_idle_transport_plan_main G x y A B C) hπ_nonneg hπ_row hπ_col      have hcost_lt := graph_idle_plan_cost_lt_one_boundary        (G.degree x) (G.degree y) A.card B.card C.card hpos_dx hlt hdx hdy hb_eq      exact lt_of_le_of_lt (hdist_le.trans hcost_le) hcost_lt  · -- Case B.card ≤ C.card + 1    have hb_le' : B.card ≤ C.card + 1 := by omega    obtain ⟨hπ_nonneg, hπ_row, hπ_col⟩ :=      graph_idle_transport_plan_main_marginals G x y hxy A B C P        hAmem hBmem hCmem hPmem hcover hdx hdy hle hab    have hcost_le := graph_idle_transport_plan_main_cost G x y hxy hdiam A B C P      hAmem hBmem hCmem hPmem hcover hdx hdy hle    have hdist_le := graph_wasserstein_dist_le_of_plan G      (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y)      (graph_idle_transport_plan_main G x y A B C) hπ_nonneg hπ_row hπ_col    have hcost_lt := graph_idle_plan_cost_lt_one      (G.degree x) (G.degree y) A.card B.card C.card hpos_dx hle hdx hdy hb_le'    exact lt_of_le_of_lt (hdist_le.trans hcost_le) hcost_lt/-- Assembly: for an edge partition of a diameter-2 graph with min degree at least 2n/3 - 1, W(μ_x^{1/2}, μ_y^{1/2}) < 1. -/theorem graph_idle_wasserstein_lt_one_of_edge_partition {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (hxy : G.Adj x y)    (hdiam : G.ediam ≤ 2)    (hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ))    (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)    (hn : Fintype.card V = 2 + A.card + B.card + C.card + P.card) :    graph_wasserstein_dist G (graph_idle_measure G (1/2) x) (graph_idle_measure G (1/2) y) < 1 := by  rcases le_total (G.degree x) (G.degree y) with hle | hle  · exact graph_idle_wasserstein_lt_one_of_edge_partition_aux G x y hxy hdiam hδ      A B C P hAmem hBmem hCmem hPmem hcover hdx hdy hn hle  · rw [graph_wasserstein_dist_comm]    have hcover_swap : (Finset.univ : Finset V) = {y} ∪ {x} ∪ B ∪ A ∪ C ∪ P := by      rw [hcover]      ext v      simp only [Finset.mem_union, Finset.mem_singleton]      tauto    have hCmem_swap : ∀ v, v ∈ C ↔ (G.Adj y v ∧ G.Adj x v) := by      intro v      rw [hCmem, and_comm]    have hPmem_swap : ∀ v, v ∈ P ↔ (¬ G.Adj y v ∧ ¬ G.Adj x v) := by      intro v      rw [hPmem, and_comm]    have hn_swap : Fintype.card V = 2 + B.card + A.card + C.card + P.card := by      omega    exact graph_idle_wasserstein_lt_one_of_edge_partition_aux G y x hxy.symm hdiam hδ      B A C P hBmem hAmem hCmem_swap hPmem_swap hcover_swap hdy hdx hn_swap hle
See it in the graphDiscuss this resultChallenge it