MHB Exercise about connected graphs

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Exercise Graphs
AI Thread Summary
The discussion focuses on proving a property of connected graphs regarding the distance between two vertices, u and v. It establishes that if the distance d(v, u) = k, then there exists a path from v to u such that no two vertices in the path are adjacent if they are at least two indices apart. The proof involves a contradiction: if there were such an edge between non-adjacent vertices, it would imply a shorter path exists, contradicting the definition of distance. The calculations of path lengths are clarified, leading to the conclusion that the assumption of an edge between distant vertices cannot hold. This reinforces the original claim about the structure of paths in connected graphs.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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.
 
Physics news on Phys.org
And what is $d(u,v)$?
 
Evgeny.Makarov said:
And what is $d(u,v)$?

$d(u,v)$ is the minimum distance from the vertex u to the vertex v.
 
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.
 
mathmari said:
Hey! :o

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$?
 
caffeinemachine said:
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$.
 
mathmari said:
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?
 
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?
 
mathmari said:
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$.
 
  • #10
caffeinemachine said:
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. :o
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$.
 
Back
Top