## Math 3118 Practice Exam 3-1

1. True or False? A tree on 12 vertices cannot have a vertex of degree 14.

2. Find the tree on 8 vertices (A,B,C,D,E,F,G,H) whose corresponding list is (F,G, A, F, B, A).

3. Let G be the graph whose vertices are labeled 1,2,3,4,5, and whose edges i-j cost |i-j|. This means that the edge from 2 to 5 costs 3. Find a minimum spanning tree for G.

4. How many labeled trees on 10 vertices have vertex A with degree 4?

5. How many rooted trees on 6 vertices are there?

## Math 3118 Practice Exam 3-2

1. True or False? A tree on 12 vertices cannot have exactly one vertex of degree 1.

2. Find the corresponding list for the tree whose edges are AF, BE, BF, BC, AD, EG.

3. Give an example of a graph whose minimum spanning tree must use the largest cost edge.

4. How many labeled trees on 7 vertices have a vertex of degree 6?

5. How many forests of rooted trees are there with 5 vertices?

## Math 3118 Practice Exam 3-3 (really long)

1. True or False? A tree on 12 vertices cannot have 2 different vertices of degree 5.

2. Find the tree on 9 vertices (A,B,C,D,E,F,G,H,I) whose corresponding word is (I,E,E,A,E,I,E).

3. Find the corresponding list for the tree whose edges are AG, BG, BC, DG, BE, BF.

4. Find a minimum spanning tree for the graph below whose costs of edges are given below:

edge AB: 3, edge AC:2 edge AD:1, edge AE:4,edge BC: 2, edge BD:5, edge BE: 3; edge CD: 2 edge CE:4, edge DE: 3.

5. How many rooted trees on 6 vertices are there whose root has exactly 2 sons?

6. How many labeled trees on 10 vertices have degrees of vertices which are only 1 or 2, (nothing larger than 2 is allowed) ?