Distinguishability of infinite groups and graphs (Q426906)

Summary: 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.