I've seen the similar question "A connected k-regular bipartite graph is 2-connected" answered:
- A connected k-regular bipartite graph is 2-connected.
- Prove that every connected k-regular bipartite graph on at least 3 vertices is 2-connected for k at least 2
But I was thinking... isn't a connected k-regular bipartite graph not only 2-connected, but also n-connected.
Does anyone have a proof or a counterexample?
Halfway through writing the question, I cracked it! This a counterexample.
A 3-regular, connected, bipartite graph which is NOT 3-connected. Notice that taking out, for example $4$ and $6$ leaves the graph disconnected.
This can also be applied to build a counterexample for any $k$.
The idea is to build 2 complete bipartite graphs $K_{k,k}$ and then remove one edge from each of them, let's call them {a,b} and {c,d} respectively. (Note: there's an added restriction here, $a$ and $c$ should belong to the same partition set, whereas $b$ and $d$ should both belong the to other). And then add other two edges instead, {a,d} and {b,c}. This leaves the graph:
but NOT k-connected (removing $a$ and $b$ leaves the graph disconnected).