Clarification from a proof that a certain type of graph can be endowed with a group operation

Question

I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property.

I'll just throw some definitions here first...

Definitions.

1. An alphabet $A$ is a union of two sets, one called $X$ and one called $X^{-1}$, together with a map $^{-1}:A\rightarrow A$, with $^{-1}(x)$ written $x^{-1}$, such that $x^{-1}\in X^{-1}$ for every $x\in X$ and $x^{-1}\in X$ for every $x\in X^{-1}$. A group alphabet is an alphabet such that $X^{-1}\subseteq X$.

2. An $X$-digraph is a directed graph such that each edge is labeled with an element of $X$.

3. We say that an $X$-digraph $\Gamma$ is folded if, given any edge $u\rightarrow v$ labeled with $x$, there are no edges $u\rightarrow w$ to any vertex $w$ labeled with $x$.

4. An $X$-digraph morphism is a map $\varphi:\Gamma\Rightarrow G$ between $X$-digraphs $\Gamma$, $G$ that preserves connectedness and edge labels, i.e. if $A\subseteq \Gamma$ is connected, so is its image $\varphi(A)$, and if $x_e$ is the element of $X$ associated with an edge $e$ going from $v$ to $w$, there is an edge from $\varphi(v)$ to $\varphi(w)$ with label $x_e$.

This is the relevant part of the theorem I'm looking at.

Theorem. Let $X$ be a group alphabet and $\Gamma$ a folded $X$-digraph. Suppose that

(a) $\Gamma$ is connected, and

(b) for every $u,v$ in $V(\Gamma)$ there exists an $X$-digraph isomorphism $\varphi:\Gamma \rightarrow \Gamma$ such that $\varphi(u)=v$.

Then $V(\Gamma)$ is a group.

Proof. We construct a group $G$ on the set $V(\Gamma)$ with the operation defined as follows. Fix some vertex $v_0$. For each $v\in \Gamma$, choose any path from $v_0$ to $v$, and denote its label by $w_v$. For $u,v\in G$, define $uv$ to be the endpoint of the path starting at $v_0$ labeled with $w_u\circ w_v$. It is straightforward to check that $G$ is a group.

OK, so, there are a few things here that are unclear to me.

1. I'm not sure what $w_u\circ w_v$ is. Apparently there is a function called $\circ:X\times X\rightarrow X$. It wasn't defined, and maybe it's obvious enough that it should be implied, but I don't see it. (The larger context is that this appears in a proof that $\Gamma$ is the Caley Graph of some group, so I don't think we can assume there is a group operation on the group alphabet yet.)

2. the label of a path wasn't defined, either. My guess is that $a_1\xrightarrow{w_1}{a_2}\xrightarrow{w_2}\cdots \xrightarrow{w_{n-1}}{a_n}$ would be labeled by $w_1\circ w_2 \circ \cdots \circ w_{n-1}$, but again, I'm not sure what that means.

3. I'm not sure how the condition (b) fits into this proof. (I predict that that in some way answers my other two questions.)

Is anyone familiar enough with this type of material to fill me in?

Answer 1

Oh, I figured it out. Here it is, in case anybody ever stumbles across this page with the same confusion...

Claim. If $x\in X$ appears as an edge label on $\Gamma$, then for every $u\in \Gamma$, there is a (unique) $v_{u,x}\in \Gamma$ such that $u\xrightarrow{x} v_{u,x}$.

Suppose that $y\xrightarrow{x} z$ for some $y,z\in V(\Gamma)$. By condition (b), there is an $X$-digraph isomorphism $\varphi:\Gamma\rightarrow \Gamma$ such that $\varphi(y)=u$. Since $\varphi$ preserves edge labeling, $u\xrightarrow{x} \varphi(z)\triangleq v_{u,x}$. Uniqueness follows from the fact that $\Gamma$ is folded.

Define the label of a path $a_1\xrightarrow{w_1}{a_2}\xrightarrow{w_2}\cdots \xrightarrow{w_{n-1}}{a_n}$ by $w_1\circ w_2 \circ \cdots \circ w_{n-1}$.

If $u\in \Gamma$ and $x\in X$ define $x(u)$ by $v_{u,x}$ as in the claim. Extend this definition to path labels inductively by $(w_1\circ w_2 \circ \cdots \circ w_{n-1})(u)=w_{n-1}(w_{n-2}( \cdots (w_{1}(u))\cdots ))$.

Then everything works!