I was reading "Discrete Mathematics and its Applications" by Kenneth Rosen where I came across the following lemma and I felt that is incomplete to some extent.
Lemma: Let $A$ be a set with $n$ elements, and let $R$ be a relation on A. If there is a path of length at least one in $R$ from $a$ to $b$, then there is such a path with length not exceeding $n$. Moreover, when $a \neq b$,if there is a path of length at least one in R from a to b,then there is such a path with length not exceeding $n − 1$ .
Figure: Producing a Path with Length Not Exceeding n.
Proof: Suppose there is a path from $a$ to $b$ in $R$. Let $m$ be the length of the shortest such path. Suppose that $x_0,x_1,x_2,...,x_{m−1} ,x_m$, where $x_0 = a$ and $x_m = b$ , is such a path. Suppose that $a = b$ and that $m>n$, so that $m ≥ n + 1$. By the pigeonhole principle, because there are $n$ vertices in $A$, among the $m$ vertices $x_0,x_1,x_2,...,x_{m−1}$ , at least two are equal (see Figure). Suppose that $x_i = x_j$ with $0 ≤ i<j≤ m − 1$ . Then the path contains a circuit from $x_i$ to itself. This circuit can be deleted from the path from $a$ to $b$, leaving a path, namely, $x_0,x_1 ,...,x_i ,x_{j +1} ,...,x_{m−1} ,x_m$ , from $a$ to $b$ of shorter length. Hence, the path of shortest length must have length less than or equal to n. The case where a = b is left as an exercise for the reader.
Here the author is saying that $m$ is the length of shortest possible path from $a$ to $b$ and assumes it be $>n$ then he tries to reach at a contradiction by pigeonhole principle. Now first of all when we are making the assumption it is possible that $m>n$ is not just few integers greater than $n$, may be some multiple of $n$ added with some constant such as $m=kn+c$ and using the generalize pigeonhole principle there can be at least $k+1$ vertices which are repeated. It might so happen that they are just repeated one after the other. Then if we use the simple pigeon hole principle and remove say only the first two repetitions then then our new length $m'$ shall be smaller than the previous length $m$ but chances are there( as in this one) that the duplicates are not removed completely and simply we can't say by applying the pigeonhole principle only once that $m'\leqslant n$ when $a=b$. We can even have more than one such loop as shown in the shown in the figure. Probably the author has simplified the situation by implicitly considering the situation when there is only one such loop. To be more clear with the proof using the simple pigeonhole principle I feel the end of the proof should be modified a bit and stated as, "after removing one such loop if $m'>n$ the same situation arises and we continue till we are left with $m^{'''...''}\leqslant n$ , the situation when no such loops exists".
Please correct me if I am wrong.
It doesn’t matter whether there was more than one loop: the argument isn’t intended to produce a shortest path. The point is that the path was assumed to be a shortest possible path from $a$ to $b$ and of length $m>n$, and the argument shows that these two assumptions are incompatible: if the path has length greater than $n$, then it can be shortened by removal of a loop, so it cannot have been a shortest possible path. There certainly is a shortest path from $a$ to $b$, so we can now conclude that it cannot have length greater than $n$: if it did, we’ve just seen that there would be at least one shorter path.