1
$\begingroup$

I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely

Every finitely generated group can be represented as a symmetry group of a connected, directed, locally finite graph.

The proof basically begins by constructing something very similar to Cayley graph, then when it comes to proving connectedness it seems to me that the directedness of the graphs is just brushed over without consideration. So are Cayley graphs weakly connected, in the sense that they are connected only when we ignore direction, or are they strongly connected?

$\endgroup$
2
$\begingroup$

If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.

$\endgroup$
  • 2
    $\begingroup$ That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point. $\endgroup$ – Derek Holt Dec 28 '18 at 16:01
  • 1
    $\begingroup$ Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial. $\endgroup$ – user3482749 Dec 28 '18 at 16:13
  • $\begingroup$ In the context of the proof from Meier's book, the vertex set of the graph is the elements of $\langle S \rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g \in G$ and $s \in S$ $\endgroup$ – Jay Dec 28 '18 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.