A1.8
Part II, 2001
(i) Show that any graph with minimal degree contains a cycle of length at least . Give examples to show that, for each possible value of , there is a graph with minimal degree but no cycle of length greater than .
(ii) Let be the complete graph with vertices labelled . Prove, from first principles, that there are different spanning trees in . In how many of these spanning trees does the vertex have degree 1 ?
A spanning tree in is chosen at random, with each of the trees being equally likely. Show that the average number of vertices of degree 1 in the random tree is approximately when is large.
Find the average degree of vertices in the random tree.