Why in a Hamiltonian walk, the summation of the lengths of the subwalks is less than equal to the length of the hamiltonian walk?

23 Views Asked by At

Given below is an excerpt from the text A First Course in Graph Theory by Chartrand, Zhang.

Here $L(W)$ means the length of the walk $W$.Graph $G$ has $n$ vertices. $h(G)$ is the length of the Hamiltonian walk in $G$.

Let $W$ be a Hamiltonian walk in $G$ with $L(W)=h(G)$. Suppose that $W=(x_1,x_2,...,x_N,x_1)$, where $N\geq n$. Define $v_1=x_1$ and $v_2=x_2$. For $3\leq i \leq n$, define $v_i$ to be $x_{j_i}$, where $j_i$ is the smallest positive integer such that $x_{j_i} \notin \{v_1,v_2,...,v_{i-1}\}$. Then $s: v_1,v_2,...,v_n,v_{n+1}=v_1$ is cyclic ordering of $V(G)$. For each $i$ with $1\leq i\leq n$, let $Q_i$ be the $v_i-v_{i+1}$ subwalk of $W$ and so $d(v_i,v_i+1) \leq L(Q_i)$. So,

$$\sum_{i=1}^{n} L(Q_i)\leq L(W) \tag 1$$

I cannot understand why in $(1)$ we are getting a possibility of $\lt$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

The possibility doesn't exist, since for any cyclic ordering of the vertices, if we take the concatenation of geodesics between consecutive vertices we get a closed walk that passes through all the vertices, and therefore its length is less than $L(W)$.

I think in this part of the book the author simply wants to show that in order to find a hamiltonian walk for the graph it is sufficient to just consider all cyclic orderings of the vertices, a hamiltonian walk can be obtained by considering the concatenations of geodesics between consecutive vertices in the ordering.