The Harris-Luck criterion judges the relevance of (potentially) spatially correlated, quenched disorder induced by, e.g., random bonds, randomly diluted sites, or a quasiperiodicity of the lattice, for altering the critical behavior of a coupled matter system. We investigate the applicability of this type of criterion to the case of spin variables coupled to random lattices. Their aptitude to alter critical behavior depends on the degree of spatial correlations present, which is quantified by a wandering exponent. We consider the cases of Poissonian random graphs resulting from the Voronoï-Delaunay construction and of planar, “fat” φ3 Feynman diagrams and precisely determine their wandering exponents. The resulting predictions are compared to various exact and numerical results for the Potts model coupled to these quenched ensembles of random graphs.