If G is a $k$-connnected graph and $u,v_1,v_2, \dots , v_t$ are $t+1$ distinct vertices in $G$ for $2 \leq t \leq k$, $G$ contains a $u-v_i$ path for each $1 \leq i \leq t$, every two paths of which have only $u$ in common.

I believe the result comes from Whitney's theorem but how to show this?


We construct a new graph $G'$ by adding a new vertex $w$ and adding $t$ new edges $(w, v_1)$, $(w, v_2)$, $\cdots$, and $(w, v_t)$ to $G$. The resulting graph $G'$ is $t$-connected. By the Menger's theorem, there exist $t$ vertex-disjoint paths from $u$ to $w$ in $G'$. Note any path from $u$ to $w$ must pass one of $\{v_1, \cdots, v_t\}$. Therefore, the $t$ vertex-disjoint paths from $u$ to $w$ correspond to $t$-vertex disjoint paths from $u$ to $\{v_1, \cdots, v_t\}$ respectively.

  • $\begingroup$ Do you mean after adding vertex $w$ then $t=k$ so there exists $t$ internally disjoint paths ? isn't that whiteny's theorem which can be provedby menger's theorem ? $\endgroup$ – Frank Mar 17 '17 at 17:21
  • $\begingroup$ ok.Why can we suppose the existence of $w$? $\endgroup$ – Frank Mar 17 '17 at 17:36
  • $\begingroup$ what if I change the claim to If G is a $k$-edge connected graph and $v,v_1,v_2, \dots , v_k$ are $k+1$ vertices of $G$,then for $i$=$1,2...,k$, there exists a $v-v_i$ path $P_i$ such that each path $P_i$ contains exactly one vertex ${v_1,v_2,...v_k}$ and for $i$ doesn't equal to$ j$ .$P_i$ and $P_j$ are edge disjoint .Is it valid ? $\endgroup$ – Frank Mar 18 '17 at 8:22
  • $\begingroup$ How would you suggest to do that? $\endgroup$ – Frank Mar 18 '17 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.