Exercise about connected graphs

[mathmari]

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]

And what is $d(u,v)$?

 

[mathmari]

And what is $d(u,v)$?

$d(u,v)$ is the minimum distance from the vertex u to the vertex v.

 

[Evgeny.Makarov]

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]

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]

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]

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]

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]

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]

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$.