The Wasserstein metric over a metric space X is an optimal-transport based distance on the set of probability measures on X. Metric spaces for which the optimal transport problem is "easiest" to solve are trees,  in the sense that the Wasserstein metric on trees isometrically embeds into $L^1$. Property A is a coarse invariant of metric spaces introduced by Yu as an approach to solving the coarse Baum-Connes conjecture. We prove a new characterization of bounded degree graphs X with Property A as precisely those that are coarsely equivalent to another space Y whose Wasserstein metric admits a biLipschitz embedding into $L^1$. Applications to group actions on Banach spaces will be discussed. Based on joint work with Tianyi Zheng and Ignacio Vergara.