Let G a graph (connected) and the walk $T = (u, x_1, \dots , x_k, v)$ a geodesic (walk with the shortest distance) between the vertex $u$ and $v$. Show that: 1. $T$ is a path. 2. If $i,j \in \{1, \dots, k \}$ and $i \leq j$ then the walk $(x_i, T, x_j)$ is a geodesic between $x_i$ and $x_j$.

In (1) I have the idea to led a contradiction: Proof: Suppose that $T$ is not a path, i.e. there's at least one vertex with more than one occurrence. Since $G$ is connected then there's a path between $u$ and $v$. So, let $T'$ a path between $u$ and $v$, since $T$ is a path then it has the shortest distance between these two vertex. So $T'$ is geodesic and $T$ is not. Contradiction.

In (2) I must to assume that the vertex are not adjacent, but since then, what?


For (1), if you remove the first and last occurrence of the repeated vertex in $T$ you obtain a shorter walk Than $T$ which is a contradiction.

For (2), if $(x_i, T, x_j)$ is not geodesic then there is a shorter walk between $x_i$ and $x_j$ which means that $T$ is not geodesic because you can get shorter walk between $u$ and $v$ by replacing $(x_i, T, x_j)$ in $T$ the shorter walk between $x_i$ and $x_j$ which is contradiction


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.