My comments (JP)

Q1
a) well done
b) T is a spanning tree if any 2 of the following hold:
	1. T is connected
	2. T has n-1 arcs where n=|V|
	3. T has no circuits
c) not required
d) not marked because it was subject to interpretation
e) most people received 1 out of 2. see the solutions for the correct
answer. this may be a bit harsh as I am told what was done in class may
have been misleading but nonetheless it is good to think about why what
you put is not quite right.

Q2
a) well done
b) fairly well done
c) need c_ij - yi + yj = 0. Note the -ve sign !
   the multipliers are not unique !!
d) fairly well done
e) good

Please see me if you have any concerns.

John-Paul Pretti (J.P.) 
University of Waterloo
Department of Combinatorics & Optimization
MC 5136A (519)888-4567 x6895