Solutions
Problem 1: (a) The 7 edges of cost 1: 1-2,2-3,3-4,4-5,5-6,6-7,7-8 form a spanning tree of minimal cost 7.
(b) Yes, the graph is connected and all vertices have even degree so it does have one. It is easy to give one also.
Problem 2: Suppose that K3,3 were planar. Then by Euler's formula, V-E+F=2, V=6, E=9, so F=5, the number of faces. Since K3,3 is bipartite, each face must have an even degree at least 4. So the sum of the face degrees is at least 20, which is greater than 2 times the number of edges which is 18. This is a contradiction to the hypothesis that K3,3 is planar.
Problem 3: The number of edges in Kn+1 is the number of edges of Kn, plus the number of edges emanating from vertex n+1, which is n. This proves the recurrence. Since the first difference is n, the answer is (n choose 2)+c, and c=0 since a1=0. Or you can say that Kn has (n choose 2) edges.
Problem 4: Let Ai be the set of words where i does not occur. We need to find the size of the intersection of the complements of the sets Ai, 1≤ i≤ k. By I-E this is
kn (all words) minus the sum of the sizes of each set. There are k sets each of size (k-1)n. Then we add back in the double intersections, each one has size (k-2)n, and there are (k choose 2) such double intersections. In general there are (k choose i) i-fold intersections, each with size (k-i)n.
This number is k!S(n,k), the number of set partitions of an n-sets into k ordered blocks.
When k=2 we get 2n-2.
Problem 5: (a) There are nn-2 spanning trees of Kn. How many of them have vertex 1 as a leaf? In the Prufer correspondence, 1 cannot appear, so there are (n-1)n-2 such trees. So the probability is (n-1)n-2/nn-2=(1-1/n)n-2, which has limit 1/e (use calculus).
(b) If n is odd the answer is 0 since no graph can have an odd number of vertices of odd degree. If n is even then the tree must have n/2-1 vertices of degree 3 and n/2+1 verticies of degree 1. There are (n choose n/2-1) ways to choose which vertices have degree 3. Each of these labels must appear twice in the Prufer word of length n-2. There are (n-2 choose 2,2,..,2) ways to form such words. So the answer is
(n chose n/2-1)*(n-2 choose 2,2,..,2)/nn-2.
Problem 6: (a) There are 7 on each list.
(b) The generating function when the parts are not multiples of 3 is
A(x)= 1/(1-x)(1-x2)(1-x4)(1-x5)...
The generating function when the parts have multiplicity at most 2 is
B(x)= (1+x+x2)(1+x2+x4)...=
(1-x3)/(1-x)*(1-x6)/(1-x2)...
The numerator exponents are all multiples of 3, while the denominator exponents are all positive integers, so B(x)=A(x) and thus bn=an.