An Improved Degree Condition for Connectivity-Preserving Spanning $(u,v)$-Paths

Abstract

Teng and Tian proved the following result. Let $k\ge 2$ and $t\ge 3$, and let $G$ be a $k$-connected graph of order $n$. If $n\ge 6k+1$ and $δ(G)\ge \lceil(n+6)/2\rceil$ when $t=3$, while $n\ge 6k+7t-17$ and $δ(G)\ge \lceil(n+t+2)/2\rceil$ when $t\ge 4$, then, for any two distinct vertices $u,v$ and every integer $s$ with $1\le s\le t$, there exist $s$ internally vertex-disjoint $(u,v)$-paths $P_1,\dots,P_s$ whose union spans $G$ and such that $G-E(P_1\cup\cdots\cup P_s)$ is $k$-connected. They asked whether the minimum-degree condition could be lowered to $δ(G)\ge \lceil(n+t)/2\rceil$ for every $t\ge 3$. We answer this question affirmatively and further reduce the required order to $n\ge \max\{6k+9-3t,\,2k+t+3\}$.

Disclosure

“rder hypothesis. The resulting order bound n ≥ max{6k + 9 − 3t, 2k + t + 3} cannot be lowered using the estimates in the present proof; any further improvement would require sharper estimates or a different argument. Declaration of AI Use. ChatGPT was used to assist in developing and checking the con- structions and proofs. The author independently verified all mathematical arguments, wrote the paper, and takes full responsibility for its content. References [1] G. Chartrand, S.F”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:27:34.017360Z

Structural counts