The K ‐Connectedness of Bipartite Graphs

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 T mn is the number of such unlabelled graphs, we show that T mn ∼ 2 mn /( m ! n !). If T′ mn is the number of such unlabelled graphs with the colours removed, then T′ mn ∼ T mn if m < n and T′ mn ∼ ½ T nn . 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.