Two Paths Joining Given Vertices in $(2k+1)$-Edge-Connected Graphs

Abstract

Let $k\ge 3$ be odd and $G=(V(G),E(G))$ be a $k$-edge-connected graph. For $X\subseteq V(G)$, $e(X)$ denotes the number of edges between $X$ and $V(G)–X$. We here prove that if $\{s_i,t_i\}\subseteq X_i\subseteq V(G)$, $i=1,2$, $X_1\cap X_2=\mathrm{\varnothing }$, $e(X_1)\le 2k-2$ and $e(X_2)<2k-1$, then there exist paths $P_1$ and $P_2$ such that $P_i$ joins $s_i$ and $t_i$, $V(P_i)\subseteq X_i$ ($i=1,2$) and $G–E(P_1\cup P_2)$ is $(k-2)$-edge-connected. And in fact, we give a generalization of this result and some other results about paths not containing given edges.