Cayley graphs of finite 2-generator groups 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$.)
 A: 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.
