# Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann., 1971) that a connected vertex-transitive graph without $K_4$ has optimal vertex connectivity. My question is: which of the two papers by Mader mentioned above proves this result, and what is the exact statement of this result?

This result implies that all connected vertex-transitive graphs with clique number 2 or 3 have optimal vertex connectivity. In particular, all connected Cayley graphs generated by transpositions (these graphs are bipartite) have optimal vertex connectivity.

This article by Maya Stein states the relevant results on these two papers by Mader (page 11):

Which degree at each vertex do we need in order to ensure that our graph has a $k$-(edge-) connected subgraph?

It is known that in finite graphs a degree of $k$ is enough, and moreover the subgraph will be the graph itself. In fact, every finite vertex-transitive $k$-regular connected graph is $k$-edge-connected [27]. It is even k-connected, as long as it does not contain $K^4$ as a subgraph [25].

• [25] W. Mader. Uber den Zusammenhang symmetrischer Graphen. Archiv der Math., 21:331-336, 1970.

• [27] W. Mader. Minimale n-fach zusammenhangende Graphen. Math. Ann., 191:21-28, 1971.

So the result you're looking for is on the 1970 paper.

• I think "nite" should be "finite"? Perhaps the ligature did not survive the cut-n-paste process? Nov 2 '15 at 23:37
• @GordonRoyle Thanks! Just a copy-paste gone wrong. Nov 3 '15 at 0:05
• @Myshkin. Thanks. I would appreciate if someone could confirm first-hand (from Mader's original paper) that this result is in Mader's paper. Nov 3 '15 at 9:33
• @AshwinGanesan Indeed, the 1970 paper states this as a theorem: "Satz 4. Wenn ein zusammenhängender eckensymmetrischer Graph vom Grad $g$ keinen $V_4$ enthält, ist er $g$-fach zusammenhängend." — "Theorem 4. If a connected vertex transitive graph of regularity $g$ contains no $K_4$, then it is $g$-connected." Nov 17 '15 at 2:13