Induction problem 6

Solution

Suppose that G is a graph. Suppose that a and b are nodes in G.

Proof by induction on n, which is the length of the walk.

Base: n=0. A zero-length walk (a single node) is always a path.

Inductive hypothesis: Suppose that if there is a walk of length n from node a to node b, then there is a path from a to b, for all lengths n=0,1,...,k-1.

Rest of inductive step: Suppose that we have a walk W from a to b which has length k. Let's suppose the node sequence for W is \(a=v_1, v_2, \ldots, v_{k+1} = b\).

If W is a path, then we're done.

If W is not a path, it must use some node twice. Suppose that the first repeated node is \(v_j\) and it appears again in the walk as \(v_p\). If \(v_j = b\), then the node sequence \(a=v_1, v_2, \ldots, v_j = b\) is a path from a to b because \(v_j\) was the first repeated node.

Otherwise, let's form a new walk W' with node sequence \(a=v_1, v_2, \ldots, v_j, v_{p+1}, \ldots, v_{k+1} = b\). W' still goes from a to b, but it is shorter than W, i.e. length k-1 or shorter. So, by the inductive hypothesis, there is a path P from a to b.

Comments

Notice that we kept G, a, and b fixed for the whole proof. This doesn't always work. For some similar claims, you might need to use the inductive hypothesis for different choices of the graph and/or nodes. In such cases, you might need to write something like this

Suppose that G is a graph.

Proof by induction on n, which is the length of the walk.

.....

Inductive hypothesis: Suppose that if there is a walk of length n from node a to node b, then there is a path from a to b, for any nodes a and b and all lengths n=0,1,...,k-1.

....

Self-check

Is your base case at n=0 (not n=1)? Was it a single-node walk? It's not wrong to have an extra base case for a two-node (n=1) walk, but it's wrong to start your base cases with n=1.

Notice that the length of walks is measured in edges (not nodes). So when we write out the node sequence for a walk of length k, it must contain k+1 nodes.

Does your inductive step involve joining two paths together to make a path? Or does it say something like this:

..., let's form a new walk W' with node sequence \(a=v_1, v_2, \ldots, v_j, v_{p+1}, \ldots, v_{k+1} = b\). W' is a path from a to b.

Remember that joining two paths may create a walk that isn't a path, because the two paths might share intermediate nodes. Also removing one loop from a walk doesn't necessarily make it into a path, because it might contain other loops. Notice that the model solution takes the partly-fixed walk and uses the inductive hypothesis to find a corresponding path (which might be slightly different from the partly-fixed walk).