A probabilistic definition of groups with Kazhdan's property (T), due to Glasner  & Weiss (1997), is that on any Cayley graph G of the group, for any ergodic group-invariant random black-and-white colouring of the vertices, with the density of each colour bounded away from 0, the density of edges connecting black to white vertices remains bounded away from zero. Amenable groups and free groups do not have property (T), while SL_d(\Z) with d\geq 3 do. The cost of a transitive graph is one half of the infimum of the expected degree of invariant connected spanning subgraphs. Amenable transitive graphs and Cayley graphs of SL_d(\Z) with d\geq 3 have cost 1, while any Cayley graph of the free group on d generators has cost d, by Gaboriau (2000). A question of Gaboriau aims to connect cost with the first L^2-Betti number of groups. For Kazhdan groups, the latter has been known to be 0 since Bekka & Valette (1997), and Gaboriau's question then suggests that the cost of any Kazhdan Cayley graph should be 1. This is what we prove, in joint work with Tom Hutchcroft (Cambridge).