Long Path Lemma concerning Connectivity and Independence Number - Fujita, Shinya; Halperin, Alexander; Magnant, Colton (The Electronic Journal of Combinatorics, 2011)
We show that, in a $k$-connected graph $G$ of order $n$ with $α(G) = α$, between any pair of vertices, there exists a path $P$ joining them with $$|P| ≥ \min \left\{ n, \frac{(k - 1)(n - k)}{α} + k \right\}.$$ This implies that, for any edge $e \in E(G)$, there is a cycle containing $e$ of length at least $$\min \left\{ n, \frac{(k - 1)(n - k)}{α} + k \right\}.$$ Moreover, we generalize our result as follows: for any choice $S$ of $s ≤ k$ vertices in $G$, there exists a tree $T$ whose set of leaves is $S$ with $$|T| ≥ \min \left\{ n, \frac{(k - s + 1)(n - k)}{α} + k \right\}.$$