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 Answer 1

2
$\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$
3
  • $\begingroup$ Thanks , I know the part related to the edge-disjoint but I was doubtful about having one vertex $\endgroup$
    – Frank
    Mar 18, 2017 at 18:32
  • $\begingroup$ But you mean every path from $v$ to $v_2$ must pass $v_1$ $\endgroup$
    – Frank
    Mar 18, 2017 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, 2017 at 5:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .