# Edge and vertex connectivity of bipartite graph

Let graph $G=(V,E)$ be bipartite graph with partite sets $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$. Vertices $x_i$ and $y_j$ are connected with edge if and only if $i \neq j$. What would be edge connectivity ($\lambda(G)$) and vertex connectivity($\kappa(G)$) of this graph?

I think that edge connectivity would be $\lambda(G) = 1$ since there are no vertices connected with no more then one edge. But I am not sure, and I don't know vertex connectivity.

Thank you for help

• Are you sure you don't mean that every vertex has precisely $n-1$ neighbours? That would give you $K_{n,n}$ minus one matching. – Jernej Apr 13 '15 at 8:39
• @Jernej Yes, I am sure. – Superian007 Apr 13 '15 at 8:41
• So in this case your graph is a matching which is a disconnected graph for $n > 1.$ – Jernej Apr 13 '15 at 8:42
• What do you mean by "your graph is matching"? And disconnected graph in terms of edge connectivity or vertex connectivity? – Superian007 Apr 13 '15 at 9:42
• The graph you describe is the disjoint union of $n$ edges. Hence if $n > 1$ the graph is not connected. But as I said I think you're confused with the definition and in fact want to consider $K_{n,n}$-matching. – Jernej Apr 13 '15 at 10:07