On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m   edges. Mader proved that if n⩾3k-2n⩾3k-2 then m⩽k(n-k)m⩽k(n-k), and for n⩾3k-1n⩾3k-1 an equality is possible if, and only if, G   is the complete bipartite graph Kk,n-kKk,n-k. Cai proved that if n⩽3k-2n⩽3k-2 then m⩽⌊(n+k)2/8⌋m⩽⌊(n+k)2/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.