Long path lemma concerning connectivity and independence number (Q554003)

Summary: We show that, in a \(k\)-connected graph \(G\) of order \(n\) with \(\alpha(G)=\alpha\), between any pair of vertices, there exists a path \(P\) joining them with \(|P|\geq \min\left\{n,{(k-1)(n- k)\over \alpha}+ 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,{(k- 1)(n- k)\over\alpha}+ k\right\}\). Moreover, we generalize our result as follows: for any choice \(S\) of \(s\leq k\) vertices in \(G\), there exists a tree \(T\) whose set of leaves is \(S\) with \(|T|\geq \min\left\{n,{(k-s+1)(n-k)\over\alpha}+ k\right\}\).