Welcome to our community

Be a part of something great, join today!

Exercise about connected graphs

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hey!! :eek:

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
Jan 30, 2012
2,492
And what is $d(u,v)$?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Mar 10, 2012
834
Hey!! :eek:

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
Apr 14, 2013
4,047
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
Mar 10, 2012
834
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
Apr 14, 2013
4,047
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
Mar 10, 2012
834
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
Apr 14, 2013
4,047
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. :eek:
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$.