Cayley graphs of finite 2-generator groups

Question

Let $G=\left<a,b\right>$ be a finite 2-generator group and $\Gamma$ its Cayley graph with respect to $\{a,b\}$. Is it true that $\Gamma\setminus\{e,f\}$ is connected for two arbitrarily chosen edges $e$ and $f$? In a path one may traverse edges in both directions. (In case a generator $a$ has order 2 I assume the edges $(g,ga)$ and $(ga,gaa)=(ga,g)$ to be distinct, so every vertex has in-degree as well as out-degree $2$. If you are uncomfortable with this convention then please assume that no generator has order $2$.)

Answer 1

It is known that the edge-connectivity of a connected vertex-transitive graph is equal to its valency. In your case, the Cayley graph $\Gamma$ is a directed graph, with each vertex having indegree 2 and outdegree 2. Consider the graph $\Gamma'$, defined to be the undirected version of $\Gamma$ (so $\Gamma'$ is obtained from $\Gamma$ by just removing the orientation of the arcs). Then $\Gamma'$ is a 4-regular vertex-transitive graph. You want to know whether any two edges can be removed from $\Gamma'$ without disconnecting the graph, i.e. whether the edge-connectivity of $\Gamma'$ is at least 3. Since $\Gamma'$ is connected, vertex-transitive and has valency at least 3, the answer to your question is in the affirmative.

The problem can be modified so that any parallel edges in $\Gamma'$ (if they exist) are removed before determining the edge-connectivity. For example, if the two generators $a$ and $b$ are the $n$-cycle $(1,2,\ldots,n)$ and its inverse $(1,n,\ldots,2)$, then $\Gamma$ is the digraph of an $n$-cycle graph, with an arc from vertex $i$ to $i+1$ and also an arc from $i+1$ to $i$. Removing the orientations in $\Gamma$ gives a graph $\Gamma'$ that has parallel edges (it is a multigraph). If these parallel edges are removed, then we get a simple, undirected $n$-cycle graph. There do exist two edges in this graph whose removal disconnects the graph, for example the two edges incident to a vertex. When the generator set is closed under inverses, we can view the Cayley graph as undirected, and this undirected graph is 2-regular and has edge-connectivity exactly equal to 2.