AMS 301.1 First Test, Fall 2009, SOLUTIONS
1. Graphs are isomorphic.See Figure 1.19 in text.
2. Test A: LB = 18 (subtracting first from rows). Don't use (1,3), LB=22; use (1.3) (deleting row 1 & col 3 and setting (entry (3,1) = infinity), LB = 19.
Test B: LB = 14 (subtracting first from rows). Don't use (1,3), LB = 19; use (1,3) (deleting row 1 & col 3 and setting entru (3,1) = infinity), LB= 16
3. Test A: connected; test B: not connected
4. Test A and 5. Test B: vertices equal actuaries/statisticians, edges = personaly conflicts, colors = hotels; does 6 colors suffice?
5. Test A and 4. Test B: a) not possible, violates e <=3v-6; b) possible, v = (Test A, 12), (Test B, 10)-- remember that all vertices musst have deg 3; c) many possibilities, e.g., triangle with trailing path (like a kite),
6. As explained in class, by symmetry and need to use at least one vertical edge, you can assume you start with edge (c,h), at c by symmetry choose b-c & delete c-d, forcing at d, e-d-i. Two cases at b or h or e or i. We consider cases at h
Case 1. Use h-f, delete h-j => at j use e-j-g, at e delete e-a, => at a use b-a-f, subcricuit 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. a) Many possibilities.
b) If a cutset K did not intersect a tree T, then G-K would still be connected since G-K would contain a spanning tree.
c) If G1 and G2 are the two components of G-K, and if circuit C starts in G1, then any time C uses an edge of K, it moves over to G2. It must eventually return to G1, using a second edge of K. Thus crossing to G2 and returning to G1 cna occur many times, but each time the circuit uses 2 edges of K.

AMS301.1 First Test Fall, 2008 SOLUTIONS
1. Test A: a,d = 4,6, b=7,c=5,e=2,f=3,g=1, Text B: a,d = 4,7, b=3, c=5,e=1,f=2,g=6
2. Test A: LB = 16, branch on (4,2), don't use LB = 21, use LB = 18
Test B: LB = 12, branch on (4,2), don't use LB = 18, use LB = 14.
3. Test A: not connected, Test B: a-b-g-f-d-c-e
4. Vertices=ships, edges= overlappig time in port, colors=piers, min = 2.
5. Test A: a) v= 6, not possible, b) v = 8, many possibilities, c) circuit of length 10,
Test B: a) v = 7, not possible, b) v = 6, many possibilities, c) circuit of length 8.
6./7. Ham circuit problem, Must use d-i-m, b-k-n. 3 cases a j: i) e-j-f, ii) e-j-e, iii) e-j-g
i) delete h-j-g, use m-h-c-g-n, forces at n delete n-f and at m delete m-e, at e and f forces, e-a and f-a => subcircuit a-e-j-f-a.
ii) delete f-j-g, use a-f-n-g-c. 3 edges now used at n
iii) delete h-j-f, use a-f-n and m-h-c, at n delete n-g and use g-c, at m delete m-e and use e-a. Delete remaining 2 edges at a and c, isolating d and b.
6./7. Independent set question: a) if a,b same color, then they cannot be adj.
b) 5-circuit has max indep set of 2, n-circuit has size n/2 rounded down size.
c) a tree with one vertex as root and all other vertices as leaves of the root.

AMS 301.2 First Test Spring, 2008 SOLUTIONS
1. Not isomorphic. Subgraphs of deg-3 vertices different.
2. initial LB = 18. Branch on (3,2) or (4,1), Don't Use--LB=21, Use-- LB=18;
3. Not connected.
4. Vertices = animals, colors= areas, edges= animal conflicts.
5. a) Many possiblities: e=13; b) not possible; c) many possiblities.
6. 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. 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.