Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 204 / 2 / a / Solution

An $n$-step self-avoiding walk on a graph $G=(V,E)$ is a sequence $(v_0,v_1,\dots ,v_n)$ of $n+1$ distinct graph vertices such that $\{v_{i-1},v_i\}\in E$ for $1\le i\le n$. It has $n$ edges and no repeated vertex, including its starting graph vertex. The $0$-step self-avoiding walk consists of its starting graph vertex alone.