Question 18.5: Do you see any bugs in the argument above? (Choose all that ......
Do you see any bugs in the argument above? (Choose all that apply.)
a) The concatenation P^{*} of {P}_{1}^{*} and {\mathbf{}}P_{2} need not have origin v.
b) P^{*} need not have destination w.
c) P^{*} need not have internal vertices only in {1, 2, . . . ,k}.
d) P^{*} need not be cycle-free.
e) P^{*} need not have length less than L.
f) Nope, no bugs.
(See Section 18.4.6 for the solution and discussion.)
Correct answer: (d). The concatenation P^{*} of {P}_{1}^{*} and {\mathbf{}}P_{2} definitely starts at v (because {P}_{1}^{*} does) and ends at w (because {\mathbf{}}P_{2} does). The internal vertices of P^{*} are the same as those of {P}_{1}^{*} and of {\mathbf{}}P_{2}, plus the new internal vertex k. Because all of the internal vertices of {P}_{1}^{*} and {\mathbf{}}P_{2} belong to {1, 2, . . . ,k − 1}, all of the internal vertices of P^{*} belong to {1, 2, . . . ,k}. The length of the concatenation of two paths is the sum of their lengths, so P^{*} does indeed have length L_{1}^{*}+L_{2}\lt L.
The issue is that the concatenation of two cycle-free paths need not be cycle-free. For example, in the graph concatenating the path 1\rightarrow2\rightarrow5 with the path 5\rightarrow3\rightarrow2\rightarrow4 produces a path that contains the directed cycle 2\rightarrow5\rightarrow3\rightarrow2.
