Induction problem 6


Induction variables measure the size of something. What's a sensible definition of the size of a path?

What sort of flaw would mean that a walk is not a path? How would you fix the flaw to make it into a path? If you aren't sure what to do, draw a concrete example of a walk that isn't a path. Ignoring the formal math for a second, try to describe how you'd modify the walk to make a path connecting the same two nodes.

What happens if a walk has more than one such flaw? If you remove one flaw, can you use the inductive hypothesis (e.g. like a recursive function call) to deal with any additional flaws?