AMS 301.2 First Test Spring, 2008 SOLUTIONS
1. Not isomorphic. Subgraphs of deg-3 vertices different.
2. Test A: initial LB = 18. Branch on (3,2) or (4,1), Don't Use--LB=21, Use-- LB=18; Test B: initial LB = 15. Branch on (4,1). Don't Use-- LB=17, Use-- LB= 17.
3. Not connected.
4. Vertices = animals, colors= areas, edges= animal conflicts.
5. a) Many possiblities TestA: e=13, TestB: e=15; b) not possible; c) many possiblities.
6. (7 for Test B): use h-i-j; 2 cases at h: Case 1. Use h-b, delete g-h-m, use a-g-l-m-o, at l, delete l-n, use o-n-q, at o delete o-p, use q-p-j, delete at q, q-k, delete at j, j-k; now k has deg 1.
Case 2. Use h-g, delete b-h-m, use a-b-d, l-m-o, at g by symmetry use g-a and delete a-c, use d-c-f, at d delete d-e, use f-e-j, Subc j-i-h-g-a-b-d-c-f-e-j
7. (6. for Test B): a) 5 mutually overlapping circles; b) lots of choices, e.g., two isolated circles; c) 2 sets of 3 concentric circles; circles in one set overlap all circles in other set.

AMS301.1 First Test Fall, 2007 SOLUTIONS
1. 8 pts. Isomorphic: Test A: a=6, b=5, c=4, d=3, e=2, f=7, g=1. Other possibilities.
2. 7 pts Test A: Initial LB = 15, Use 2,4, LB = 15, Don't Use 2,4 LB = 21
Test B: Initial LB = 18, Use 2,4, LB= 18, Don't Use 2,4, LB = 24
3. 4 pt Connected
4. 5 pt Vertices = Classes, Edges= between classes meeting at same times, Colors = Computerized Classrooms.
5. Test A a) v=12, possible, lots of graphs, b) e = 13, not possible, c) possible, lots of graphs
Text B a) v = 12, possible, lots of graphps, b) e = 16, not possible, c) possible, lots of graphs
6. By symmetry start with edge 1-6 (from outer pentagon to inner star) and use edge 1-2, deleting 1-5 which at 5 forces 4-5-10. At 2 or 6 or 4 or 10, we need to consider two cases. Pick 6. Case 1, use 6-9, delete 6-8, at 8 must use 3-8-10; at 10 delete 10-7; at 7, use 2-7-9, subcircuit 1-2-7-9-6-1.
Case 2, use 6-8, delete 6-9, at 9 must use 4-9-7; at 4, delete 4-3, at 3 use 2-3-8, subcircuit 1-6-8-3-2-1.
7a Maximum degree of a guest vertex is 5 (cannot shake own hand or spouse's hand). If all 6 guest vertex degrees are different, only possibility is 0,1,2,3,4,5.
b) Since 3 guest vertices have odd deg, Trump vertex must have odd deg. so that total number of vertices of odd deg is even.
c) Draw graph by connecting vertex of deg 5 to every other vertex except spouse, Spouse of deg-5 vertex must be vertex of deg 0 (since all other vertices now have positive degree). Next, pick one of the guest vertices adj to deg-5 vert to be the vertex of deg 4, connecting it to all other vertices except its spouse and the vertex of deg 0. The spouse of the deg 4 vertex must be the deg 1 vertex because all other unspecificed vertices have deg 2. Finally, the remaining two guest vertices, which are spouses of each other, currently each have degree 2. One must have degree 3-- only choice for third edge is to go to Trump. So vertices of deg 5,4,3 are adjacent to Trump. Trumps has deg 3.

AMS301.1 First Test Fall,2006 SOLUTIONS
1. (7 pts) Isomorphic a=1, b=6, c=3, d=8,e=5, f=2, h=4, i=9.

2. (8 pts) Test A: LB=18, Branch on (1,3), Don't Use, LB=22, Use LB=19; also could branch on (2,4).
Test B: LB=13, Branch on (2,4), Don't use LB = 17, Use LB = 13; also could use (3,1).

3. (4 pts) Test A: Connected: a-b-c-f-d, back up to a, a-g-e.
Test B: Not connected, a-c-b. back up to c, c-d-f (can't reach e or g.

4. (5 pts) Test A: Vert = actuaries, edges = personality confict; colors = hotels.
Test B: Vert = animals, edges = can't live togehter, colors = open areas.

5. (12=4+4+4 pts) Test A: a) v = 6, not possible; b) v=10, possible; c) lots of possibilities.
Test B: a) v=8, possible, b) v = 10, possible, c) lots of possibilities (must include a K4).

` 6.(15 pts) Assumme vertical edge (c,h) used, by symmetry, assume other edge at c is c-b. At c delete c-d and at d use e-d-i. Two cases at h or d. We pick h.
Case 1: use h-f, delete h-j, at j use e-j-g. At e delete e-a, and at a use b-a-f => subcircuit a-b-c-h-f-a.
Case 2: use h-j, delete h-f, at f use a-f-i. At i, delete i-g. At g use b-g-j => subcircuit b-c-h-j-g-b.

7. (12 = 3+4+5 pts) Edge coloring = colors edges so that no two edges with a common endpoiint have the same color. Vert=people, edges= games, colors=days.
4-person tournament can be edge-3-colored (e.g. day 1: 1-2,3-4, day 2: 1-3,2-4, day 3: 1-4, 2-3).
5-person tournament can be edge-5-colored (2 games a day; one person sits out each day, e.g., day1:1-2,3-5, day2:2-3,1-4, day3: 3-4,2-5, day4: 4-5,3-1, day5: 5-1,2-4).