2
$\begingroup$

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$.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot for your help. One should be better aware of important graph theoretic results when one uses graphs! Unfortunately I have not enough reputation to upvote your answer! $\endgroup$ – user 59363 Nov 13 '14 at 14:55

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.