Finding an underlying group and a generating set from given Cayley Graph Let’s say we have given a Cayley Graph. From this graph can we obtain an underlying group and a generating set?
My answer: Yes, we can. By trial and error. Taking all groups of order = order of graph and trying all of the possible generating sets. But this sounds tedious.
Do we have an algorithm to work this out?
 A: Note that we define the Caley digraph $\Gamma$ for a given group $G$ and generating set $S\subseteq G$ as follows:

*

*$V(\Gamma)=G$ (the set of vertices)

*$A(\Gamma)=\{(g,gs):g\in G,s\in S\}$ (the set of arcs)

*Each arc $(g,gs)$ is labeled by $s$
Note that in the case when $S$ is finite, the outdegrees of a Caley graph are equal to $|S|$ since $gs_1=gs_2$ implies $s_1=s_2$. The same is true for the indegrees: given a vertex $b$, the set of arcs ending in $b$ is $\{(bs^{-1},b):s\in S\}$. Thus, Caley graphs are regular.
Also, note that Condition 3 is correct, i.e. given an arc $(a,b)$, there is a unique $s$, such that $b=as$. The generating set can be defined immediately: it's just the set of labels of arcs outgoing from some vertex.
What about the group itself, it'll be sufficient to reconstruct the Caley table, i.e. given elements $a,b\in G$, we want to know what $ab$ will be. For this, suppose $e$ is the identity element. How can you find it using the Caley graph? Since $e$ is the identity element, $es=s$ for some $s\in S$. Thus, there is an arc $(x,s)$ labeled by $s$. Since this arc is unique, $e$ must be $x$.
Now, consider the set $S'=\{s^{-1}:s\in S\}$. Suppose $b=\sigma_1...\sigma_n$, where $\sigma_1,...,\sigma_n\in S\cup S'$. Suppose there is an arc $(g,h)$ labeled by $s$. This means that $h=gs$. Thus, $g=hs^{-1}$. That is, if you want to get the result of multiplication of $h$ by $s^{-1}$, just find the unique arc $(x,h)$ labeled by $s$, and put $hs^{-1}=x$. This means that using arcs in both directions, we have at least one way to reach $b$ from $e$: if $\sigma_i=s\text{ }(s^{-1})$, use the out-$s$-arc (in-$s$-arc) from the current vertex. Thus, suppose you've found such a pseudo-path from $e$ to $b$. Now, applying this pseudo-path to $a$, you'll reach $ab$.
In other words, a Caley graph contains data both about the group and generating set.
