Induction problem 6

More Hints

Are you getting confused about what to do if the walk has more than one repeated node? For this proof:

If you have more than one flaw, it doesn't matter which you remove first. You can pick the one that's most convenient for writing your proof, e.g. the first one.

In your draft proof, are you joining two paths together? Remember that if you join two paths end-to-end, you might not get a path. The two paths might both go through the same intermediate node. If your proof has this issue, here's a hint:

If you have a partly-fixed walk that is shorter than the original, what does the inductive hypothesis tell you?