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| ≥ { n, (k - 1)(n - k)α + k }. This implies that, for any edge e E(G), there is a cycle containing e of length at least { n, (k - 1)(n - k)α + k }. 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| ≥ { n, (k - s + 1)(n - k)α + k }.