Distinguishability of infinite groups and graphs

<p>The distinguishing number of a group G acting faithfully on a set V is the least number of colors needed to color the elements of V so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph Gamma is said to have connectivity 1 if there exists a vertex alpha \in V\Gamma such that Gamma \setminus \{\alpha\} is not connected. For alpha \in V, an orbit of the point stabilizer G_\alpha is called a suborbit of G.We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number 2. Consequently, any nonnull, infinite, primitive, locally finite graph is 2-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number 2.All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.</p>