A1.8

Graph Theory
Part II, 2001

(i) Show that any graph GG with minimal degree δ\delta contains a cycle of length at least δ+1\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 δ+1\delta+1.

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

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

Find the average degree of vertices in the random tree.