1. TRUE. A tree with 12 vertices has 11 edges, so the largest possible degree is 11.
2. The edges formed (in order) are HF, GE, GA, DF, FB, CA, AB.
3. The path 0-1-2-3-4 costs 4 since each edge costs 1, this is the smallest possible since each edge costs at least 1.
4. We need lists of length 8 in 10 letters, and those with exactly 3 A's. The total is (8 choose 3)* 9^5.
5. The Catalan number C_5=1/6*(10 choose 5)=42.
1. TRUE. There are at least 2 terminal verticies for any tree. Let the tree have n vertices and thus n-1 edges. One way to see this is that the sum of the vertex degrees is twice the number of edges, which is 2*(n-1). If all but one of the vertices had degree at least two, this sum would be at least 2*(n-1)+1, which is impossible.
2. The non-terminal vertices are (A,B,E,F), the terminal vertices are (C,D,G).
Remove G, write down E, new non-terminal vertices are (A,B,F), the terminal vertices are (C,D,E).
Remove E, write down B, new non-terminal vertices are (A,B,F), the terminal vertices are (C,D).
Remove D, write down A, new non-terminal vertices are (B,F), the terminal vertices are (A,C,E).
Remove C, write down B, new non-terminal vertex is (F), the terminal vertices are (A,B).
Remove B, write down F, non-terminal vertices are gone, the terminal vertices are (A,F).
The word is EBABF.
3. Take a graph with 4 vertices A,B,C,D: ABC form a circuit of length 3, and add an edge from DA to A. Then any spanning tree must use the edge DA, so make it the most expensive edge.
4. How many words of length 5 in the letters A,B,C,D,E,F,G have a letter appearing exactly 4 times? Clearly we can use only one such letter. So choose which letter appears 4 times (7 choices), then choose the four positions it occupies (5 choose 4), and finally fill in the last position (6 choices), so the answer is 7*(5 choose 4)*6=7*5*6=210.
5. One tree with 5 vertices alone: C_4=14. Two trees: C_0*C_3+C_1*C_2+C_2*C_1+C_3*C_0=14.
Three trees: C_0*C_0*C_2+C_0*C_1*C_1+C_0*C_2*C_0+C_1*C_0*C_1+C_1*C_1*C_0+C_2*C_0*C_0=9.
Four trees: C_0*C_0*C_0*C_1+C_0*C_0*C_1*C_0+C_0*C_1*C_0*C_0+C_1*C_0*C_0*C_0=4.
Five trees: C_0*C_0*C_0*C_0*C_0=1
for a total of 42 forests. A simpler way to see this is to tie the forests together in a root, and get a rooted tree with 6 vertices, there are C_5=42 such trees.
1. FALSE. We could take any word of length 10 with 4 A's, 4 B's, and the other two positions arbitrary. Then our 1-1 correspondence will give us a tree where both A and B have degree 5.
2. word =(I,E,E,A,E,I,E), Non-terminal vertices (A,E,I), terminal vertices (B,C,D,F,G,H).
Connect H to I, new word (E,E,A,E,I,E), non-terminal vertices (A,E,I), terminal vertices (B,C,D,F,G).
Connect E to G, new word (E,A,E,I,E), non-terminal vertices (A,E,I), terminal vertices (B,C,D,F).
Connect E to F, new word (A,E,I,E), non-terminal vertices (A,E,I), terminal vertices (B,C,D).
Connect A to D, new word (E,I,E), non-terminal vertices (E,I), terminal vertices (A,B,C).
Connect E to C, new word (I,E), non-terminal vertices (E,I), terminal vertices (A,B).
Connect I to B, new word (E), non-terminal vertices (E), terminal vertices (A,I).
Connect E to I, new word empty, non-terminal vertices, terminal vertices (A,E).
Finally connect A to E. This gives us 8 edges.
3. The non-terminal vertices are (B,G), the terminal vertices are (A,C,D,E,F).
Remove F, write down B, new non-terminal vertices are (B,G), the terminal vertices are (A,C,D,E).
Remove E, write down B, new non-terminal vertices are (B,G), the terminal vertices are (A,C,D).
Remove D, write down G, new non-terminal vertices are (B,F), the terminal vertices are (A,C).
Remove C, write down B, new non-terminal vertex is (G), the terminal vertices are (A,B).
Remove B, write down G, non-terminal vertices are gone, the terminal vertices are (A,G).
The word is BBGBG.
4. Choose edges AD (cost 1), AC (cost 2), BC (cost 2), DE (cost 3), the total cost is 8.
5. We must find the number of pairs (T_1, T_2) of rooted trees, with 5 vertices. The first tree T_1 could have 1,2,3 or 4 vertices, while T_2 has 4,3,2, or 1. So the total is
C_0*C+3+C_1*C_2+C_2*C_1+C_3*C_0=5+2+2+5=14.