(i) Show that any graph $G$ with minimal degree $\delta$ contains a cycle of length at least $\delta+1$. Give examples to show that, for each possible value of $\delta$, there is a graph with minimal degree $\delta$ but no cycle of length greater than $\delta+1$.

(ii) Let $K_{N}$ be the complete graph with $N$ vertices labelled $v_{1}, v_{2}, \ldots, v_{N}$. Prove, from first principles, that there are $N^{N-2}$ different spanning trees in $K_{N}$. In how many of these spanning trees does the vertex $v_{1}$ have degree 1 ?

A spanning tree in $K_{N}$ is chosen at random, with each of the $N^{N-2}$ trees being equally likely. Show that the average number of vertices of degree 1 in the random tree is approximately $N / e$ when $N$ is large.

Find the average degree of vertices in the random tree.