Let $\Gamma$ be a finite connected bipartite $k$-regular multigraph (for $k\ge 3$) which is both vertex and edge transitive. Here by regularity I mean every vertex has $k$ edges incident to it. By multigraph I mean a graph with possibly multiple edges between any two given vertices. I do not allow loops.
If $\Gamma$ is simple then the vertex-transitivity implies that $\Gamma$ is $k$-edge connected. Clearly removing all the $k$ edges adjacent to a vertex will disconnect the graph. Is it possible to disconnect the graph by removing $k$ edges without isolating a vertex?
To be clear, I want to show that the only way to disconnect such a graph by removing $k$ edges must involve isolating a vertex.
(Edited to add bipartite and remove $k$ edges condition)
Best Answer
Short answer: No, it is not possible.
Long answer involves some history.
The property you are looking for has a name: a graph is super-$\lambda$ if it is $\lambda$-edge-connected, and every edge cut with $\lambda$ edges leaves an isolated vertex.
So the result you want is this: Every connected edge and vertex transitive bipartite graph with vertex degree at least $3$ is super-$\lambda$. Apparently, R. Tindell proved that every connected edge-transitive graph with degree at least $3$ is super-$\lambda$ in the 1980s (according to his own citation to a paper in review), but I cannot find this paper!
I found the citation and result (without proof) in "Circulants and their connectives" by R. Tindell and F. Boesch.
Luckily, the result has been improved (with an original proof that does not use the inaccessible one by Tindell). The fact that every edge-transitive connected graph that is not a cycle is super-$\lambda$ (i.e., the result we want) is an immediate consequence of Theorem 1 in the paper "Super Edge Connectivity Properties of Connected Edge Symmetric Graphs" by Qiaoliang Li and Qiao Li - published in the journal Networks volume 33, issue 2.
The proof is a bit involved, and the paper itself can be found online.