Menu
For a set \( S \) of two or more vertices in a nontrivial connected graph \( G \) of order \( n \), a collection \(\{T_1, T_2, \ldots, T_\ell\}\) of trees in \( G \) is said to be an internally disjoint set of trees connecting \( S \) if these trees are pairwise edge-disjoint and \( V(T_i) \cap V(T_j) = S \) for every pair \( i, j \) of distinct integers with \( 1 \leq i, j \leq \ell \). For an integer \( k \) with \( 2 \leq k \leq n \), the tree \( k \)-connectivity \( \kappa_k(G) \) of \( G \) is the greatest positive integer \( \ell \) for which \( G \) contains at least \( \ell \) internally disjoint trees connecting \( S \) for every set \( S \) of \( k \) vertices of \( G \). It is shown for every two integers \( k \) and \( r \) with \( 3 \leq k \leq 2r \) that
\[
\kappa_k(K_{r,r}) = r – \left\lceil \frac{k-1}{4} \right\rceil.
\]