0
$\begingroup$

As a modification to a previous question I asked

In a $k$-connnected graph for every two paths contain only the initial vertex

I made the following claim and I would like to find out whether it is possible to prove it

If G is a $k$-edge connected graph and $v,v_1,v_2,…,v_k$ are $k+1$ vertices of graph $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

since a non-trivial graph $G$ is $k$-edge connected if and only if $ G $ contains $k$ pairwise edge disjoint u-v paths for each pair u,v of distinct vertices of G but how to show that each path $P_i$ will contain exactly one vertex $v_1,v_2,...v_k$

$\endgroup$
1
$\begingroup$

It is not necessarily that each path $P_i$ contains exactly one of $\{v_1, \cdots, v_k\}$. A counterexample is as follows.

Counterexample. The following figure shows a $2$-edge-connected graph, where $v$ is green, $v_1$ is blue and $v_2$ is red. As you can see, every path from $v$ to $v_2$ must pass $v_2$.

enter image description here

However, it is true that $P_i$ and $P_j$ are edge-disjoint if $i \neq j$. To prove this, you can construct a new graph $G'$ by adding a new vertex $w$ and $k$ new edges, namely $(w, v_1)$, $(w, v_2)$, $\cdots$ and $(w, v_k)$, to $G$. It is easy to know that $G'$ is $k$-edge connected. By Menger's theorem, there exists $k$ edge-disjoint paths from $v$ to $w$. If we remove $w$ from each of these paths, the paths are from $v$ to each $v_i$ in $G$ and are edge-disjoint.

$\endgroup$
  • $\begingroup$ Thanks , I know the part related to the edge-disjoint but I was doubtful about having one vertex $\endgroup$ – Frank Mar 18 '17 at 18:32
  • $\begingroup$ But you mean every path from $v$ to $v_2$ must pass $v_1$ $\endgroup$ – Frank Mar 18 '17 at 18:35
  • $\begingroup$ @Frank That is, every path from $v$ to $v_2$ must contain both $v_1$ and $v_2$. $\endgroup$ – PSPACEhard Mar 19 '17 at 5:15

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.