Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 5 / b

A graph path of length at most $k+1$ either already has length at most $k$, or consists of a prefix of length at most $k$ followed by one edge. ThereforeThe forward implication follows by removing the final edge of a nonempty graph path. Conversely, concatenating the indicated prefix and edge gives a walk of length at most $k+1$, and removing repetitions if necessary gives a graph path no longer than that walk.

Writing $\odot$ for Boolean matrix multiplication, the formula is $P_{k+1}=P_k\vee (P_k\odot E)$. Because $P_1$ includes the identity matrix, an equivalent formula isCompute each new matrix from an unchanged copy of the preceding matrix, so the subscript continues to specify exactly the length bound.