### Welcome to our community

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!

I got stuck at the following exercise... Could you give me an idea how to show this?

Let $G=(V,E)$ be a connected graph and $u,v$ $\epsilon$ $V$.If $d(v,u)=k$,then there is a path $v=v_{1},v_{2},....,v_{k+1}=u$ so that $\{v_{i},v_{j}\}$ doesn't belong in $E$ for $j \geq i+2$. Especially,there can't be repeated vertices.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
And what is $d(u,v)$?

#### mathmari

##### Well-known member
MHB Site Helper
And what is $d(u,v)$?
$d(u,v)$ is the minimum distance from the vertex u to the vertex v.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
By distance I assume the number of edges in a path from $u$ to $v$. Then the path of this minimal length has the required property, doesn't it? Otherwise it could be shortened.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Hey!!

I got stuck at the following exercise... Could you give me an idea how to show this?

Let $G=(V,E)$ be a connected graph and $u,v$ $\epsilon$ $V$.If $d(v,u)=k$,then there is a path $v=v_{1},v_{2},....,v_{k+1}=u$ so that $\{v_{i},v_{j}\}$ doesn't belong in $E$ for $j \geq i+2$. Especially,there can't be repeated vertices.
Just as Evgeny mentioned, you can argue by contradiction.

Since $d(u,v)=k$, the shortest path between $u$ and $v$ has length $k$.
Let $v=v_1,\ldots,v_{k+1}=u$ be a shortest path between $u$ and $v$ and call this path $P$.
Assume there exists $i$ and $j$ with $j\geq i+2$ such that $v_iv_j\in E$.

Can you construct a path between $u$ and $v$ which is shorter than $P$?

#### mathmari

##### Well-known member
MHB Site Helper
Just as Evgeny mentioned, you can argue by contradiction.

Since $d(u,v)=k$, the shortest path between $u$ and $v$ has length $k$.
Let $v=v_1,\ldots,v_{k+1}=u$ be a shortest path between $u$ and $v$ and call this path $P$.
Assume there exists $i$ and $j$ with $j\geq i+2$ such that $v_iv_j\in E$.

Can you construct a path between $u$ and $v$ which is shorter than $P$?
Assuming that there exists $i$ and $j$ with $j \geq i+2$ such that $v_iv_j \in E$, then there is a path between $u$ and $v$ whose distance is less than k, that means that there is a path which shorter than $P$.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Assuming that there exists $i$ and $j$ with $j \geq i+2$ such that $v_iv_j \in E$, then there is a path between $u$ and $v$ whose distance is less than k, that means that there is a path which shorter than $P$.
Yes. Does that solve your problem?

#### mathmari

##### Well-known member
MHB Site Helper
I found in my notes the following proof:

If $\{v_i,v_j\} \in E$ for $i,j$ with $j \geq i+1$.
Then the path is $v=v_1, ... , v_i, v_j, v_{j+1}, ..., v_{k+1}=u$ which length is $i-1+1+(k+1)-j=k-(j-i)+1 \leq k-2+1=k-1$.
$v_j=v_i$ for $j>i$ then $\{v_i,v_{j+1}\}=\{v_j,v_{j+1}\}$

Could you explain me how we calculated the length $i-1+1+(k+1)-j=k-(j-i)+1 \leq k-2+1=k-1$ ?
I assume that we have calculated the length of the path $v_1, ..., v_i$, which is $i-1+1$ and then the length of the path $v_j, ..., v_{k+1}$ which is $k+1-j+1=k-j+2$, isn't?

#### caffeinemachine

##### Well-known member
MHB Math Scholar
I found in my notes the following proof:

If $\{v_i,v_j\} \in E$ for $i,j$ with $j \geq i$+$1$. (I believe you meant $2$ rather than $1$.)
Then the path is $v=v_1, ... , v_i, v_j, v_{j+1}, ..., v_{k+1}=u$ which length is $i-1+1+(k+1)-j=k-(j-i)+1 \leq k-2+1=k-1$.
$v_j=v_i$ for $j>i$ then $\{v_i,v_{j+1}\}=\{v_j,v_{j+1}\}$ $\leftarrow$ I do not understand this line.

Could you explain me how we calculated the length $i-1+1+(k+1)-j=k-(j-i)+1 \leq k-2+1=k-1$ ?
I assume that we have calculated the length of the path $v_1, ..., v_i$, which is $i-1+1$ and then the length of the path $v_j, ..., v_{k+1}$ which is $k+1-j+1=k-j+2$, isn't?
How did calculate the length of the path?
It is kind of immediate from the definition of length of path.
How many edges are there in the path $v=v_1,\ldots,v_i,v_j,v_{j+1},\ldots,v_{k+1}=u$?
(Remember that a path is actually a graph.)

There are $l=\underbrace{(i-1)}_{\text{from } v \text{ to } v_i}+\underbrace{1}_{\text{for the edge between }v_i \text{ and } v_j}+\underbrace{(k+1-j)}_{\text{from } v_j \text{ to } u}$.

This gives $l=i-j+k+1$.
Now since $i-j\leq -2$, we have the $l\leq k-1$.

#### mathmari

##### Well-known member
MHB Site Helper
How did calculate the length of the path?
It is kind of immediate from the definition of length of path.
How many edges are there in the path $v=v_1,\ldots,v_i,v_j,v_{j+1},\ldots,v_{k+1}=u$?
(Remember that a path is actually a graph.)

There are $l=\underbrace{(i-1)}_{\text{from } v \text{ to } v_i}+\underbrace{1}_{\text{for the edge between }v_i \text{ and } v_j}+\underbrace{(k+1-j)}_{\text{from } v_j \text{ to } u}$.

This gives $l=i-j+k+1$.
Now since $i-j\leq -2$, we have the $l\leq k-1$.
Oh yes, I calculated the number of vertices between $v$ and $u$ instead of the number of edges.
That's why I found an other result..

So, since $l<k-1$, there is also a shorter path, but that contradicts to that what we have assumed, that the length of the shortest path is $k$. So it cannot be $j \geq i+2$.