# Stabilizers, conjugacy classes and automorphism relations (graph theory)

I am trying to get through the proof of the following theorem:

Let $G = (V,E)$ be a locally finite, connected, infinite graph with linear growth and infinite motion. Then $G$ is 2-distinguishable.

In the proof of this theorem we claim that the stabilizer of every vertex $v\in V$ is finite and since the vertex set is countable, the stabilizer can only have countably many conjugacy classes and hence the automorphism group itself must be countable.

I don't quite understand that. Why can the stabilizer have only countably many conjugacy classes and how does that imply that the automorphism group must be countable?

Maybe I am missing some definitions here. The stabilizer of the element $s$ in the group $\Gamma$ is the set: $$\Gamma_s = \{ \gamma \in \Gamma : \gamma s = s \}$$ And the conjguacy class of an element $a$ in the group $G$ is a set, such that: $$Cl(a) = \{b \in G : \exists g \in G: b = gag^{-1}\}$$

We would like to get assumptions to use a following statement to prove our thesis.

Let $\Gamma$ be a group of permutations of a set $S$ and assume that $\Gamma$ has infinite motion. If $\Gamma$ is countable then there is $\Gamma$-distinguishing 2-colouring of $S$.

Could anyone explain that to me, please?

• If ${\rm Stab}(v)$ is finite then of course it has countably many conjugacy classes. Perhaps the author instead meant to write ${\rm Aut}(G)$ contains countably many subgroups conjugate to ${\rm Stab}(v)$? (This would follow from $V$ being countable since $g{\rm Stab}(v)g^{-1}={\rm Stab}(gv)$.) – anon May 19 '18 at 1:44
• Thank you for your reply and I am really sorry, but abstract algebra is not something what I am familiar with and it just turned out to be important. Still don't get that equation you've written. What happened with the $g^{-1}$, but I get that implies that $V$ is countable. Maybe it would be helpful if I said that we need to get following assumptions to use a theorem to get our thesis. Let $\Gamma$ be a group of permutations of a set $S$ and assume that $\Gamma$ has infinite motion. If $\Gamma$ is countable then there is $\Gamma$-distinguishing 2-colouring of $S$. – Dreeze May 19 '18 at 7:48
• Well, $\sigma v=v$ is equivalent to $(g\sigma g^{-1})(gv)=gv$, so $\sigma\in{\rm Stab}(v)$ is equivalent to $g\sigma g^{-1}\in{\rm Stab}(gv)$. Therefore $${\rm Stab}(gv)=\{ g\sigma g^{-1}\mid \sigma\in{\rm Stab}(v)\}=g{\rm Stab}(v)g^{-1}.$$ Also, I never said "implies that $V$ is countable" in my comment, I used the fact that $V$ was countable to conclude ${\rm Stab}(v)$ has countably many conjugate subgroups $g{\rm Stab}(v)g^{-1}$ (since all of these conjugates will be of the form ${\rm Stab}(w)$ where $w$ is another vertex, and there are only countably many vertices). – anon May 19 '18 at 16:32