Exam practice: the whole unit Problem set B Answers

Yes, it is possible. There are exactly 2 vertices of odd degree, B and F: start at one and finish at the other.

1. (a) 10
2. (b) 13
3. (c) 12
4. (d) 9

UB = 60: E-C-F-B-D-A-E

1. (a) AB (4), BC (7), BE (10), EG (5), FG (3)
2. (b) 29

1. (a) Yes, it is possible. There are exactly 2 vertices of odd degree, B and E: start at one and finish at the other.
2. (b) CE = 15; BF = 12; EF = 12; DG = 7
3. (c) UB = 56
4. (d) Edges BC (4), DE (5), AC (7), CF (8), CD (10); weight 34
5. (e) LB = 43
6. (f) Delete a different vertex (and find the lower bound again); the largest lower bound is the best.
7. (g) 49.5

1. (a) UB = 69
2. (b) LB = 62
3. (c) Try deleting a different vertex. Deleting D gives 61; the better lower bound is 62.