I am asked to prove that every connected, bipartite, k-regular ($k \ge2$) graph is 2-connected. Now for $n \ge 3$ I can use few of the theorems included and show that it is so indeed (focusing on the fact that the graph is bipartite).
What I wonder/have issue with is – what if we take a graph with two vertices x,y that have multiple edges between them? It would be 1-connected according to my book's definition (the connectivity of G is the minimum size of vertex set S such that G-S is disconnected or has only one vertex). What am I missing in here?
Connected question: A connected k-regular bipartite graph is 2-connected.
Edit: To clarify, my definition of graph allows multiple edges and loops. If a graph has none of these, it's stated it is a simple graph. In this question it isn't stated that the graph is a simple graph.
Best Answer
Suppose your $k$-regular graph $G$, split in vertex parts $X$ and $Y$, is not 2-connected.
Then there is a vertex $v$ whose removal splits $G$ in at least two connected components. Let $C$ be one of these components.
We'll just count the number of edges in $C$ and run into a problem. Suppose without loss of generality that $v \in Y$. Now, $C$ induces a bipartite graph, say with parts $X' \subset X$ and $Y' \subset Y$. Let $x = |X'|$ and $y = |Y'|$. Also, let $i$ be the number of edges going from $v$ to $C$. We have that $0 < i < k$. It turns out the bounds on $i$ are important, but I'll let you figure out why exactly we must have that.
Let $e_C$ be the number of edges in $C$. We have $e_C = x \cdot k - i$, since every vertex in $X'$ is of degree $k$, but the edges going to $v$ are not in $C$. Also, $e_C = y \cdot k$, since $Y'$ has no edges going out of $C$. Therefore $x \cdot k - i = y \cdot k$ and thus $x - \frac{i}{k} = y$. Since $y$ is the number of vertices in $Y'$, it is an integer, meaning that $i$ is a multiple of $k$. But $0 < i < k$, which makes it impossible.
Note that we never assumed $G$ was a simple graph, and this holds even if we have multi-edges.
EDIT : I seem to have missed the point of the question, as commented. The specific problem at hand is when $n = 2$. It does look there there are problems in the statement, and that you need n>2. Every definition of vertex-connectivity I came across states that a complete graph of n vertices has connectedness n−1 (even when extended to multigraphs). So the graph you speak would not be 2-connected. I think it's a mistake, and this happens sometimes in the literature with the special cases that are considered 'trivial'.