The K -Connectedness of Bipartite Graphs
Elizabeth Mary Wright · Journal of the London Mathematical Society · 1982
We consider bipartite graphs on m red points and n blue points, where m ⩽ n, and prove that, for any fixed k, almost all such graphs (labelled or unlabelled) are k-connected as n → ∞, provided m > C log n, where C depends on k. If Tmn is the number of such unlabelled graphs, we show that Tmn ∼ 2mn/(m!n!). If T′mn is the number of such unlabelled graphs with the colours removed, then T′mn ∼ Tmn if m < n and T′mn ∼ ½Tnn. We deduce that almost all bipartite graphs on p points in all, whether labelled or unlabelled, are k-connected and so prove a conjecture of Harary and Robinson.