Consider the result from lecture that for any graph G = (V, E),

We proved this informally in lecture, which was good enough for our purposes; here we will construct the formal proof by induction, for rigour and practice. Some of the proof is provided for you; your job is to fill in the missing pieces, namely:

1. the base case;

2. the inductive step.