graph_wasserstein_dist_comm
The Wasserstein distance is symmetric: W(μ, ν) = W(ν, μ).
Statement
theorem graph_wasserstein_dist_comm {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) : graph_wasserstein_dist G μ ν = graph_wasserstein_dist G ν μ
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- Used by 2
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- 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 Wasserstein distance W(μ, ν) is the infimum of transport costs ∑ a, ∑ b, d(a, b) π(a, b) over all couplings π with marginals μ and ν. The proof shows symmetry by proving that the sets of achievable transport costs for (μ, ν) and (ν, μ) are identical. For any coupling π, its transpose π'(a, b) = π(b, a) is a valid coupling for the swapped marginals with the exact same cost, since the graph distance is symmetric and the order of finite summation can be exchanged.
The equality of Wasserstein distances reduces to showing that a transport cost c is achievable between μ and ν if and only if it is achievable between ν and μ.
Unfolding the definition of the Wasserstein distance expresses each side as the infimum of the set of costs achievable by valid couplings. Congruence reduces equality of infima to equality of the underlying sets, which by set extensionality reduces to proving a bi-implication for any given cost c.
unfold graph_wasserstein_dist congr 1 ext c constructor
Any transport cost achievable between μ and ν is also achievable between ν and μ.
Given a coupling π from μ to ν with cost c, consider the transposed coupling π'(a, b) = π(b, a). Transposing π swaps the row and column marginals, making π' a valid coupling from ν to μ. Exchanging the order of summation via Finset.sum_comm and using the symmetry of the graph metric via SimpleGraph.dist_comm shows that the transport cost of π' is identically c.
uses
Finset.sum_comm,SimpleGraph.dist_comm· rintro ⟨π, h0, h1, h2, rfl⟩ refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩ rw [Finset.sum_comm] simp_rw [SimpleGraph.dist_comm]
Conversely, any transport cost achievable between ν and μ is also achievable between μ and ν.
By symmetry, given a coupling π from ν to μ, its transpose π'(a, b) = π(b, a) is a valid coupling from μ to ν achieving the same cost, again verified using Finset.sum_comm and SimpleGraph.dist_comm.
uses
Finset.sum_comm,SimpleGraph.dist_comm· rintro ⟨π, h0, h1, h2, rfl⟩ refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩ rw [Finset.sum_comm] simp_rw [SimpleGraph.dist_comm]
Finset.sum_comm- In a finite double sum, the order of summation can be exchanged: ∑ x ∈ s, ∑ y ∈ t, f(x, y) = ∑ y ∈ t, ∑ x ∈ s, f(x, y).
SimpleGraph.dist_comm- The shortest-path distance between vertices in a simple graph is symmetric: d(u, v) = d(v, u).
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.
theorem graph_wasserstein_dist_comm {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) : graph_wasserstein_dist G μ ν = graph_wasserstein_dist G ν μ := by unfold graph_wasserstein_dist congr 1 ext c constructor · rintro ⟨π, h0, h1, h2, rfl⟩ refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩ rw [Finset.sum_comm] simp_rw [SimpleGraph.dist_comm] · rintro ⟨π, h0, h1, h2, rfl⟩ refine ⟨fun a b => π b a, fun a b => h0 b a, h2, h1, ?_⟩ rw [Finset.sum_comm] simp_rw [SimpleGraph.dist_comm]