Math 3118 Exam 3 Solutions

(20 points) 1. Find the labeled tree on the vertex set {A,B,C,D,E,F,G,H,I} whose corresponding list is HEFBBBE.

Solution: This is a routine problem, see the book.

(20 points) 2. Find a minimal spanning tree for the weighted graph below.

Solution: This is a routine problem, see the book.

(20 points) 3. How many rooted planar trees are there on 6 vertices such that the root has exactly one child?

Solution: If the root has exactly one child, then that child and the 4 other descendents form a rooted planar tree with 5 vertices. So the total number is C_4=14.

(20 points) 4. Recall that K_n is the graph with n vertices, labeled 1, 2, ... ,n, and with exactly one edge connecting every two vertices. So there are (n choose 2) edges in K_n. Let's make the cost every edge equal to 1.
(a) Find the cost of a minimum cost spanning tree of K_n.
(b) How many different spanning trees of K_n have the same cost as your answer to (a)?

Solution: (a) K_n has n vertices, so any spanning tree has n-1 edges. Each edge costs 1, so the minimum cost is n-1.

(b) We just count all possible spanning trees in K_n, since they all cost the same, n-1. By Cayley's formula there are n^{n-2} trees on the labeled vertex set, {1,2,...,n}.

(20 points) 5. How many labeled trees are there on n vertices such that all vertices have degree 1 or 2?

Solution: The corresponding word has length n-2, and each letter in the word can occur at most once. The first position has n choices for its letter, the second position n-1 (anything not equal to the first letter), continuing we have n*(n-1)*(n-2)...*3=n!/2 such trees.

Or we could choose the n-2 letters (n choose n-2)=(n choose 2), and then permute them in (n-2)! ways, for a total of (n choose 2)*(n-2)!=n!/2.